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"
47 ClassImp(AliMUONContourMaker)
52 void PrintSegments(const TObjArray& array)
57 while ( ( s = static_cast<AliMUONSegment*>(next()) ) )
59 cout << Form("i=%d %s",i,s->AsString()) << endl;
65 //_____________________________________________________________________________
66 AliMUONContourMaker::AliMUONContourMaker()
68 /// Default constructor
72 //_____________________________________________________________________________
73 AliMUONContourMaker::~AliMUONContourMaker()
78 //_____________________________________________________________________________
80 AliMUONContourMaker::CreateContour(const TObjArray& polygons, const char* name) const
82 /// Create the contour of the polygon array
83 /// and get back the intermediate verticals and horizontal segments
84 /// both arrays are arrays of AliMUONSegment objects.
88 if ( polygons.IsEmpty() ) return 0x0; // protection against user error...
90 // Sanity check : insure that all polygons are oriented counter-clockwise
91 TIter next(&polygons);
93 while ( ( pol = static_cast<AliMUONPolygon*>(next()) ) )
95 if ( !pol->IsCounterClockwiseOriented() )
97 AliError(Form("Got a clockwise oriented polygon in CreateContour(%s). That's not OK !",name));
98 StdoutToAliError(polygons.Print());
103 AliMUONContour* contour(0x0);
105 if ( polygons.GetLast() == 0 )
107 AliCodeTimerAuto("Trivial case");
108 contour = new AliMUONContour(name);
109 pol = static_cast<AliMUONPolygon*>(polygons.First());
111 contour->AssertOrientation();
115 TObjArray polygonVerticalEdges; // arrray of AliMUONSegment objects
116 polygonVerticalEdges.SetOwner(kTRUE);
117 // get vertical edges of input polygons
118 GetVerticalEdges(polygons,polygonVerticalEdges);
120 // sort them in ascending x order
121 // if same x, insure that left edges are before right edges
122 // within same x, order by increasing bottommost y (see AliMUONSegment::Compare method)
123 polygonVerticalEdges.Sort();
125 if ( polygonVerticalEdges.GetLast()+1 < 2 )
127 AliError(Form("Got too few edges here for createContour %s",name));
133 // Find the vertical edges of the merged contour. This is the meat of the algorithm...
134 TObjArray contourVerticalEdges;
135 contourVerticalEdges.SetOwner(kTRUE);
136 Sweep(polygonVerticalEdges,contourVerticalEdges);
138 TObjArray horizontals;
139 horizontals.SetOwner(kTRUE);
140 VerticalToHorizontal(contourVerticalEdges,horizontals);
142 contour = FinalizeContour(contourVerticalEdges,horizontals);
144 if ( contour && name ) contour->SetName(name);
149 //_____________________________________________________________________________
151 AliMUONContourMaker::FinalizeContour(const TObjArray& verticals,
152 const TObjArray& horizontals) const
154 /// For a list of vertical and horizontal edges, we build the final
157 AliCodeTimerAuto("");
159 TObjArray all; // array of AliMUONSegment
160 TObjArray inorder; // array of AliMUONSegment
162 all.SetOwner(kFALSE);
163 inorder.SetOwner(kFALSE);
165 for ( Int_t i = 0; i <= verticals.GetLast(); ++i )
167 all.Add(verticals.UncheckedAt(i));
168 all.Add(horizontals.UncheckedAt(i));
173 AliMUONContour* contour = new AliMUONContour;
177 while ( !all.IsEmpty() )
183 AliError("Total 1000 reached !!!!");
187 AliMUONSegment* si = static_cast<AliMUONSegment*>(all.UncheckedAt(i));
189 const AliMUONSegment* all0 = static_cast<const AliMUONSegment*>(all.First());
190 if ( i != 0 && AliMUONSegment::AreEqual(si->EndX(),all0->StartX()) && AliMUONSegment::AreEqual(si->EndY(),all0->StartY()) )
194 AliMUONPolygon polygon(inorder.GetLast()+2);
196 // we got a cycle. Add it to the contour
197 for ( Int_t j = 0; j <= inorder.GetLast(); ++j )
199 AliMUONSegment* s = static_cast<AliMUONSegment*>(inorder.UncheckedAt(j));
200 polygon.SetVertex(++n,s->StartX(),s->StartY());
208 contour->Add(polygon);
210 if ( ! all.IsEmpty() )
218 for ( Int_t j = 0; j <= all.GetLast(); ++j)
222 const AliMUONSegment* sj = static_cast<const AliMUONSegment*>(all.UncheckedAt(j));
223 if ( AliMUONSegment::AreEqual(si->EndX(),sj->StartX()) && AliMUONSegment::AreEqual(si->EndY(),sj->StartY()))
232 contour->AssertOrientation(kTRUE);
237 //_____________________________________________________________________________
239 AliMUONContourMaker::GetVerticalEdges(const TObjArray& polygons, TObjArray& polygonVerticalEdges) const
241 /// From an array of polygons, extract the list of vertical edges.
242 /// Output array polygonVerticalEdges should be empty before calling.
244 AliCodeTimerAuto("");
246 for ( Int_t i = 0; i <= polygons.GetLast(); ++i )
248 const AliMUONPolygon* g = static_cast<const AliMUONPolygon*>(polygons.UncheckedAt(i));
249 for ( Int_t j = 0; j < g->NumberOfVertices()-1; ++j )
251 if ( AliMUONSegment::AreEqual(g->X(j),g->X(j+1)) ) // segment is vertical
253 polygonVerticalEdges.Add(new AliMUONSegment(g->X(j),g->Y(j),g->X(j+1),g->Y(j+1)));
260 //_____________________________________________________________________________
262 AliMUONContourMaker::GetYPositions(const TObjArray& polygonVerticalEdges,
263 TArrayD& yPositions) const
265 /// Fill the array yPositions with the different y positions found in
266 /// polygonVerticalEdges
268 AliCodeTimerAuto("");
270 Double_t* y = new Double_t[polygonVerticalEdges.GetSize()*2];
273 for ( Int_t i = 0; i < polygonVerticalEdges.GetLast(); ++i )
275 AliMUONSegment* s = static_cast<AliMUONSegment*>(polygonVerticalEdges.UncheckedAt(i));
280 Int_t* ix = new Int_t[n+1];
282 TMath::Sort(n,y,ix,kFALSE);
289 for ( Int_t i = 0; i < n; ++i )
293 yPositions[u] = y[ix[i]];
306 //_____________________________________________________________________________
308 AliMUONContourMaker::MergeContour(const TObjArray& contours, const char* name) const
310 /// Merge all the polygons of all contours into a single contour
312 AliCodeTimerAuto("");
315 polygons.SetOwner(kTRUE);
317 TIter next(&contours);
318 AliMUONContour* contour;
319 while ( ( contour = static_cast<AliMUONContour*>(next()) ) )
321 const TObjArray* contourPolygons = contour->Polygons();
322 TIter nextPol(contourPolygons);
324 while ( ( pol = static_cast<AliMUONPolygon*>(nextPol()) ) )
326 polygons.Add(new AliMUONPolygon(*pol));
330 if ( polygons.IsEmpty() ) return 0x0;
332 contour = CreateContour(polygons,name);
337 //_____________________________________________________________________________
339 AliMUONContourMaker::SortPoints(const TObjArray& polygonVerticalEdges,
340 TObjArray& sortedPoints) const
342 /// Sort the point of the vertical edges in ascending order, first on ordinate,
343 /// then on abcissa, and put them in output vector sortedPoints.
344 /// Output array sortedPoints should be empty before calling this method.
346 AliCodeTimerAuto("");
348 for ( Int_t i = 0; i <= polygonVerticalEdges.GetLast(); ++i )
350 const AliMUONSegment* e = static_cast<const AliMUONSegment*>(polygonVerticalEdges.UncheckedAt(i));
351 sortedPoints.Add(new AliMUONPointWithRef(e->StartX(),e->StartY(),i));
352 sortedPoints.Add(new AliMUONPointWithRef(e->EndX(),e->EndY(),i));
353 // note that we keep track of the original edge, which is used
354 // later on to deduce orientation of horizontal edges.
360 //_____________________________________________________________________________
362 AliMUONContourMaker::Sweep(const TObjArray& polygonVerticalEdges,
363 TObjArray& contourVerticalEdges) const
365 /// This is the meat of the algorithm of the contour merging...
367 AliCodeTimerAuto("");
370 GetYPositions(polygonVerticalEdges,yPositions);
372 AliMUONSegmentTree segmentTree(yPositions);
374 for ( Int_t i = 0; i <= polygonVerticalEdges.GetLast(); ++i )
376 const AliMUONSegment* edge = static_cast<const AliMUONSegment*>(polygonVerticalEdges.UncheckedAt(i));
380 if ( edge->IsLeftEdge() )
382 segmentTree.Contribution(edge->Bottom(),edge->Top());
383 segmentTree.InsertInterval(edge->Bottom(),edge->Top());
387 segmentTree.DeleteInterval(edge->Bottom(),edge->Top());
388 segmentTree.Contribution(edge->Bottom(),edge->Top());
391 AliMUONSegment e1(*edge);
393 if ( i < polygonVerticalEdges.GetLast() )
395 const AliMUONSegment* next = static_cast<const AliMUONSegment*>(polygonVerticalEdges.UncheckedAt(i+1));
399 if ( ( edge->IsLeftEdge() != e1.IsLeftEdge() ) ||
400 ( !AliMUONSegment::AreEqual(edge->StartX(),e1.StartX() ) ) ||
401 ( i == polygonVerticalEdges.GetLast() ) )
403 const TObjArray& stack = segmentTree.Stack();
405 double x = edge->StartX();
407 for ( Int_t j = 0; j <= stack.GetLast(); ++j )
409 AliMUONSegment* sj = static_cast<AliMUONSegment*>(stack.UncheckedAt(j));
410 AliMUONSegment* s = new AliMUONSegment(x,sj->StartY(),x,sj->EndY());
418 if ( edge->IsLeftEdge() != s->IsLeftEdge() )
420 s->Set(x,sj->EndY(),x,sj->StartY());
422 contourVerticalEdges.Add(s);
424 segmentTree.ResetStack();
429 //_____________________________________________________________________________
431 AliMUONContourMaker::VerticalToHorizontal(const TObjArray& polygonVerticalEdges,
432 TObjArray& horizontalEdges) const
434 /// Deduce the set of horizontal edges from the vertical edges
435 /// Output array horizontalEdges should be empty before calling this method
437 AliCodeTimerAuto("");
439 TObjArray points; // array of AliMUONPointWithRef
440 points.SetOwner(kTRUE);
442 SortPoints(polygonVerticalEdges,points);
444 for ( Int_t k = 0; k < (points.GetLast()+1)/2; ++k )
446 const AliMUONPointWithRef* p1 = static_cast<AliMUONPointWithRef*>(points.UncheckedAt(k*2));
447 const AliMUONPointWithRef* p2 = static_cast<AliMUONPointWithRef*>(points.UncheckedAt(k*2+1));
449 const AliMUONSegment* refEdge = static_cast<const AliMUONSegment*>(polygonVerticalEdges.UncheckedAt(p1->Ref()));
451 // (p1,p2) is the horizontal edge.
452 // refEdge is used to deduce the orientation of (p1,p2)
454 if ( AliMUONSegment::AreEqual(p1->X(),refEdge->EndX()) && AliMUONSegment::AreEqual(p1->Y(),refEdge->EndY()) )
455 // if ( AreEqual(p1,refEdge->End()) )
457 horizontalEdges.Add(new AliMUONSegment(p1->X(),p1->Y(),p2->X(),p2->Y()));
461 horizontalEdges.Add(new AliMUONSegment(p2->X(),p2->Y(),p1->X(),p1->Y()));