Fix coverity defect
[u/mrichter/AliRoot.git] / MUON / AliMUONContourMaker.cxx
1 /**************************************************************************
2 * Copyright(c) 1998-1999, 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 /// Maker/merger of contours. Can create contour from a set polygons or
20 /// merger a set of contours into a single one.
21 /// 
22 /// This is based on (one of the) algorithm found in 
23 /// Diane L. Souvaine and Iliana Bjorling-Sachs,
24 /// Proceedings of the IEEE, Vol. 80, No. 9, September 1992, p. 1449
25 ///
26 /// Note that besides the AliMUON prefix, nothing is really MUON specific
27 /// in this class...
28 ///
29 /// \author Laurent Aphecetche, Subatech
30 ///
31
32 #include "AliMUONContourMaker.h"
33
34 #include "AliCodeTimer.h"
35 #include "AliLog.h"
36 #include "AliMUONContour.h"
37 #include "AliMUONPointWithRef.h"
38 #include "AliMUONPolygon.h"
39 #include "AliMUONSegment.h"
40 #include "AliMUONSegmentTree.h"
41 #include "Riostream.h"
42 #include "TArrayD.h"
43 #include "TMath.h"
44 #include <cassert>
45 #include "TArrayI.h"
46
47 /// \cond CLASSIMP
48 ClassImp(AliMUONContourMaker)
49 /// \endcond
50
51 //_____________________________________________________________________________
52 AliMUONContourMaker::AliMUONContourMaker() 
53 {
54 /// Default constructor
55 }
56
57
58 //_____________________________________________________________________________
59 AliMUONContourMaker::~AliMUONContourMaker()
60 {
61 /// Destructor
62 }
63
64 //_____________________________________________________________________________
65 AliMUONContour* 
66 AliMUONContourMaker::CreateContour(const TObjArray& polygons, const char* name) const
67 {
68   /// Create the contour of the polygon array
69   /// and get back the intermediate verticals and horizontal segments
70   /// both arrays are arrays of AliMUONSegment objects.
71   
72   AliCodeTimerAuto("",0);
73   
74   if ( polygons.IsEmpty() ) return 0x0; // protection against user error...
75   
76   // Sanity check : insure that all polygons are oriented counter-clockwise
77   TIter next(&polygons);
78   AliMUONPolygon* pol;
79   while ( ( pol = static_cast<AliMUONPolygon*>(next()) ) )
80   {
81     if ( !pol->IsCounterClockwiseOriented() )
82     {
83       AliError(Form("Got a clockwise oriented polygon in CreateContour(%s). That's not OK !",name));
84       StdoutToAliError(polygons.Print());
85       return 0x0;
86     }
87   }
88   
89   AliMUONContour* contour(0x0);
90   
91   if ( polygons.GetLast() == 0 ) 
92   {
93     AliCodeTimerAuto("Trivial case",1);
94     contour = new AliMUONContour(name);
95     pol = static_cast<AliMUONPolygon*>(polygons.First());
96     contour->Add(*pol);
97     contour->AssertOrientation();
98     return contour;
99   }
100   
101   TObjArray polygonVerticalEdges; // arrray of AliMUONSegment objects  
102   polygonVerticalEdges.SetOwner(kTRUE);
103   // get vertical edges of input polygons
104   GetVerticalEdges(polygons,polygonVerticalEdges);
105   
106   // sort them in ascending x order
107   // if same x, insure that left edges are before right edges
108   // within same x, order by increasing bottommost y (see AliMUONSegment::Compare method)
109   polygonVerticalEdges.Sort();
110   
111   if ( polygonVerticalEdges.GetLast()+1 < 2 ) 
112   {
113     polygons.Print();
114     AliFatal(Form("Got too few edges here for createContour %s",name));
115   }
116   
117   // Find the vertical edges of the merged contour. This is the meat of the algorithm...
118   TObjArray contourVerticalEdges;
119   contourVerticalEdges.SetOwner(kTRUE);
120   Sweep(polygonVerticalEdges,contourVerticalEdges);
121   
122   TObjArray horizontals;
123   horizontals.SetOwner(kTRUE);
124   VerticalToHorizontal(contourVerticalEdges,horizontals);
125   
126   contour = FinalizeContour(contourVerticalEdges,horizontals);
127   
128   if ( contour && name ) contour->SetName(name);
129   
130   return contour;
131 }
132
133 //_____________________________________________________________________________
134 AliMUONContour* 
135 AliMUONContourMaker::FinalizeContour(const TObjArray& verticals,
136                                      const TObjArray& horizontals) const
137 {  
138   /// For a list of vertical and horizontal edges, we build the final
139   /// contour object.
140   
141   AliCodeTimerAuto("",0);
142   
143   TObjArray all; // array of AliMUONSegment
144   TObjArray inorder; // array of AliMUONSegment
145
146   all.SetOwner(kFALSE);
147   inorder.SetOwner(kFALSE);
148     
149   for ( Int_t i = 0; i <= verticals.GetLast(); ++i ) 
150   {
151     all.Add(verticals.UncheckedAt(i));
152     all.Add(horizontals.UncheckedAt(i));
153   }
154
155   TArrayI alreadyAdded(all.GetLast()+1);
156   alreadyAdded.Reset();
157   
158   Int_t i(0);
159   
160   AliMUONContour* contour = new AliMUONContour;
161   
162   int total(0);
163   
164   while ( !all.IsEmpty() )
165   {
166     total++;
167     
168     if ( total > 1000 ) 
169     {
170       AliError("Total 1000 reached !!!!");
171       return 0x0;
172     }
173     
174     AliMUONSegment* si = static_cast<AliMUONSegment*>(all.UncheckedAt(i));
175     inorder.Add(si);
176     alreadyAdded[i] = 1;
177     const AliMUONSegment* all0 = static_cast<const AliMUONSegment*>(all.First());
178     if ( i != 0 && AliMUONSegment::AreEqual(si->EndX(),all0->StartX()) && AliMUONSegment::AreEqual(si->EndY(),all0->StartY()) )
179     {
180       Int_t n(-1);
181       
182       AliMUONPolygon polygon(inorder.GetLast()+2);
183
184       // we got a cycle. Add it to the contour
185       for ( Int_t j = 0; j <= inorder.GetLast(); ++j ) 
186       {
187         AliMUONSegment* s = static_cast<AliMUONSegment*>(inorder.UncheckedAt(j));
188         polygon.SetVertex(++n,s->StartX(),s->StartY());
189         all.Remove(s);
190       }
191       
192       all.Compress();
193
194       polygon.Close();
195       
196       contour->Add(polygon);
197       
198       if ( ! all.IsEmpty() )
199       {
200         i = 0;
201         inorder.Clear();
202         alreadyAdded.Set(all.GetLast()+1);
203         alreadyAdded.Reset();
204       }
205       continue;
206     }
207     
208     for ( Int_t j = 0; j <= all.GetLast(); ++j) 
209     {
210       if ( j != i && alreadyAdded[j] == 0 ) 
211       {        
212         const AliMUONSegment* sj = static_cast<const AliMUONSegment*>(all.UncheckedAt(j));
213         if ( AliMUONSegment::AreEqual(si->EndX(),sj->StartX()) && AliMUONSegment::AreEqual(si->EndY(),sj->StartY()))
214         {
215           i = j;
216           break;
217         }
218       }
219     }    
220   }
221   
222   contour->AssertOrientation(kTRUE);
223   return contour;
224 }
225
226
227 //_____________________________________________________________________________
228 void 
229 AliMUONContourMaker::GetVerticalEdges(const TObjArray& polygons, TObjArray& polygonVerticalEdges) const
230 {
231   /// From an array of polygons, extract the list of vertical edges.
232   /// Output array polygonVerticalEdges should be empty before calling.
233   
234   AliCodeTimerAuto("",0);
235   
236   for ( Int_t i = 0; i <= polygons.GetLast(); ++i ) 
237   {
238     const AliMUONPolygon* g = static_cast<const AliMUONPolygon*>(polygons.UncheckedAt(i));
239     for ( Int_t j = 0; j < g->NumberOfVertices()-1; ++j ) 
240     {
241       if ( AliMUONSegment::AreEqual(g->X(j),g->X(j+1)) ) // segment is vertical
242       {
243         polygonVerticalEdges.Add(new AliMUONSegment(g->X(j),g->Y(j),g->X(j+1),g->Y(j+1)));
244       }
245     }
246   }
247 }
248
249
250 //_____________________________________________________________________________
251 void
252 AliMUONContourMaker::GetYPositions(const TObjArray& polygonVerticalEdges,
253                                    TArrayD& yPositions) const
254 {
255   /// Fill the array yPositions with the different y positions found in 
256   /// polygonVerticalEdges
257   
258   AliCodeTimerAuto("",0);
259   
260   Double_t* y = new Double_t[polygonVerticalEdges.GetSize()*2];
261   Int_t n(0);
262   
263   for ( Int_t i = 0; i < polygonVerticalEdges.GetLast(); ++i ) 
264   {
265     AliMUONSegment* s = static_cast<AliMUONSegment*>(polygonVerticalEdges.UncheckedAt(i));
266     y[n] = s->StartY();
267     y[n+1] = s->EndY();
268     n += 2;
269   }
270   Int_t* ix = new Int_t[n+1];
271   
272   TMath::Sort(n,y,ix,kFALSE);
273   
274   yPositions.Set(n+1);
275   
276   Int_t u(0);
277   Double_t x(FLT_MAX);
278   
279   for ( Int_t i = 0; i < n; ++i ) 
280   {
281     if ( y[ix[i]] != x )
282     {
283       yPositions[u] = y[ix[i]];
284       x = y[ix[i]];
285       ++u;
286     }
287   }
288
289   yPositions.Set(u);
290   
291   delete[] ix;
292   delete[] y;
293   
294 }
295
296 //_____________________________________________________________________________
297 AliMUONContour* 
298 AliMUONContourMaker::MergeContour(const TObjArray& contours, const char* name) const
299 {
300   /// Merge all the polygons of all contours into a single contour
301   
302   AliCodeTimerAuto("",0);
303   
304   TObjArray polygons;
305   polygons.SetOwner(kTRUE);
306   
307   TIter next(&contours);
308   AliMUONContour* contour;
309   while ( ( contour = static_cast<AliMUONContour*>(next()) ) )
310   {
311     const TObjArray* contourPolygons = contour->Polygons();
312     TIter nextPol(contourPolygons);
313     AliMUONPolygon* pol;
314     while ( ( pol = static_cast<AliMUONPolygon*>(nextPol()) ) )
315     {
316       polygons.Add(new AliMUONPolygon(*pol));
317     }
318   }
319   
320   if ( polygons.IsEmpty() ) return 0x0;
321   
322   contour = CreateContour(polygons,name);
323   
324   return contour;
325 }
326
327 //_____________________________________________________________________________
328 void 
329 AliMUONContourMaker::SortPoints(const TObjArray& polygonVerticalEdges, 
330                                 TObjArray& sortedPoints) const
331 {
332   /// Sort the point of the vertical edges in ascending order, first on ordinate, 
333   /// then on abcissa, and put them in output vector sortedPoints.
334   /// Output array sortedPoints should be empty before calling this method.
335   
336   AliCodeTimerAuto("",0);
337   
338   for ( Int_t i = 0; i <= polygonVerticalEdges.GetLast(); ++i )
339   {
340     const AliMUONSegment* e = static_cast<const AliMUONSegment*>(polygonVerticalEdges.UncheckedAt(i));
341     sortedPoints.Add(new AliMUONPointWithRef(e->StartX(),e->StartY(),i));
342     sortedPoints.Add(new AliMUONPointWithRef(e->EndX(),e->EndY(),i));
343     // note that we keep track of the original edge, which is used
344     // later on to deduce orientation of horizontal edges.
345   }
346   
347   sortedPoints.Sort(); 
348 }
349
350 //_____________________________________________________________________________
351 void 
352 AliMUONContourMaker::Sweep(const TObjArray& polygonVerticalEdges, 
353                            TObjArray& contourVerticalEdges) const
354 {
355   /// This is the meat of the algorithm of the contour merging...
356   
357   AliCodeTimerAuto("",0);
358   
359   TArrayD yPositions;
360   GetYPositions(polygonVerticalEdges,yPositions);
361   
362   AliMUONSegmentTree segmentTree(yPositions);
363   
364   for ( Int_t i = 0; i <= polygonVerticalEdges.GetLast(); ++i )
365   {
366     const AliMUONSegment* edge = static_cast<const AliMUONSegment*>(polygonVerticalEdges.UncheckedAt(i));
367     
368     assert(edge!=0x0);
369     
370     if ( edge->IsLeftEdge() ) 
371     {
372       segmentTree.Contribution(edge->Bottom(),edge->Top());
373       segmentTree.InsertInterval(edge->Bottom(),edge->Top());
374     }
375     else
376     {
377       segmentTree.DeleteInterval(edge->Bottom(),edge->Top());
378       segmentTree.Contribution(edge->Bottom(),edge->Top());
379     }
380     
381     AliMUONSegment e1(*edge);
382     
383     if ( i < polygonVerticalEdges.GetLast() ) 
384     {
385       const AliMUONSegment* next = static_cast<const AliMUONSegment*>(polygonVerticalEdges.UncheckedAt(i+1));
386       e1 = *next;
387     }
388
389     if ( ( edge->IsLeftEdge() != e1.IsLeftEdge() ) ||
390         ( !AliMUONSegment::AreEqual(edge->StartX(),e1.StartX() ) ) ||
391         ( i == polygonVerticalEdges.GetLast() ) )
392     {
393       const TObjArray& stack = segmentTree.Stack();
394       
395       double x = edge->StartX();
396       
397       for ( Int_t j = 0; j <= stack.GetLast(); ++j )
398       {
399         AliMUONSegment* sj = static_cast<AliMUONSegment*>(stack.UncheckedAt(j));
400         AliMUONSegment* s = new AliMUONSegment(x,sj->StartY(),x,sj->EndY());
401         
402         if  (s->IsAPoint()) 
403         {
404           delete s;
405           continue;
406         }
407         
408         if ( edge->IsLeftEdge() != s->IsLeftEdge() ) 
409         {
410           s->Set(x,sj->EndY(),x,sj->StartY());
411         }
412         contourVerticalEdges.Add(s);
413       }
414       segmentTree.ResetStack();
415     }
416   }
417 }
418
419 //_____________________________________________________________________________
420 void 
421 AliMUONContourMaker::VerticalToHorizontal(const TObjArray& polygonVerticalEdges,
422                                           TObjArray& horizontalEdges) const
423 {
424   /// Deduce the set of horizontal edges from the vertical edges
425   /// Output array horizontalEdges should be empty before calling this method
426   
427   AliCodeTimerAuto("",0);
428   
429   TObjArray points; // array of AliMUONPointWithRef
430   points.SetOwner(kTRUE);
431   
432   SortPoints(polygonVerticalEdges,points);
433   
434   for ( Int_t k = 0; k < (points.GetLast()+1)/2; ++k )
435   {
436     const AliMUONPointWithRef* p1 = static_cast<AliMUONPointWithRef*>(points.UncheckedAt(k*2));
437     const AliMUONPointWithRef* p2 = static_cast<AliMUONPointWithRef*>(points.UncheckedAt(k*2+1));
438     
439     const AliMUONSegment* refEdge = static_cast<const AliMUONSegment*>(polygonVerticalEdges.UncheckedAt(p1->Ref()));
440     
441     // (p1,p2) is the horizontal edge.
442     // refEdge is used to deduce the orientation of (p1,p2)
443     
444     if ( AliMUONSegment::AreEqual(p1->X(),refEdge->EndX()) && AliMUONSegment::AreEqual(p1->Y(),refEdge->EndY()) )
445 //    if ( AreEqual(p1,refEdge->End()) )
446     {
447       horizontalEdges.Add(new AliMUONSegment(p1->X(),p1->Y(),p2->X(),p2->Y()));
448     }
449     else
450     {
451       horizontalEdges.Add(new AliMUONSegment(p2->X(),p2->Y(),p1->X(),p1->Y()));
452     }
453   }
454 }
455