]>
Commit | Line | Data |
---|---|---|
4347b38f | 1 | /************************************************************************** |
2 | * Copyright(c) 2004, ALICE Experiment at CERN, All rights reserved. * | |
3 | * * | |
4 | * Author: The ALICE Off-line Project. * | |
5 | * Contributors are mentioned in the code where appropriate. * | |
6 | * * | |
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 | **************************************************************************/ | |
15 | ||
16 | /* $Id$ */ | |
17 | ||
18 | ////////////////////////////////////////////////////////////////////////////// | |
19 | // | |
20 | // Utility class to help implement shape of the FMD modules | |
21 | // | |
22 | // Latest changes by Christian Holm Christensen | |
23 | // | |
24 | ////////////////////////////////////////////////////////////////////////////// | |
25 | #ifndef ALIFMDPOLYGON_H | |
26 | # include "AliFMDPolygon.h" | |
27 | #endif | |
28 | #ifndef ALILOG_H | |
29 | # include "AliLog.h" | |
30 | #endif | |
31 | #ifndef ROOT_TString | |
32 | # include <TString.h> | |
33 | #endif | |
34 | #ifndef ROOT_TVector2 | |
35 | # include <TVector2.h> | |
36 | #endif | |
37 | #ifndef ROOT_TCanvas | |
38 | # include <TCanvas.h> | |
39 | #endif | |
40 | #ifndef ROOT_TText | |
41 | # include <TText.h> | |
42 | #endif | |
43 | #ifndef ROOT_TGraph | |
44 | # include <TGraph.h> | |
45 | #endif | |
46 | #ifndef ROOT_TError | |
47 | # include <TError.h> | |
48 | #endif | |
49 | ||
50 | //____________________________________________________________________ | |
51 | ClassImp(AliFMDPolygon); | |
52 | ||
53 | //____________________________________________________________________ | |
54 | AliFMDPolygon::AliFMDPolygon() | |
55 | : fState(kUnknown) | |
56 | {} | |
57 | ||
58 | //____________________________________________________________________ | |
59 | AliFMDPolygon::~AliFMDPolygon() | |
60 | { | |
61 | fVerticies.Delete(); | |
62 | } | |
63 | ||
64 | //____________________________________________________________________ | |
65 | bool | |
66 | AliFMDPolygon::AddVertex(double x, double y) | |
67 | { | |
68 | // Add points in order to the polygon. | |
69 | TVector2* c = new TVector2(x,y); | |
70 | return AddVertex(c); | |
71 | } | |
72 | //____________________________________________________________________ | |
73 | bool | |
74 | AliFMDPolygon::AddVertex(TVector2* c) | |
75 | { | |
76 | // Add points in order to the polygon. | |
77 | // | |
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). | |
82 | if (!c) return false; | |
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", | |
88 | c->X(), c->Y()); | |
89 | return false; | |
90 | } | |
91 | } | |
92 | fState = kUnknown; | |
93 | fVerticies.AddAtAndExpand(c, fVerticies.GetEntries()); | |
94 | return true; | |
95 | } | |
96 | ||
97 | //____________________________________________________________________ | |
98 | const TVector2& | |
99 | AliFMDPolygon::GetVertex(size_t i) const | |
100 | { | |
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))); | |
106 | } | |
107 | ||
108 | //____________________________________________________________________ | |
109 | bool | |
110 | AliFMDPolygon::Contains(const TVector2* c) const | |
111 | { | |
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. | |
115 | * | |
116 | * Suppose we had the polygon and point | |
117 | * | |
118 | * 2 x----x 1 | |
119 | * / \\ | |
120 | * 3 x P x 0 | |
121 | * \\ / | |
122 | * 4 x----x 5 | |
123 | * | |
124 | * Then, P is on LHS of the segment 0->1, 1->2, ..., and 5->0, and | |
125 | * so inside the polygon. | |
126 | * | |
127 | * Suppose instead the point was like | |
128 | * | |
129 | * 2 x----x 1 | |
130 | * / \\ P | |
131 | * 3 x x 0 | |
132 | * \\ / | |
133 | * 4 x----x 5 | |
134 | * | |
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. | |
138 | */ | |
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. | |
147 | return false; | |
148 | return true; | |
149 | } | |
150 | ||
151 | //____________________________________________________________________ | |
152 | bool | |
153 | AliFMDPolygon::Contains(double x, double y) const | |
154 | { | |
155 | TVector2 c(x,y); | |
156 | return Contains(&c); | |
157 | } | |
158 | ||
159 | //____________________________________________________________________ | |
160 | bool | |
161 | AliFMDPolygon::ConvexCheck() const | |
162 | { | |
163 | /* | |
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 | |
166 | * next vertex. | |
167 | * | |
168 | * Suppose we have the polygon | |
169 | * | |
170 | * 2 x----x 1 | |
171 | * / \\ | |
172 | * 3 x x 0 | |
173 | * \\ / | |
174 | * 4 x----x 5 | |
175 | * | |
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. | |
179 | * | |
180 | * If we had a polygon like | |
181 | * | |
182 | * 2 x----x 1 | |
183 | * \\ \\ | |
184 | * 3 x x 0 | |
185 | * / / | |
186 | * 4 x----x 5 | |
187 | * | |
188 | * Then, the vertex 4 is NOT on the LHS of the segment 2->3, and so | |
189 | * the polygon is NOT convex. | |
190 | */ | |
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); | |
204 | return false; | |
205 | } | |
206 | } | |
207 | return true; | |
208 | } | |
209 | ||
210 | //____________________________________________________________________ | |
211 | bool | |
212 | AliFMDPolygon::IsOnLeftHand(const TVector2* c, size_t i1, size_t i2) const | |
213 | { | |
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. | |
216 | * | |
217 | * Suppose we have the segment and point | |
218 | * | |
219 | * 1 x | |
220 | * \\ P | |
221 | * x 0 | |
222 | * | |
223 | * Then, we define the vectors | |
224 | * | |
225 | * v: 0->P | |
226 | * u: perpendicular to 1->0 | |
227 | * | |
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 | |
230 | * RHS of the segment | |
231 | * | |
232 | * Suppose we had | |
233 | * | |
234 | * 1 x | |
235 | * P \\ | |
236 | * x 0 | |
237 | * | |
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 | |
241 | */ | |
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); | |
248 | } | |
249 | ||
250 | //____________________________________________________________________ | |
251 | void | |
252 | AliFMDPolygon::Clear(Option_t*) | |
253 | { | |
254 | fState = kUnknown; | |
255 | fVerticies.Delete(); | |
256 | // fVerticies.Resize(0); | |
257 | } | |
258 | ||
259 | //____________________________________________________________________ | |
260 | void | |
261 | AliFMDPolygon::Draw(const char* option, const char* name) const | |
262 | { | |
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()); | |
270 | } | |
271 | const TVector2& v = GetVertex(0); | |
272 | g->SetPoint(n, v.X(), v.Y()); | |
273 | g->Draw(option); | |
274 | TString opt(option); | |
275 | if (!opt.Contains("p", TString::kIgnoreCase)) | |
276 | return; | |
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)); | |
280 | t->Draw(); | |
281 | } | |
282 | } | |
283 | ||
284 | //____________________________________________________________________ | |
285 | // | |
286 | // EOf | |
287 | // |