1 /**************************************************************************
2 * Copyright(c) 1998-1999, 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 **************************************************************************/
19 /// Maker/merger of contours. Can create contour from a set polygons or
20 /// merger a set of contours into a single one.
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
26 /// Note that besides the AliMUON prefix, nothing is really MUON specific
29 /// \author Laurent Aphecetche, Subatech
32 #include "AliMUONContourMaker.h"
34 #include "AliCodeTimer.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"
48 ClassImp(AliMUONContourMaker)
51 //_____________________________________________________________________________
52 AliMUONContourMaker::AliMUONContourMaker()
54 /// Default constructor
58 //_____________________________________________________________________________
59 AliMUONContourMaker::~AliMUONContourMaker()
64 //_____________________________________________________________________________
66 AliMUONContourMaker::CreateContour(const TObjArray& polygons, const char* name) const
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.
72 AliCodeTimerAuto("",0);
74 if ( polygons.IsEmpty() ) return 0x0; // protection against user error...
76 // Sanity check : insure that all polygons are oriented counter-clockwise
77 TIter next(&polygons);
79 while ( ( pol = static_cast<AliMUONPolygon*>(next()) ) )
81 if ( !pol->IsCounterClockwiseOriented() )
83 AliError(Form("Got a clockwise oriented polygon in CreateContour(%s). That's not OK !",name));
84 StdoutToAliError(polygons.Print());
89 AliMUONContour* contour(0x0);
91 if ( polygons.GetLast() == 0 )
93 AliCodeTimerAuto("Trivial case",1);
94 contour = new AliMUONContour(name);
95 pol = static_cast<AliMUONPolygon*>(polygons.First());
97 contour->AssertOrientation();
101 TObjArray polygonVerticalEdges; // arrray of AliMUONSegment objects
102 polygonVerticalEdges.SetOwner(kTRUE);
103 // get vertical edges of input polygons
104 GetVerticalEdges(polygons,polygonVerticalEdges);
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();
111 if ( polygonVerticalEdges.GetLast()+1 < 2 )
114 AliFatal(Form("Got too few edges here for createContour %s",name));
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);
122 TObjArray horizontals;
123 horizontals.SetOwner(kTRUE);
124 VerticalToHorizontal(contourVerticalEdges,horizontals);
126 contour = FinalizeContour(contourVerticalEdges,horizontals);
128 if ( contour && name ) contour->SetName(name);
133 //_____________________________________________________________________________
135 AliMUONContourMaker::FinalizeContour(const TObjArray& verticals,
136 const TObjArray& horizontals) const
138 /// For a list of vertical and horizontal edges, we build the final
141 AliCodeTimerAuto("",0);
143 TObjArray all; // array of AliMUONSegment
144 TObjArray inorder; // array of AliMUONSegment
146 all.SetOwner(kFALSE);
147 inorder.SetOwner(kFALSE);
149 for ( Int_t i = 0; i <= verticals.GetLast(); ++i )
151 all.Add(verticals.UncheckedAt(i));
152 all.Add(horizontals.UncheckedAt(i));
155 TArrayI alreadyAdded(all.GetLast()+1);
156 alreadyAdded.Reset();
160 AliMUONContour* contour = new AliMUONContour;
164 while ( !all.IsEmpty() )
170 AliError("Total 1000 reached !!!!");
174 AliMUONSegment* si = static_cast<AliMUONSegment*>(all.UncheckedAt(i));
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()) )
182 AliMUONPolygon polygon(inorder.GetLast()+2);
184 // we got a cycle. Add it to the contour
185 for ( Int_t j = 0; j <= inorder.GetLast(); ++j )
187 AliMUONSegment* s = static_cast<AliMUONSegment*>(inorder.UncheckedAt(j));
188 polygon.SetVertex(++n,s->StartX(),s->StartY());
196 contour->Add(polygon);
198 if ( ! all.IsEmpty() )
202 alreadyAdded.Set(all.GetLast()+1);
203 alreadyAdded.Reset();
208 for ( Int_t j = 0; j <= all.GetLast(); ++j)
210 if ( j != i && alreadyAdded[j] == 0 )
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()))
222 contour->AssertOrientation(kTRUE);
227 //_____________________________________________________________________________
229 AliMUONContourMaker::GetVerticalEdges(const TObjArray& polygons, TObjArray& polygonVerticalEdges) const
231 /// From an array of polygons, extract the list of vertical edges.
232 /// Output array polygonVerticalEdges should be empty before calling.
234 AliCodeTimerAuto("",0);
236 for ( Int_t i = 0; i <= polygons.GetLast(); ++i )
238 const AliMUONPolygon* g = static_cast<const AliMUONPolygon*>(polygons.UncheckedAt(i));
239 for ( Int_t j = 0; j < g->NumberOfVertices()-1; ++j )
241 if ( AliMUONSegment::AreEqual(g->X(j),g->X(j+1)) ) // segment is vertical
243 polygonVerticalEdges.Add(new AliMUONSegment(g->X(j),g->Y(j),g->X(j+1),g->Y(j+1)));
250 //_____________________________________________________________________________
252 AliMUONContourMaker::GetYPositions(const TObjArray& polygonVerticalEdges,
253 TArrayD& yPositions) const
255 /// Fill the array yPositions with the different y positions found in
256 /// polygonVerticalEdges
258 AliCodeTimerAuto("",0);
260 Double_t* y = new Double_t[polygonVerticalEdges.GetSize()*2];
263 for ( Int_t i = 0; i < polygonVerticalEdges.GetLast(); ++i )
265 AliMUONSegment* s = static_cast<AliMUONSegment*>(polygonVerticalEdges.UncheckedAt(i));
270 Int_t* ix = new Int_t[n+1];
272 TMath::Sort(n,y,ix,kFALSE);
279 for ( Int_t i = 0; i < n; ++i )
283 yPositions[u] = y[ix[i]];
296 //_____________________________________________________________________________
298 AliMUONContourMaker::MergeContour(const TObjArray& contours, const char* name) const
300 /// Merge all the polygons of all contours into a single contour
302 AliCodeTimerAuto("",0);
305 polygons.SetOwner(kTRUE);
307 TIter next(&contours);
308 AliMUONContour* contour;
309 while ( ( contour = static_cast<AliMUONContour*>(next()) ) )
311 const TObjArray* contourPolygons = contour->Polygons();
312 TIter nextPol(contourPolygons);
314 while ( ( pol = static_cast<AliMUONPolygon*>(nextPol()) ) )
316 polygons.Add(new AliMUONPolygon(*pol));
320 if ( polygons.IsEmpty() ) return 0x0;
322 contour = CreateContour(polygons,name);
327 //_____________________________________________________________________________
329 AliMUONContourMaker::SortPoints(const TObjArray& polygonVerticalEdges,
330 TObjArray& sortedPoints) const
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.
336 AliCodeTimerAuto("",0);
338 for ( Int_t i = 0; i <= polygonVerticalEdges.GetLast(); ++i )
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.
350 //_____________________________________________________________________________
352 AliMUONContourMaker::Sweep(const TObjArray& polygonVerticalEdges,
353 TObjArray& contourVerticalEdges) const
355 /// This is the meat of the algorithm of the contour merging...
357 AliCodeTimerAuto("",0);
360 GetYPositions(polygonVerticalEdges,yPositions);
362 AliMUONSegmentTree segmentTree(yPositions);
364 for ( Int_t i = 0; i <= polygonVerticalEdges.GetLast(); ++i )
366 const AliMUONSegment* edge = static_cast<const AliMUONSegment*>(polygonVerticalEdges.UncheckedAt(i));
370 if ( edge->IsLeftEdge() )
372 segmentTree.Contribution(edge->Bottom(),edge->Top());
373 segmentTree.InsertInterval(edge->Bottom(),edge->Top());
377 segmentTree.DeleteInterval(edge->Bottom(),edge->Top());
378 segmentTree.Contribution(edge->Bottom(),edge->Top());
381 AliMUONSegment e1(*edge);
383 if ( i < polygonVerticalEdges.GetLast() )
385 const AliMUONSegment* next = static_cast<const AliMUONSegment*>(polygonVerticalEdges.UncheckedAt(i+1));
389 if ( ( edge->IsLeftEdge() != e1.IsLeftEdge() ) ||
390 ( !AliMUONSegment::AreEqual(edge->StartX(),e1.StartX() ) ) ||
391 ( i == polygonVerticalEdges.GetLast() ) )
393 const TObjArray& stack = segmentTree.Stack();
395 double x = edge->StartX();
397 for ( Int_t j = 0; j <= stack.GetLast(); ++j )
399 AliMUONSegment* sj = static_cast<AliMUONSegment*>(stack.UncheckedAt(j));
400 AliMUONSegment* s = new AliMUONSegment(x,sj->StartY(),x,sj->EndY());
408 if ( edge->IsLeftEdge() != s->IsLeftEdge() )
410 s->Set(x,sj->EndY(),x,sj->StartY());
412 contourVerticalEdges.Add(s);
414 segmentTree.ResetStack();
419 //_____________________________________________________________________________
421 AliMUONContourMaker::VerticalToHorizontal(const TObjArray& polygonVerticalEdges,
422 TObjArray& horizontalEdges) const
424 /// Deduce the set of horizontal edges from the vertical edges
425 /// Output array horizontalEdges should be empty before calling this method
427 AliCodeTimerAuto("",0);
429 TObjArray points; // array of AliMUONPointWithRef
430 points.SetOwner(kTRUE);
432 SortPoints(polygonVerticalEdges,points);
434 for ( Int_t k = 0; k < (points.GetLast()+1)/2; ++k )
436 const AliMUONPointWithRef* p1 = static_cast<AliMUONPointWithRef*>(points.UncheckedAt(k*2));
437 const AliMUONPointWithRef* p2 = static_cast<AliMUONPointWithRef*>(points.UncheckedAt(k*2+1));
439 const AliMUONSegment* refEdge = static_cast<const AliMUONSegment*>(polygonVerticalEdges.UncheckedAt(p1->Ref()));
441 // (p1,p2) is the horizontal edge.
442 // refEdge is used to deduce the orientation of (p1,p2)
444 if ( AliMUONSegment::AreEqual(p1->X(),refEdge->EndX()) && AliMUONSegment::AreEqual(p1->Y(),refEdge->EndY()) )
445 // if ( AreEqual(p1,refEdge->End()) )
447 horizontalEdges.Add(new AliMUONSegment(p1->X(),p1->Y(),p2->X(),p2->Y()));
451 horizontalEdges.Add(new AliMUONSegment(p2->X(),p2->Y(),p1->X(),p1->Y()));