Got rid of class template AliFMD<Type> on request of Federico, who
[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 #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
33
34 //____________________________________________________________________
35 ClassImp(AliFMDPolygon);
36
37 //____________________________________________________________________
38 AliFMDPolygon::AliFMDPolygon()
39   : fState(kUnknown)
40 {}
41
42 //____________________________________________________________________
43 AliFMDPolygon::~AliFMDPolygon() 
44 {
45   fVerticies.Delete();
46 }
47
48 //____________________________________________________________________
49 bool
50 AliFMDPolygon::AddVertex(double x, double y) 
51 {
52   // Add points in order to the polygon. 
53   TVector2* c = new TVector2(x,y);
54   return AddVertex(c);
55 }
56 //____________________________________________________________________
57 bool
58 AliFMDPolygon::AddVertex(TVector2* c) 
59 {
60   // Add points in order to the polygon.
61   //
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).
66   if (!c) return false;
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", 
72             c->X(), c->Y());
73       return false;
74     }
75   }
76   fState = kUnknown;
77   fVerticies.AddAtAndExpand(c, fVerticies.GetEntries());
78   return true;
79 }
80
81 //____________________________________________________________________
82 const TVector2&
83 AliFMDPolygon::GetVertex(size_t i) const
84 {
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)));
90 }
91
92 //____________________________________________________________________
93 bool
94 AliFMDPolygon::Contains(const TVector2* c) const
95 {
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.
99    * 
100    * Suppose we had the polygon and point 
101    *
102    *     2 x----x 1
103    *      /      \\
104    *    3 x   P   x 0
105    *      \\      /
106    *     4 x----x 5
107    * 
108    * Then, P is on LHS of the segment 0->1, 1->2, ..., and 5->0, and
109    * so inside the polygon.
110    * 
111    * Suppose instead the point was like
112    * 
113    *     2 x----x 1
114    *      /      \\    P
115    *    3 x       x 0
116    *      \\      /
117    *     4 x----x 5
118    * 
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.
122    */ 
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.
131       return false;
132   return true;
133 }
134
135 //____________________________________________________________________
136 bool
137 AliFMDPolygon::Contains(double x, double y) const
138 {
139   TVector2 c(x,y);
140   return Contains(&c);
141 }
142
143 //____________________________________________________________________
144 bool
145 AliFMDPolygon::ConvexCheck() const
146 {
147   /* 
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
150    * next vertex.
151    * 
152    * Suppose we have the polygon 
153    *           
154    *     2 x----x 1
155    *      /      \\
156    *    3 x       x 0
157    *      \\      /
158    *     4 x----x 5
159    * 
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.
163    * 
164    * If we had a polygon like
165    *
166    *     2 x----x 1
167    *        \\    \\
168    *       3 x    x 0
169    *        /     /
170    *     4 x----x 5
171    * 
172    * Then, the vertex 4 is NOT on the LHS of the segment 2->3, and so
173    * the polygon is NOT convex.
174    */
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);
188       return false;
189     }
190   }
191   return true;
192 }
193     
194 //____________________________________________________________________
195 bool
196 AliFMDPolygon::IsOnLeftHand(const TVector2* c, size_t i1, size_t i2) const
197 {
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.
200    * 
201    * Suppose we have the segment and point 
202    * 
203    *     1 x
204    *        \\    P
205    *         x 0  
206    *
207    * Then, we define the vectors 
208    *
209    *   v: 0->P 
210    *   u: perpendicular to 1->0 
211    * 
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
214    * RHS of the segment
215    *
216    * Suppose we had 
217    *
218    *       1 x
219    *    P     \\    
220    *           x 0  
221    *
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
225    */
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);
232 }
233
234 //____________________________________________________________________
235 void
236 AliFMDPolygon::Clear(Option_t*) 
237 {
238   fState = kUnknown;
239   fVerticies.Delete();
240   // fVerticies.Resize(0);
241 }
242
243 //____________________________________________________________________
244 void
245 AliFMDPolygon::Draw(const char* option, const char* name) const 
246 {
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());
254   }
255   const TVector2& v = GetVertex(0);
256   g->SetPoint(n, v.X(), v.Y());
257   g->Draw(option);
258   TString opt(option);
259   if (!opt.Contains("p", TString::kIgnoreCase))
260     return;
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));
264     t->Draw();
265   }
266 }
267
268 //____________________________________________________________________
269 //
270 // EOf
271 //