Coverity fix for uninitialized variables and check for returned null value
[u/mrichter/AliRoot.git] / MUON / AliMUONContourMaker.cxx
CommitLineData
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
48ClassImp(AliMUONContourMaker)
49/// \endcond
50
0b936dc0 51//_____________________________________________________________________________
52AliMUONContourMaker::AliMUONContourMaker()
53{
cddcc1f3 54/// Default constructor
0b936dc0 55}
56
cddcc1f3 57
0b936dc0 58//_____________________________________________________________________________
59AliMUONContourMaker::~AliMUONContourMaker()
60{
cddcc1f3 61/// Destructor
0b936dc0 62}
63
64//_____________________________________________________________________________
65AliMUONContour*
66AliMUONContourMaker::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//_____________________________________________________________________________
134AliMUONContour*
135AliMUONContourMaker::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//_____________________________________________________________________________
228void
229AliMUONContourMaker::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//_____________________________________________________________________________
251void
252AliMUONContourMaker::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//_____________________________________________________________________________
297AliMUONContour*
298AliMUONContourMaker::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//_____________________________________________________________________________
328void
329AliMUONContourMaker::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//_____________________________________________________________________________
351void
352AliMUONContourMaker::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//_____________________________________________________________________________
420void
421AliMUONContourMaker::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