1 /**************************************************************************
2 * Copyright(c) 2004, ALICE Experiment at CERN, All rights reserved. *
4 * Author: The ALICE Off-line Project. *
5 * Contributors are mentioned in the code where appropriate. *
7 * Permission to use, copy, modify and distribute this software and its *
8 * documentation strictly for non-commercial purposes is hereby granted *
9 * without fee, provided that the above copyright notice appears in all *
10 * copies and that both the copyright notice and this permission notice *
11 * appear in the supporting documentation. The authors make no claims *
12 * about the suitability of this software for any purpose. It is *
13 * provided "as is" without express or implied warranty. *
14 **************************************************************************/
18 //////////////////////////////////////////////////////////////////////////////
20 // Utility class to help implement shape of the FMD modules
22 // Latest changes by Christian Holm Christensen
24 //////////////////////////////////////////////////////////////////////////////
25 #include "AliFMDPolygon.h" // ALIFMDPOLYGON_H
26 #include "AliLog.h" // ALILOG_H
27 #include "TString.h" // ROOT_TString
28 #include "TVector2.h" // ROOT_TVector2
29 #include "TCanvas.h" // ROOT_TCanvas
30 #include "TText.h" // ROOT_TText
31 #include "TGraph.h" // ROOT_TGraph
32 #include "TError.h" // ROOT_TError
34 //____________________________________________________________________
35 ClassImp(AliFMDPolygon);
37 //____________________________________________________________________
38 AliFMDPolygon::AliFMDPolygon()
42 //____________________________________________________________________
43 AliFMDPolygon::~AliFMDPolygon()
48 //____________________________________________________________________
50 AliFMDPolygon::AddVertex(double x, double y)
52 // Add points in order to the polygon.
53 TVector2* c = new TVector2(x,y);
56 //____________________________________________________________________
58 AliFMDPolygon::AddVertex(TVector2* c)
60 // Add points in order to the polygon.
62 // Checks if the addition of the vertex makes the alipolygon
63 // concave, and if it does, returns false. Note, that the check
64 // isn't performed until at least 3 verticies have already been
65 // added to the alipolygon (a triangle is always convex).
67 if (fVerticies.GetEntries() >= 3) {
68 if (!IsOnLeftHand(c, fVerticies.GetEntries()-2,
69 fVerticies.GetEntries()-1)) {
70 Error("AliFMDPolygon::AddVertex",
71 "Adding vertex (%f,%f) makes alipolygon concave",
77 fVerticies.AddAtAndExpand(c, fVerticies.GetEntries());
81 //____________________________________________________________________
83 AliFMDPolygon::GetVertex(size_t i) const
85 // Get one of the verticies
86 if (i > size_t(fVerticies.GetEntries()))
87 Fatal("AliFMDPolygon::GetVertex", "Index %d out of range [0,%d]",
88 i, fVerticies.GetEntries());
89 return *(static_cast<TVector2*>(fVerticies.At(i)));
92 //____________________________________________________________________
94 AliFMDPolygon::Contains(const TVector2* c) const
96 /* This function checks if a point is inside the polygon. It does
97 * that by looping over the segments of the polygon, and decides
98 * wether the point is on the left-hand-side (LHS) of the segment.
100 * Suppose we had the polygon and point
108 * Then, P is on LHS of the segment 0->1, 1->2, ..., and 5->0, and
109 * so inside the polygon.
111 * Suppose instead the point was like
119 * Then it would still be on the LHS of the segments 1->2, 2->3,
120 * 3->4, 4->5, but on the right-hand-side of 5->0, and 0->1 and
121 * hence outside the polygon.
123 if (!c) return kFALSE;
124 if (fState == kUnknown) fState = (ConvexCheck() ? kConvex : kConcave);
125 if (fState == kConcave) return false;
126 size_t n = fVerticies.GetEntries();
127 for (size_t i = 0; i < n; ++i)
128 if (!IsOnLeftHand(c, i, (i + 1) % n))
129 // If point is on the left hand side of the segment, it's
130 // outside the polygon.
135 //____________________________________________________________________
137 AliFMDPolygon::Contains(double x, double y) const
143 //____________________________________________________________________
145 AliFMDPolygon::ConvexCheck() const
148 * This member function loops through the verticies, and checks if
149 * the next-to-next vertex is in between the current vertex and the
152 * Suppose we have the polygon
160 * Then the vertex 2 is on the left-hand-side (LHS) of the segment
161 * 0->1, 3 is on the LHS of 1->2, ..., and 0 is on the RHS of 4->5,
162 * and so the polygon is convex.
164 * If we had a polygon like
172 * Then, the vertex 4 is NOT on the LHS of the segment 2->3, and so
173 * the polygon is NOT convex.
175 size_t n = fVerticies.GetEntries();
176 // A triangle is always convex.
177 if (n <= 3) return true;
178 for (size_t i = 0; i < n; i++) {
179 // Get the next, and next-to-next indicies, taking care to go
180 // around the polygon.
181 size_t j = (i + 1) % n;
182 size_t k = (i + 2) % n;
183 // Check The next-to-next vertex is on the LHS of the current
184 // vertex and the next vertex
185 if (!IsOnLeftHand(static_cast<TVector2*>(fVerticies.At(k)), i, j)) {
186 Error("AliFMDPolygon::ConvexCheck",
187 "AliFMDPolygon is concave at segment %d -> %d" , i, j);
194 //____________________________________________________________________
196 AliFMDPolygon::IsOnLeftHand(const TVector2* c, size_t i1, size_t i2) const
198 /* Check if a point is on the left-hand-side (LHS) or
199 * right-hand-side (RHS) of the segment defined by the two indicies.
201 * Suppose we have the segment and point
207 * Then, we define the vectors
210 * u: perpendicular to 1->0
212 * The dot product of u and v is >= 0, meaning that the
213 * angle between the two vectors is in [0,pi], and so P is on the
222 * And defining the vectors u,v as above. In this case the dot
223 * product is less than 0, meaning the angle between u,v is in
224 * (pi,2pi], and so P is on the LHS of the segment
226 if (!c) return false;
227 const TVector2& v1 = GetVertex(i1);
228 const TVector2& v2 = GetVertex(i2);
229 double dot = ( (c->X() - v1.X()) * (v2.Y() - v1.Y())
230 - (c->Y() - v1.Y()) * (v2.X() - v1.X()));
231 return (dot < 0 ? true : false);
234 //____________________________________________________________________
236 AliFMDPolygon::Clear(Option_t*)
240 // fVerticies.Resize(0);
243 //____________________________________________________________________
245 AliFMDPolygon::Draw(const char* option, const char* name) const
247 size_t n = fVerticies.GetEntries();
248 TGraph* g = new TGraph(n+1);
249 if (name) g->SetName(name);
250 g->SetMarkerStyle(20);
251 for (size_t i = 0; i < n; i++) {
252 const TVector2& v = GetVertex(i);
253 g->SetPoint(i, v.X(), v.Y());
255 const TVector2& v = GetVertex(0);
256 g->SetPoint(n, v.X(), v.Y());
259 if (!opt.Contains("p", TString::kIgnoreCase))
261 for (size_t i = 0; i < n; i++) {
262 const TVector2& v = GetVertex(i);
263 TText* t = new TText(v.X(), v.Y(), Form("%d", i));
268 //____________________________________________________________________