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