FMD/AliFMDPolygon.cxx

   1 /**************************************************************************
   2  * Copyright(c) 2004, 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 //
  20 // Utility class to help implement shape of the FMD modules
  21 //
  22 // Latest changes by Christian Holm Christensen
  23 //
  24 //////////////////////////////////////////////////////////////////////////////
  25 #include "AliFMDPolygon.h"      // ALIFMDPOLYGON_H
  26 #include "AliLog.h"             // ALILOG_H
  27 #include "TString.h"            // ROOT_TString
  28 #include "TVector2.h"           // ROOT_TVector2
  29 #include "TCanvas.h"            // ROOT_TCanvas
  30 #include "TText.h"              // ROOT_TText
  31 #include "TGraph.h"             // ROOT_TGraph
  32 #include "TError.h"             // ROOT_TError
  33
  34 //____________________________________________________________________
  35 ClassImp(AliFMDPolygon);
  36
  37 //____________________________________________________________________
  38 AliFMDPolygon::AliFMDPolygon()
  39   : fState(kUnknown)
  40 {}
  41
  42 //____________________________________________________________________
  43 AliFMDPolygon::~AliFMDPolygon()
  44 {
  45   fVerticies.Delete();
  46 }
  47
  48 //____________________________________________________________________
  49 bool
  50 AliFMDPolygon::AddVertex(double x, double y)
  51 {
  52   // Add points in order to the polygon.
  53   TVector2* c = new TVector2(x,y);
  54   return AddVertex(c);
  55 }
  56 //____________________________________________________________________
  57 bool
  58 AliFMDPolygon::AddVertex(TVector2* c)
  59 {
  60   // Add points in order to the polygon.
  61   //
  62   // Checks if the addition of the vertex makes the alipolygon
  63   // concave, and if it does, returns false.  Note, that the check
  64   // isn't performed until at least 3 verticies have already been
  65   // added to the alipolygon (a triangle is always convex).
  66   if (!c) return false;
  67   if (fVerticies.GetEntries() >= 3) {
  68     if (!IsOnLeftHand(c, fVerticies.GetEntries()-2,
  69                       fVerticies.GetEntries()-1)) {
  70       Error("AliFMDPolygon::AddVertex",
  71             "Adding vertex (%f,%f) makes alipolygon concave",
  72             c->X(), c->Y());
  73       return false;
  74     }
  75   }
  76   fState = kUnknown;
  77   fVerticies.AddAtAndExpand(c, fVerticies.GetEntries());
  78   return true;
  79 }
  80
  81 //____________________________________________________________________
  82 const TVector2&
  83 AliFMDPolygon::GetVertex(size_t i) const
  84 {
  85   // Get one of the verticies
  86   if (i > size_t(fVerticies.GetEntries()))
  87     Fatal("AliFMDPolygon::GetVertex", "Index %d out of range [0,%d]",
  88           i, fVerticies.GetEntries());
  89   return *(static_cast<TVector2*>(fVerticies.At(i)));
  90 }
  91
  92 //____________________________________________________________________
  93 bool
  94 AliFMDPolygon::Contains(const TVector2* c) const
  95 {
  96   /* This function checks if a point is inside the polygon.  It does
  97    * that by looping over the segments of the polygon, and decides
  98    * wether the point is on the left-hand-side (LHS) of the segment.
  99    *
 100    * Suppose we had the polygon and point
 101    *
 102    *     2 x----x 1
 103    *      /      \\
 104    *    3 x   P   x 0
 105    *      \\      /
 106    *     4 x----x 5
 107    *
 108    * Then, P is on LHS of the segment 0->1, 1->2, ..., and 5->0, and
 109    * so inside the polygon.
 110    *
 111    * Suppose instead the point was like
 112    *
 113    *     2 x----x 1
 114    *      /      \\    P
 115    *    3 x       x 0
 116    *      \\      /
 117    *     4 x----x 5
 118    *
 119    * Then it would still be on the LHS of the segments 1->2, 2->3,
 120    * 3->4, 4->5, but on the right-hand-side of 5->0, and 0->1 and
 121    * hence outside the polygon.
 122    */
 123   if (!c) return kFALSE;
 124   if (fState == kUnknown) fState = (ConvexCheck() ? kConvex : kConcave);
 125   if (fState == kConcave) return false;
 126   size_t n = fVerticies.GetEntries();
 127   for (size_t i = 0; i < n; ++i)
 128     if (!IsOnLeftHand(c, i, (i + 1) % n))
 129       // If point is on the left hand side of the segment, it's
 130       // outside the polygon.
 131       return false;
 132   return true;
 133 }
 134
 135 //____________________________________________________________________
 136 bool
 137 AliFMDPolygon::Contains(double x, double y) const
 138 {
 139   TVector2 c(x,y);
 140   return Contains(&c);
 141 }
 142
 143 //____________________________________________________________________
 144 bool
 145 AliFMDPolygon::ConvexCheck() const
 146 {
 147   /*
 148    * This member function loops through the verticies, and checks if
 149    * the next-to-next vertex is in between the current vertex and the
 150    * next vertex.
 151    *
 152    * Suppose we have the polygon
 153    *
 154    *     2 x----x 1
 155    *      /      \\
 156    *    3 x       x 0
 157    *      \\      /
 158    *     4 x----x 5
 159    *
 160    * Then the vertex 2 is on the left-hand-side (LHS) of the segment
 161    * 0->1, 3 is on the LHS of 1->2, ..., and 0 is on the RHS of 4->5,
 162    * and so the polygon is convex.
 163    *
 164    * If we had a polygon like
 165    *
 166    *     2 x----x 1
 167    *        \\    \\
 168    *       3 x    x 0
 169    *        /     /
 170    *     4 x----x 5
 171    *
 172    * Then, the vertex 4 is NOT on the LHS of the segment 2->3, and so
 173    * the polygon is NOT convex.
 174    */
 175   size_t n = fVerticies.GetEntries();
 176   // A triangle is always convex.
 177   if (n <= 3) return true;
 178   for (size_t i = 0; i < n; i++) {
 179     // Get the next, and next-to-next indicies, taking care to go
 180     // around the polygon.
 181     size_t j = (i + 1) % n;
 182     size_t k = (i + 2) % n;
 183     // Check The next-to-next vertex is on the LHS of the current
 184     // vertex and the next vertex
 185     if (!IsOnLeftHand(static_cast<TVector2*>(fVerticies.At(k)), i, j)) {
 186       Error("AliFMDPolygon::ConvexCheck",
 187             "AliFMDPolygon is concave at segment %d -> %d" , i, j);
 188       return false;
 189     }
 190   }
 191   return true;
 192 }
 193
 194 //____________________________________________________________________
 195 bool
 196 AliFMDPolygon::IsOnLeftHand(const TVector2* c, size_t i1, size_t i2) const
 197 {
 198   /* Check if a point is on the left-hand-side (LHS) or
 199    * right-hand-side (RHS) of the segment defined by the two indicies.
 200    *
 201    * Suppose we have the segment and point
 202    *
 203    *     1 x
 204    *        \\    P
 205    *         x 0
 206    *
 207    * Then, we define the vectors
 208    *
 209    *   v: 0->P
 210    *   u: perpendicular to 1->0
 211    *
 212    * The dot product of u and v is >= 0, meaning that the
 213    * angle between the two vectors is in [0,pi], and so P is on the
 214    * RHS of the segment
 215    *
 216    * Suppose we had
 217    *
 218    *       1 x
 219    *    P     \\
 220    *           x 0
 221    *
 222    * And defining the vectors u,v as above.  In this case the dot
 223    * product is less than 0, meaning the angle between u,v is in
 224    * (pi,2pi], and so P is on the LHS of the segment
 225    */
 226   if (!c) return false;
 227   const TVector2& v1 = GetVertex(i1);
 228   const TVector2& v2 = GetVertex(i2);
 229   double dot = (  (c->X()  - v1.X())  * (v2.Y() - v1.Y())
 230                 - (c->Y() - v1.Y()) * (v2.X()  - v1.X()));
 231   return (dot < 0 ? true : false);
 232 }
 233
 234 //____________________________________________________________________
 235 void
 236 AliFMDPolygon::Clear(Option_t*)
 237 {
 238   fState = kUnknown;
 239   fVerticies.Delete();
 240   // fVerticies.Resize(0);
 241 }
 242
 243 //____________________________________________________________________
 244 void
 245 AliFMDPolygon::Draw(const char* option, const char* name) const
 246 {
 247   size_t n = fVerticies.GetEntries();
 248   TGraph* g = new TGraph(n+1);
 249   if (name) g->SetName(name);
 250   g->SetMarkerStyle(20);
 251   for (size_t i = 0; i < n; i++) {
 252     const TVector2& v = GetVertex(i);
 253     g->SetPoint(i, v.X(), v.Y());
 254   }
 255   const TVector2& v = GetVertex(0);
 256   g->SetPoint(n, v.X(), v.Y());
 257   g->Draw(option);
 258   TString opt(option);
 259   if (!opt.Contains("p", TString::kIgnoreCase))
 260     return;
 261   for (size_t i = 0; i < n; i++) {
 262     const TVector2& v = GetVertex(i);
 263     TText* t = new TText(v.X(), v.Y(), Form("%d", i));
 264     t->Draw();
 265   }
 266 }
 267
 268 //____________________________________________________________________
 269 //
 270 // EOf
 271 //