]>
Commit | Line | Data |
---|---|---|
0b936dc0 | 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> | |
fef32488 | 45 | #include "TArrayI.h" |
0b936dc0 | 46 | |
47 | /// \cond CLASSIMP | |
48 | ClassImp(AliMUONContourMaker) | |
49 | /// \endcond | |
50 | ||
0b936dc0 | 51 | //_____________________________________________________________________________ |
52 | AliMUONContourMaker::AliMUONContourMaker() | |
53 | { | |
cddcc1f3 | 54 | /// Default constructor |
0b936dc0 | 55 | } |
56 | ||
cddcc1f3 | 57 | |
0b936dc0 | 58 | //_____________________________________________________________________________ |
59 | AliMUONContourMaker::~AliMUONContourMaker() | |
60 | { | |
cddcc1f3 | 61 | /// Destructor |
0b936dc0 | 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 | ||
99c136e1 | 72 | AliCodeTimerAuto("",0); |
0b936dc0 | 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 | { | |
dd0be8a7 | 93 | AliCodeTimerAuto("Trivial case",1); |
0b936dc0 | 94 | contour = new AliMUONContour(name); |
7da191b6 | 95 | pol = static_cast<AliMUONPolygon*>(polygons.First()); |
0b936dc0 | 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 | { | |
0b936dc0 | 113 | polygons.Print(); |
fc2293be | 114 | AliFatal(Form("Got too few edges here for createContour %s",name)); |
0b936dc0 | 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 | ||
99c136e1 | 141 | AliCodeTimerAuto("",0); |
0b936dc0 | 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 | } | |
fef32488 | 154 | |
155 | TArrayI alreadyAdded(all.GetLast()+1); | |
156 | alreadyAdded.Reset(); | |
0b936dc0 | 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); | |
fef32488 | 176 | alreadyAdded[i] = 1; |
0b936dc0 | 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(); | |
fef32488 | 202 | alreadyAdded.Set(all.GetLast()+1); |
203 | alreadyAdded.Reset(); | |
0b936dc0 | 204 | } |
205 | continue; | |
206 | } | |
207 | ||
208 | for ( Int_t j = 0; j <= all.GetLast(); ++j) | |
209 | { | |
fef32488 | 210 | if ( j != i && alreadyAdded[j] == 0 ) |
0b936dc0 | 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 | ||
99c136e1 | 234 | AliCodeTimerAuto("",0); |
0b936dc0 | 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 | ||
99c136e1 | 258 | AliCodeTimerAuto("",0); |
0b936dc0 | 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 | ||
99c136e1 | 302 | AliCodeTimerAuto("",0); |
0b936dc0 | 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 | ||
99c136e1 | 336 | AliCodeTimerAuto("",0); |
0b936dc0 | 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 | ||
99c136e1 | 357 | AliCodeTimerAuto("",0); |
0b936dc0 | 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 | ||
99c136e1 | 427 | AliCodeTimerAuto("",0); |
0b936dc0 | 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 |