Complete rewrite of the FMD code.
[u/mrichter/AliRoot.git] / FMD / AliFMDPolygon.cxx
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 //