Line data Source code
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 12 : ClassImp(AliMUONContourMaker)
49 : /// \endcond
50 :
51 : //_____________________________________________________________________________
52 0 : AliMUONContourMaker::AliMUONContourMaker()
53 0 : {
54 : /// Default constructor
55 0 : }
56 :
57 :
58 : //_____________________________________________________________________________
59 : AliMUONContourMaker::~AliMUONContourMaker()
60 0 : {
61 : /// Destructor
62 0 : }
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 0 : AliCodeTimerAuto("",0);
73 :
74 0 : if ( polygons.IsEmpty() ) return 0x0; // protection against user error...
75 :
76 : // Sanity check : insure that all polygons are oriented counter-clockwise
77 0 : TIter next(&polygons);
78 : AliMUONPolygon* pol;
79 0 : while ( ( pol = static_cast<AliMUONPolygon*>(next()) ) )
80 : {
81 0 : if ( !pol->IsCounterClockwiseOriented() )
82 : {
83 0 : AliError(Form("Got a clockwise oriented polygon in CreateContour(%s). That's not OK !",name));
84 0 : StdoutToAliError(polygons.Print());
85 0 : return 0x0;
86 : }
87 : }
88 :
89 : AliMUONContour* contour(0x0);
90 :
91 0 : if ( polygons.GetLast() == 0 )
92 : {
93 0 : AliCodeTimerAuto("Trivial case",1);
94 0 : contour = new AliMUONContour(name);
95 0 : pol = static_cast<AliMUONPolygon*>(polygons.First());
96 0 : contour->Add(*pol);
97 0 : contour->AssertOrientation();
98 : return contour;
99 0 : }
100 :
101 0 : TObjArray polygonVerticalEdges; // arrray of AliMUONSegment objects
102 0 : polygonVerticalEdges.SetOwner(kTRUE);
103 : // get vertical edges of input polygons
104 0 : 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 0 : polygonVerticalEdges.Sort();
110 :
111 0 : if ( polygonVerticalEdges.GetLast()+1 < 2 )
112 : {
113 0 : polygons.Print();
114 0 : 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 0 : TObjArray contourVerticalEdges;
119 0 : contourVerticalEdges.SetOwner(kTRUE);
120 0 : Sweep(polygonVerticalEdges,contourVerticalEdges);
121 :
122 0 : TObjArray horizontals;
123 0 : horizontals.SetOwner(kTRUE);
124 0 : VerticalToHorizontal(contourVerticalEdges,horizontals);
125 :
126 0 : contour = FinalizeContour(contourVerticalEdges,horizontals);
127 :
128 0 : if ( contour && name ) contour->SetName(name);
129 :
130 : return contour;
131 0 : }
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 0 : AliCodeTimerAuto("",0);
142 :
143 0 : TObjArray all; // array of AliMUONSegment
144 0 : TObjArray inorder; // array of AliMUONSegment
145 :
146 0 : all.SetOwner(kFALSE);
147 0 : inorder.SetOwner(kFALSE);
148 :
149 0 : for ( Int_t i = 0; i <= verticals.GetLast(); ++i )
150 : {
151 0 : all.Add(verticals.UncheckedAt(i));
152 0 : all.Add(horizontals.UncheckedAt(i));
153 : }
154 :
155 0 : TArrayI alreadyAdded(all.GetLast()+1);
156 0 : alreadyAdded.Reset();
157 :
158 : Int_t i(0);
159 :
160 0 : AliMUONContour* contour = new AliMUONContour;
161 :
162 : int total(0);
163 :
164 0 : while ( !all.IsEmpty() )
165 : {
166 0 : total++;
167 :
168 0 : if ( total > 1000 )
169 : {
170 0 : AliError("Total 1000 reached !!!!");
171 0 : return 0x0;
172 : }
173 :
174 0 : AliMUONSegment* si = static_cast<AliMUONSegment*>(all.UncheckedAt(i));
175 0 : inorder.Add(si);
176 0 : alreadyAdded[i] = 1;
177 0 : const AliMUONSegment* all0 = static_cast<const AliMUONSegment*>(all.First());
178 0 : if ( i != 0 && AliMUONSegment::AreEqual(si->EndX(),all0->StartX()) && AliMUONSegment::AreEqual(si->EndY(),all0->StartY()) )
179 : {
180 : Int_t n(-1);
181 :
182 0 : AliMUONPolygon polygon(inorder.GetLast()+2);
183 :
184 : // we got a cycle. Add it to the contour
185 0 : for ( Int_t j = 0; j <= inorder.GetLast(); ++j )
186 : {
187 0 : AliMUONSegment* s = static_cast<AliMUONSegment*>(inorder.UncheckedAt(j));
188 0 : polygon.SetVertex(++n,s->StartX(),s->StartY());
189 0 : all.Remove(s);
190 : }
191 :
192 0 : all.Compress();
193 :
194 0 : polygon.Close();
195 :
196 0 : contour->Add(polygon);
197 :
198 0 : if ( ! all.IsEmpty() )
199 : {
200 : i = 0;
201 0 : inorder.Clear();
202 0 : alreadyAdded.Set(all.GetLast()+1);
203 0 : alreadyAdded.Reset();
204 0 : }
205 : continue;
206 0 : }
207 :
208 0 : for ( Int_t j = 0; j <= all.GetLast(); ++j)
209 : {
210 0 : if ( j != i && alreadyAdded[j] == 0 )
211 : {
212 0 : const AliMUONSegment* sj = static_cast<const AliMUONSegment*>(all.UncheckedAt(j));
213 0 : if ( AliMUONSegment::AreEqual(si->EndX(),sj->StartX()) && AliMUONSegment::AreEqual(si->EndY(),sj->StartY()))
214 : {
215 : i = j;
216 0 : break;
217 : }
218 0 : }
219 : }
220 0 : }
221 :
222 0 : contour->AssertOrientation(kTRUE);
223 0 : return contour;
224 0 : }
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 0 : AliCodeTimerAuto("",0);
235 :
236 0 : for ( Int_t i = 0; i <= polygons.GetLast(); ++i )
237 : {
238 0 : const AliMUONPolygon* g = static_cast<const AliMUONPolygon*>(polygons.UncheckedAt(i));
239 0 : for ( Int_t j = 0; j < g->NumberOfVertices()-1; ++j )
240 : {
241 0 : if ( AliMUONSegment::AreEqual(g->X(j),g->X(j+1)) ) // segment is vertical
242 : {
243 0 : polygonVerticalEdges.Add(new AliMUONSegment(g->X(j),g->Y(j),g->X(j+1),g->Y(j+1)));
244 : }
245 : }
246 : }
247 0 : }
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 0 : AliCodeTimerAuto("",0);
259 :
260 0 : Double_t* y = new Double_t[polygonVerticalEdges.GetSize()*2];
261 : Int_t n(0);
262 :
263 0 : for ( Int_t i = 0; i < polygonVerticalEdges.GetLast(); ++i )
264 : {
265 0 : AliMUONSegment* s = static_cast<AliMUONSegment*>(polygonVerticalEdges.UncheckedAt(i));
266 0 : y[n] = s->StartY();
267 0 : y[n+1] = s->EndY();
268 0 : n += 2;
269 : }
270 0 : Int_t* ix = new Int_t[n+1];
271 :
272 0 : TMath::Sort(n,y,ix,kFALSE);
273 :
274 0 : yPositions.Set(n+1);
275 :
276 : Int_t u(0);
277 : Double_t x(FLT_MAX);
278 :
279 0 : for ( Int_t i = 0; i < n; ++i )
280 : {
281 0 : if ( y[ix[i]] != x )
282 : {
283 0 : yPositions[u] = y[ix[i]];
284 0 : x = y[ix[i]];
285 0 : ++u;
286 0 : }
287 : }
288 :
289 0 : yPositions.Set(u);
290 :
291 0 : delete[] ix;
292 0 : delete[] y;
293 :
294 0 : }
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 0 : AliCodeTimerAuto("",0);
303 :
304 0 : TObjArray polygons;
305 0 : polygons.SetOwner(kTRUE);
306 :
307 0 : TIter next(&contours);
308 : AliMUONContour* contour;
309 0 : while ( ( contour = static_cast<AliMUONContour*>(next()) ) )
310 : {
311 0 : const TObjArray* contourPolygons = contour->Polygons();
312 0 : TIter nextPol(contourPolygons);
313 : AliMUONPolygon* pol;
314 0 : while ( ( pol = static_cast<AliMUONPolygon*>(nextPol()) ) )
315 : {
316 0 : polygons.Add(new AliMUONPolygon(*pol));
317 : }
318 0 : }
319 :
320 0 : if ( polygons.IsEmpty() ) return 0x0;
321 :
322 0 : contour = CreateContour(polygons,name);
323 :
324 0 : return contour;
325 0 : }
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 0 : AliCodeTimerAuto("",0);
337 :
338 0 : for ( Int_t i = 0; i <= polygonVerticalEdges.GetLast(); ++i )
339 : {
340 0 : const AliMUONSegment* e = static_cast<const AliMUONSegment*>(polygonVerticalEdges.UncheckedAt(i));
341 0 : sortedPoints.Add(new AliMUONPointWithRef(e->StartX(),e->StartY(),i));
342 0 : 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 0 : sortedPoints.Sort();
348 0 : }
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 0 : AliCodeTimerAuto("",0);
358 :
359 0 : TArrayD yPositions;
360 0 : GetYPositions(polygonVerticalEdges,yPositions);
361 :
362 0 : AliMUONSegmentTree segmentTree(yPositions);
363 :
364 0 : for ( Int_t i = 0; i <= polygonVerticalEdges.GetLast(); ++i )
365 : {
366 0 : const AliMUONSegment* edge = static_cast<const AliMUONSegment*>(polygonVerticalEdges.UncheckedAt(i));
367 :
368 0 : assert(edge!=0x0);
369 :
370 0 : if ( edge->IsLeftEdge() )
371 : {
372 0 : segmentTree.Contribution(edge->Bottom(),edge->Top());
373 0 : segmentTree.InsertInterval(edge->Bottom(),edge->Top());
374 : }
375 : else
376 : {
377 0 : segmentTree.DeleteInterval(edge->Bottom(),edge->Top());
378 0 : segmentTree.Contribution(edge->Bottom(),edge->Top());
379 : }
380 :
381 0 : AliMUONSegment e1(*edge);
382 :
383 0 : if ( i < polygonVerticalEdges.GetLast() )
384 : {
385 0 : const AliMUONSegment* next = static_cast<const AliMUONSegment*>(polygonVerticalEdges.UncheckedAt(i+1));
386 0 : e1 = *next;
387 0 : }
388 :
389 0 : if ( ( edge->IsLeftEdge() != e1.IsLeftEdge() ) ||
390 0 : ( !AliMUONSegment::AreEqual(edge->StartX(),e1.StartX() ) ) ||
391 0 : ( i == polygonVerticalEdges.GetLast() ) )
392 : {
393 0 : const TObjArray& stack = segmentTree.Stack();
394 :
395 0 : double x = edge->StartX();
396 :
397 0 : for ( Int_t j = 0; j <= stack.GetLast(); ++j )
398 : {
399 0 : AliMUONSegment* sj = static_cast<AliMUONSegment*>(stack.UncheckedAt(j));
400 0 : AliMUONSegment* s = new AliMUONSegment(x,sj->StartY(),x,sj->EndY());
401 :
402 0 : if (s->IsAPoint())
403 : {
404 0 : delete s;
405 0 : continue;
406 : }
407 :
408 0 : if ( edge->IsLeftEdge() != s->IsLeftEdge() )
409 : {
410 0 : s->Set(x,sj->EndY(),x,sj->StartY());
411 : }
412 0 : contourVerticalEdges.Add(s);
413 0 : }
414 0 : segmentTree.ResetStack();
415 0 : }
416 0 : }
417 0 : }
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 0 : AliCodeTimerAuto("",0);
428 :
429 0 : TObjArray points; // array of AliMUONPointWithRef
430 0 : points.SetOwner(kTRUE);
431 :
432 0 : SortPoints(polygonVerticalEdges,points);
433 :
434 0 : for ( Int_t k = 0; k < (points.GetLast()+1)/2; ++k )
435 : {
436 0 : const AliMUONPointWithRef* p1 = static_cast<AliMUONPointWithRef*>(points.UncheckedAt(k*2));
437 0 : const AliMUONPointWithRef* p2 = static_cast<AliMUONPointWithRef*>(points.UncheckedAt(k*2+1));
438 :
439 0 : 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 0 : if ( AliMUONSegment::AreEqual(p1->X(),refEdge->EndX()) && AliMUONSegment::AreEqual(p1->Y(),refEdge->EndY()) )
445 : // if ( AreEqual(p1,refEdge->End()) )
446 : {
447 0 : horizontalEdges.Add(new AliMUONSegment(p1->X(),p1->Y(),p2->X(),p2->Y()));
448 : }
449 : else
450 : {
451 0 : horizontalEdges.Add(new AliMUONSegment(p2->X(),p2->Y(),p1->X(),p1->Y()));
452 : }
453 : }
454 0 : }
455 :
|
