MUON/AliMUONContourMaker.cxx

   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 ClassImp(AliMUONContourMaker)
  49 /// \endcond
  50
  51 //_____________________________________________________________________________
  52 AliMUONContourMaker::AliMUONContourMaker()
  53 {
  54 /// Default constructor
  55 }
  56
  57
  58 //_____________________________________________________________________________
  59 AliMUONContourMaker::~AliMUONContourMaker()
  60 {
  61 /// Destructor
  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
  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 //_____________________________________________________________________________
 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   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 {
 231   /// From an array of polygons, extract the list of vertical edges.
 232   /// Output array polygonVerticalEdges should be empty before calling.
 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 {
 255   /// Fill the array yPositions with the different y positions found in
 256   /// polygonVerticalEdges
 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 //_____________________________________________________________________________
 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   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 {
 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   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 {
 355   /// This is the meat of the algorithm of the contour merging...
 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
 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   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