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 #ifndef ALIFMDPOLYGON_H
26 # include "AliFMDPolygon.h"
35 # include <TVector2.h>
50 //____________________________________________________________________
51 ClassImp(AliFMDPolygon);
53 //____________________________________________________________________
54 AliFMDPolygon::AliFMDPolygon()
58 //____________________________________________________________________
59 AliFMDPolygon::~AliFMDPolygon()
64 //____________________________________________________________________
66 AliFMDPolygon::AddVertex(double x, double y)
68 // Add points in order to the polygon.
69 TVector2* c = new TVector2(x,y);
72 //____________________________________________________________________
74 AliFMDPolygon::AddVertex(TVector2* c)
76 // Add points in order to the polygon.
78 // Checks if the addition of the vertex makes the alipolygon
79 // concave, and if it does, returns false. Note, that the check
80 // isn't performed until at least 3 verticies have already been
81 // added to the alipolygon (a triangle is always convex).
83 if (fVerticies.GetEntries() >= 3) {
84 if (!IsOnLeftHand(c, fVerticies.GetEntries()-2,
85 fVerticies.GetEntries()-1)) {
86 Error("AliFMDPolygon::AddVertex",
87 "Adding vertex (%f,%f) makes alipolygon concave",
93 fVerticies.AddAtAndExpand(c, fVerticies.GetEntries());
97 //____________________________________________________________________
99 AliFMDPolygon::GetVertex(size_t i) const
101 // Get one of the verticies
102 if (i > size_t(fVerticies.GetEntries()))
103 Fatal("AliFMDPolygon::GetVertex", "Index %d out of range [0,%d]",
104 i, fVerticies.GetEntries());
105 return *(static_cast<TVector2*>(fVerticies.At(i)));
108 //____________________________________________________________________
110 AliFMDPolygon::Contains(const TVector2* c) const
112 /* This function checks if a point is inside the polygon. It does
113 * that by looping over the segments of the polygon, and decides
114 * wether the point is on the left-hand-side (LHS) of the segment.
116 * Suppose we had the polygon and point
124 * Then, P is on LHS of the segment 0->1, 1->2, ..., and 5->0, and
125 * so inside the polygon.
127 * Suppose instead the point was like
135 * Then it would still be on the LHS of the segments 1->2, 2->3,
136 * 3->4, 4->5, but on the right-hand-side of 5->0, and 0->1 and
137 * hence outside the polygon.
139 if (!c) return kFALSE;
140 if (fState == kUnknown) fState = (ConvexCheck() ? kConvex : kConcave);
141 if (fState == kConcave) return false;
142 size_t n = fVerticies.GetEntries();
143 for (size_t i = 0; i < n; ++i)
144 if (!IsOnLeftHand(c, i, (i + 1) % n))
145 // If point is on the left hand side of the segment, it's
146 // outside the polygon.
151 //____________________________________________________________________
153 AliFMDPolygon::Contains(double x, double y) const
159 //____________________________________________________________________
161 AliFMDPolygon::ConvexCheck() const
164 * This member function loops through the verticies, and checks if
165 * the next-to-next vertex is in between the current vertex and the
168 * Suppose we have the polygon
176 * Then the vertex 2 is on the left-hand-side (LHS) of the segment
177 * 0->1, 3 is on the LHS of 1->2, ..., and 0 is on the RHS of 4->5,
178 * and so the polygon is convex.
180 * If we had a polygon like
188 * Then, the vertex 4 is NOT on the LHS of the segment 2->3, and so
189 * the polygon is NOT convex.
191 size_t n = fVerticies.GetEntries();
192 // A triangle is always convex.
193 if (n <= 3) return true;
194 for (size_t i = 0; i < n; i++) {
195 // Get the next, and next-to-next indicies, taking care to go
196 // around the polygon.
197 size_t j = (i + 1) % n;
198 size_t k = (i + 2) % n;
199 // Check The next-to-next vertex is on the LHS of the current
200 // vertex and the next vertex
201 if (!IsOnLeftHand(static_cast<TVector2*>(fVerticies.At(k)), i, j)) {
202 Error("AliFMDPolygon::ConvexCheck",
203 "AliFMDPolygon is concave at segment %d -> %d" , i, j);
210 //____________________________________________________________________
212 AliFMDPolygon::IsOnLeftHand(const TVector2* c, size_t i1, size_t i2) const
214 /* Check if a point is on the left-hand-side (LHS) or
215 * right-hand-side (RHS) of the segment defined by the two indicies.
217 * Suppose we have the segment and point
223 * Then, we define the vectors
226 * u: perpendicular to 1->0
228 * The dot product of u and v is >= 0, meaning that the
229 * angle between the two vectors is in [0,pi], and so P is on the
238 * And defining the vectors u,v as above. In this case the dot
239 * product is less than 0, meaning the angle between u,v is in
240 * (pi,2pi], and so P is on the LHS of the segment
242 if (!c) return false;
243 const TVector2& v1 = GetVertex(i1);
244 const TVector2& v2 = GetVertex(i2);
245 double dot = ( (c->X() - v1.X()) * (v2.Y() - v1.Y())
246 - (c->Y() - v1.Y()) * (v2.X() - v1.X()));
247 return (dot < 0 ? true : false);
250 //____________________________________________________________________
252 AliFMDPolygon::Clear(Option_t*)
256 // fVerticies.Resize(0);
259 //____________________________________________________________________
261 AliFMDPolygon::Draw(const char* option, const char* name) const
263 size_t n = fVerticies.GetEntries();
264 TGraph* g = new TGraph(n+1);
265 if (name) g->SetName(name);
266 g->SetMarkerStyle(20);
267 for (size_t i = 0; i < n; i++) {
268 const TVector2& v = GetVertex(i);
269 g->SetPoint(i, v.X(), v.Y());
271 const TVector2& v = GetVertex(0);
272 g->SetPoint(n, v.X(), v.Y());
275 if (!opt.Contains("p", TString::kIgnoreCase))
277 for (size_t i = 0; i < n; i++) {
278 const TVector2& v = GetVertex(i);
279 TText* t = new TText(v.X(), v.Y(), Form("%d", i));
284 //____________________________________________________________________