AliRoot Core  v5-06-15 (45dab64)
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
AliMUONContourMaker.cxx
Go to the documentation of this file.
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 
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 
50 
51 //_____________________________________________________________________________
53 {
55 }
56 
57 
58 //_____________________________________________________________________________
60 {
62 }
63 
64 //_____________________________________________________________________________
66 AliMUONContourMaker::CreateContour(const TObjArray& polygons, const char* name) const
67 {
71 
72  AliCodeTimerAuto("",0);
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  {
93  AliCodeTimerAuto("Trivial case",1);
94  contour = new AliMUONContour(name);
95  pol = static_cast<AliMUONPolygon*>(polygons.First());
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  {
113  polygons.Print();
114  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  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 //_____________________________________________________________________________
136  const TObjArray& horizontals) const
137 {
140 
141  AliCodeTimerAuto("",0);
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  }
154 
155  TArrayI alreadyAdded(all.GetLast()+1);
156  alreadyAdded.Reset();
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);
176  alreadyAdded[i] = 1;
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();
202  alreadyAdded.Set(all.GetLast()+1);
203  alreadyAdded.Reset();
204  }
205  continue;
206  }
207 
208  for ( Int_t j = 0; j <= all.GetLast(); ++j)
209  {
210  if ( j != i && alreadyAdded[j] == 0 )
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 {
233 
234  AliCodeTimerAuto("",0);
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 {
257 
258  AliCodeTimerAuto("",0);
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 //_____________________________________________________________________________
298 AliMUONContourMaker::MergeContour(const TObjArray& contours, const char* name) const
299 {
301 
302  AliCodeTimerAuto("",0);
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 {
335 
336  AliCodeTimerAuto("",0);
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 {
356 
357  AliCodeTimerAuto("",0);
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
422  TObjArray& horizontalEdges) const
423 {
426 
427  AliCodeTimerAuto("",0);
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 
Double_t EndX() const
Return the x-coordinate of our ending point.
Double_t Y(Int_t i) const
Return the y-coordinate of the i-th vertex.
const TObjArray & Stack() const
Get the stack.
#define TObjArray
A planar polygon.
static Bool_t AreEqual(double a, double b)
A TVector2 with an integer ref, and a specific Compare.
AliMUONContour * MergeContour(const TObjArray &contours, const char *name=0x0) const
void AssertOrientation(Bool_t autoCorrect=kFALSE)
void Set(Double_t xstart, Double_t ystart, Double_t xend, Double_t yend)
Bool_t IsCounterClockwiseOriented() const
Whether this polygon is oriented counter clockwise.
Double_t StartY() const
Return the y-coordinate of our starting point.
Implementation of a segment tree.
ClassImp(TPCGenInfo)
Definition: AliTPCCmpNG.C:254
Double_t StartX() const
Return the x-coordinate of our starting point.
Int_t NumberOfVertices() const
Get the number of vertices of this polygon.
Double_t X(Int_t i) const
Return the x-coordinate of the i-th vertex.
void Sweep(const TObjArray &polygonVerticalEdges, TObjArray &contourVerticalEdges) const
Bool_t IsLeftEdge() const
Whether we are a left edge.
double Bottom() const
Return our bottom y.
void Add(const AliMUONPolygon &polygon)
Double_t X() const
Return x value.
A basic line segment, used for contour making algorithm(s)
double Top() const
void GetYPositions(const TObjArray &polygonVerticalEdges, TArrayD &yPositions) const
const TObjArray * Polygons() const
Get the list of polygons we have.
void Contribution(double b, double e)
void DeleteInterval(double d, double e)
void ResetStack()
Reset the stack.
void VerticalToHorizontal(const TObjArray &verticalEdges, TObjArray &horizontalEdges) const
void SortPoints(const TObjArray &polygonVerticalEdges, TObjArray &sortedPoints) const
Creator/merger of AliMUONContour objects.
void GetVerticalEdges(const TObjArray &polygons, TObjArray &polygonVerticalEdges) const
Double_t EndY() const
Return the y-coordinate of our ending point.
2D contour
Int_t Ref() const
Return the index of the original point in some array.
AliMUONContour * CreateContour(const TObjArray &polygons, const char *name=0x0) const
Bool_t IsAPoint() const
Whether we're just a point.
void InsertInterval(double b, double e)
Double_t Y() const
Return y value.
AliMUONContour * FinalizeContour(const TObjArray &verticals, const TObjArray &horizontals) const