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)
53 void PrintSegments(const TObjArray& array)
58 while ( ( s = static_cast<AliMUONSegment*>(next()) ) )
60 cout << Form("i=%d %s",i,s->AsString()) << endl;
66 //_____________________________________________________________________________
67 AliMUONContourMaker::AliMUONContourMaker()
69 /// Default constructor
73 //_____________________________________________________________________________
74 AliMUONContourMaker::~AliMUONContourMaker()
79 //_____________________________________________________________________________
81 AliMUONContourMaker::CreateContour(const TObjArray& polygons, const char* name) const
83 /// Create the contour of the polygon array
84 /// and get back the intermediate verticals and horizontal segments
85 /// both arrays are arrays of AliMUONSegment objects.
87 AliCodeTimerAuto("",0);
89 if ( polygons.IsEmpty() ) return 0x0; // protection against user error...
91 // Sanity check : insure that all polygons are oriented counter-clockwise
92 TIter next(&polygons);
94 while ( ( pol = static_cast<AliMUONPolygon*>(next()) ) )
96 if ( !pol->IsCounterClockwiseOriented() )
98 AliError(Form("Got a clockwise oriented polygon in CreateContour(%s). That's not OK !",name));
99 StdoutToAliError(polygons.Print());
104 AliMUONContour* contour(0x0);
106 if ( polygons.GetLast() == 0 )
108 AliCodeTimerAuto("Trivial case",1);
109 contour = new AliMUONContour(name);
110 pol = static_cast<AliMUONPolygon*>(polygons.First());
112 contour->AssertOrientation();
116 TObjArray polygonVerticalEdges; // arrray of AliMUONSegment objects
117 polygonVerticalEdges.SetOwner(kTRUE);
118 // get vertical edges of input polygons
119 GetVerticalEdges(polygons,polygonVerticalEdges);
121 // sort them in ascending x order
122 // if same x, insure that left edges are before right edges
123 // within same x, order by increasing bottommost y (see AliMUONSegment::Compare method)
124 polygonVerticalEdges.Sort();
126 if ( polygonVerticalEdges.GetLast()+1 < 2 )
128 AliError(Form("Got too few edges here for createContour %s",name));
134 // Find the vertical edges of the merged contour. This is the meat of the algorithm...
135 TObjArray contourVerticalEdges;
136 contourVerticalEdges.SetOwner(kTRUE);
137 Sweep(polygonVerticalEdges,contourVerticalEdges);
139 TObjArray horizontals;
140 horizontals.SetOwner(kTRUE);
141 VerticalToHorizontal(contourVerticalEdges,horizontals);
143 contour = FinalizeContour(contourVerticalEdges,horizontals);
145 if ( contour && name ) contour->SetName(name);
150 //_____________________________________________________________________________
152 AliMUONContourMaker::FinalizeContour(const TObjArray& verticals,
153 const TObjArray& horizontals) const
155 /// For a list of vertical and horizontal edges, we build the final
158 AliCodeTimerAuto("",0);
160 TObjArray all; // array of AliMUONSegment
161 TObjArray inorder; // array of AliMUONSegment
163 all.SetOwner(kFALSE);
164 inorder.SetOwner(kFALSE);
166 for ( Int_t i = 0; i <= verticals.GetLast(); ++i )
168 all.Add(verticals.UncheckedAt(i));
169 all.Add(horizontals.UncheckedAt(i));
172 TArrayI alreadyAdded(all.GetLast()+1);
173 alreadyAdded.Reset();
177 AliMUONContour* contour = new AliMUONContour;
181 while ( !all.IsEmpty() )
187 AliError("Total 1000 reached !!!!");
191 AliMUONSegment* si = static_cast<AliMUONSegment*>(all.UncheckedAt(i));
194 const AliMUONSegment* all0 = static_cast<const AliMUONSegment*>(all.First());
195 if ( i != 0 && AliMUONSegment::AreEqual(si->EndX(),all0->StartX()) && AliMUONSegment::AreEqual(si->EndY(),all0->StartY()) )
199 AliMUONPolygon polygon(inorder.GetLast()+2);
201 // we got a cycle. Add it to the contour
202 for ( Int_t j = 0; j <= inorder.GetLast(); ++j )
204 AliMUONSegment* s = static_cast<AliMUONSegment*>(inorder.UncheckedAt(j));
205 polygon.SetVertex(++n,s->StartX(),s->StartY());
213 contour->Add(polygon);
215 if ( ! all.IsEmpty() )
219 alreadyAdded.Set(all.GetLast()+1);
220 alreadyAdded.Reset();
225 for ( Int_t j = 0; j <= all.GetLast(); ++j)
227 if ( j != i && alreadyAdded[j] == 0 )
229 const AliMUONSegment* sj = static_cast<const AliMUONSegment*>(all.UncheckedAt(j));
230 if ( AliMUONSegment::AreEqual(si->EndX(),sj->StartX()) && AliMUONSegment::AreEqual(si->EndY(),sj->StartY()))
239 contour->AssertOrientation(kTRUE);
244 //_____________________________________________________________________________
246 AliMUONContourMaker::GetVerticalEdges(const TObjArray& polygons, TObjArray& polygonVerticalEdges) const
248 /// From an array of polygons, extract the list of vertical edges.
249 /// Output array polygonVerticalEdges should be empty before calling.
251 AliCodeTimerAuto("",0);
253 for ( Int_t i = 0; i <= polygons.GetLast(); ++i )
255 const AliMUONPolygon* g = static_cast<const AliMUONPolygon*>(polygons.UncheckedAt(i));
256 for ( Int_t j = 0; j < g->NumberOfVertices()-1; ++j )
258 if ( AliMUONSegment::AreEqual(g->X(j),g->X(j+1)) ) // segment is vertical
260 polygonVerticalEdges.Add(new AliMUONSegment(g->X(j),g->Y(j),g->X(j+1),g->Y(j+1)));
267 //_____________________________________________________________________________
269 AliMUONContourMaker::GetYPositions(const TObjArray& polygonVerticalEdges,
270 TArrayD& yPositions) const
272 /// Fill the array yPositions with the different y positions found in
273 /// polygonVerticalEdges
275 AliCodeTimerAuto("",0);
277 Double_t* y = new Double_t[polygonVerticalEdges.GetSize()*2];
280 for ( Int_t i = 0; i < polygonVerticalEdges.GetLast(); ++i )
282 AliMUONSegment* s = static_cast<AliMUONSegment*>(polygonVerticalEdges.UncheckedAt(i));
287 Int_t* ix = new Int_t[n+1];
289 TMath::Sort(n,y,ix,kFALSE);
296 for ( Int_t i = 0; i < n; ++i )
300 yPositions[u] = y[ix[i]];
313 //_____________________________________________________________________________
315 AliMUONContourMaker::MergeContour(const TObjArray& contours, const char* name) const
317 /// Merge all the polygons of all contours into a single contour
319 AliCodeTimerAuto("",0);
322 polygons.SetOwner(kTRUE);
324 TIter next(&contours);
325 AliMUONContour* contour;
326 while ( ( contour = static_cast<AliMUONContour*>(next()) ) )
328 const TObjArray* contourPolygons = contour->Polygons();
329 TIter nextPol(contourPolygons);
331 while ( ( pol = static_cast<AliMUONPolygon*>(nextPol()) ) )
333 polygons.Add(new AliMUONPolygon(*pol));
337 if ( polygons.IsEmpty() ) return 0x0;
339 contour = CreateContour(polygons,name);
344 //_____________________________________________________________________________
346 AliMUONContourMaker::SortPoints(const TObjArray& polygonVerticalEdges,
347 TObjArray& sortedPoints) const
349 /// Sort the point of the vertical edges in ascending order, first on ordinate,
350 /// then on abcissa, and put them in output vector sortedPoints.
351 /// Output array sortedPoints should be empty before calling this method.
353 AliCodeTimerAuto("",0);
355 for ( Int_t i = 0; i <= polygonVerticalEdges.GetLast(); ++i )
357 const AliMUONSegment* e = static_cast<const AliMUONSegment*>(polygonVerticalEdges.UncheckedAt(i));
358 sortedPoints.Add(new AliMUONPointWithRef(e->StartX(),e->StartY(),i));
359 sortedPoints.Add(new AliMUONPointWithRef(e->EndX(),e->EndY(),i));
360 // note that we keep track of the original edge, which is used
361 // later on to deduce orientation of horizontal edges.
367 //_____________________________________________________________________________
369 AliMUONContourMaker::Sweep(const TObjArray& polygonVerticalEdges,
370 TObjArray& contourVerticalEdges) const
372 /// This is the meat of the algorithm of the contour merging...
374 AliCodeTimerAuto("",0);
377 GetYPositions(polygonVerticalEdges,yPositions);
379 AliMUONSegmentTree segmentTree(yPositions);
381 for ( Int_t i = 0; i <= polygonVerticalEdges.GetLast(); ++i )
383 const AliMUONSegment* edge = static_cast<const AliMUONSegment*>(polygonVerticalEdges.UncheckedAt(i));
387 if ( edge->IsLeftEdge() )
389 segmentTree.Contribution(edge->Bottom(),edge->Top());
390 segmentTree.InsertInterval(edge->Bottom(),edge->Top());
394 segmentTree.DeleteInterval(edge->Bottom(),edge->Top());
395 segmentTree.Contribution(edge->Bottom(),edge->Top());
398 AliMUONSegment e1(*edge);
400 if ( i < polygonVerticalEdges.GetLast() )
402 const AliMUONSegment* next = static_cast<const AliMUONSegment*>(polygonVerticalEdges.UncheckedAt(i+1));
406 if ( ( edge->IsLeftEdge() != e1.IsLeftEdge() ) ||
407 ( !AliMUONSegment::AreEqual(edge->StartX(),e1.StartX() ) ) ||
408 ( i == polygonVerticalEdges.GetLast() ) )
410 const TObjArray& stack = segmentTree.Stack();
412 double x = edge->StartX();
414 for ( Int_t j = 0; j <= stack.GetLast(); ++j )
416 AliMUONSegment* sj = static_cast<AliMUONSegment*>(stack.UncheckedAt(j));
417 AliMUONSegment* s = new AliMUONSegment(x,sj->StartY(),x,sj->EndY());
425 if ( edge->IsLeftEdge() != s->IsLeftEdge() )
427 s->Set(x,sj->EndY(),x,sj->StartY());
429 contourVerticalEdges.Add(s);
431 segmentTree.ResetStack();
436 //_____________________________________________________________________________
438 AliMUONContourMaker::VerticalToHorizontal(const TObjArray& polygonVerticalEdges,
439 TObjArray& horizontalEdges) const
441 /// Deduce the set of horizontal edges from the vertical edges
442 /// Output array horizontalEdges should be empty before calling this method
444 AliCodeTimerAuto("",0);
446 TObjArray points; // array of AliMUONPointWithRef
447 points.SetOwner(kTRUE);
449 SortPoints(polygonVerticalEdges,points);
451 for ( Int_t k = 0; k < (points.GetLast()+1)/2; ++k )
453 const AliMUONPointWithRef* p1 = static_cast<AliMUONPointWithRef*>(points.UncheckedAt(k*2));
454 const AliMUONPointWithRef* p2 = static_cast<AliMUONPointWithRef*>(points.UncheckedAt(k*2+1));
456 const AliMUONSegment* refEdge = static_cast<const AliMUONSegment*>(polygonVerticalEdges.UncheckedAt(p1->Ref()));
458 // (p1,p2) is the horizontal edge.
459 // refEdge is used to deduce the orientation of (p1,p2)
461 if ( AliMUONSegment::AreEqual(p1->X(),refEdge->EndX()) && AliMUONSegment::AreEqual(p1->Y(),refEdge->EndY()) )
462 // if ( AreEqual(p1,refEdge->End()) )
464 horizontalEdges.Add(new AliMUONSegment(p1->X(),p1->Y(),p2->X(),p2->Y()));
468 horizontalEdges.Add(new AliMUONSegment(p2->X(),p2->Y(),p1->X(),p1->Y()));