[u/mrichter/AliRoot.git] / FMD / AliFMDPolygon.cxx

/**************************************************************************
 * Copyright(c) 2004, ALICE Experiment at CERN, All rights reserved. *
 *                                                                        *
 * Author: The ALICE Off-line Project.                                    *
 * Contributors are mentioned in the code where appropriate.              *
 *                                                                        *
 * Permission to use, copy, modify and distribute this software and its   *
 * documentation strictly for non-commercial purposes is hereby granted   *
 * without fee, provided that the above copyright notice appears in all   *
 * copies and that both the copyright notice and this permission notice   *
 * appear in the supporting documentation. The authors make no claims     *
 * about the suitability of this software for any purpose. It is          *
 * provided "as is" without express or implied warranty.                  *
 **************************************************************************/

/* $Id$ */

//////////////////////////////////////////////////////////////////////////////
//
// Utility class to help implement shape of the FMD modules
//
// Latest changes by Christian Holm Christensen
//
//////////////////////////////////////////////////////////////////////////////
#include "AliFMDPolygon.h"	// ALIFMDPOLYGON_H
#include "AliLog.h"		// ALILOG_H
#include "TString.h"		// ROOT_TString
#include "TVector2.h"		// ROOT_TVector2
#include "TCanvas.h"		// ROOT_TCanvas
#include "TText.h"		// ROOT_TText
#include "TGraph.h"		// ROOT_TGraph
#include "TError.h"		// ROOT_TError

//____________________________________________________________________
ClassImp(AliFMDPolygon)

//____________________________________________________________________
AliFMDPolygon::AliFMDPolygon()
  : fState(kUnknown)
{}

//____________________________________________________________________
AliFMDPolygon::~AliFMDPolygon() 
{
  fVerticies.Delete();
}

//____________________________________________________________________
bool
AliFMDPolygon::AddVertex(double x, double y) 
{
  // Add points in order to the polygon. 
  TVector2* c = new TVector2(x,y);
  return AddVertex(c);
}
//____________________________________________________________________
bool
AliFMDPolygon::AddVertex(TVector2* c) 
{
  // Add points in order to the polygon.
  //
  // Checks if the addition of the vertex makes the alipolygon
  // concave, and if it does, returns false.  Note, that the check
  // isn't performed until at least 3 verticies have already been
  // added to the alipolygon (a triangle is always convex).
  if (!c) return false;
  if (fVerticies.GetEntries() >= 3) {
    if (!IsOnLeftHand(c, fVerticies.GetEntries()-2,
		      fVerticies.GetEntries()-1)) {
      Error("AliFMDPolygon::AddVertex", 
	    "Adding vertex (%f,%f) makes alipolygon concave", 
	    c->X(), c->Y());
      return false;
    }
  }
  fState = kUnknown;
  fVerticies.AddAtAndExpand(c, fVerticies.GetEntries());
  return true;
}

//____________________________________________________________________
const TVector2&
AliFMDPolygon::GetVertex(size_t i) const
{
  // Get one of the verticies
  if (i > size_t(fVerticies.GetEntries()))
    Fatal("AliFMDPolygon::GetVertex", "Index %d out of range [0,%d]", 
	  i, fVerticies.GetEntries());
  return *(static_cast<TVector2*>(fVerticies.At(i)));
}

//____________________________________________________________________
bool
AliFMDPolygon::Contains(const TVector2* c) const
{
  /* This function checks if a point is inside the polygon.  It does
   * that by looping over the segments of the polygon, and decides
   * wether the point is on the left-hand-side (LHS) of the segment.
   * 
   * Suppose we had the polygon and point 
   *
   *     2 x----x 1
   *      /      \\
   *    3 x   P   x 0
   *      \\      /
   *     4 x----x 5
   * 
   * Then, P is on LHS of the segment 0->1, 1->2, ..., and 5->0, and
   * so inside the polygon.
   * 
   * Suppose instead the point was like
   * 
   *     2 x----x 1
   *      /      \\    P
   *    3 x       x 0
   *      \\      /
   *     4 x----x 5
   * 
   * Then it would still be on the LHS of the segments 1->2, 2->3,
   * 3->4, 4->5, but on the right-hand-side of 5->0, and 0->1 and
   * hence outside the polygon.
   */ 
  if (!c) return kFALSE;
  if (fState == kUnknown) fState = (ConvexCheck() ? kConvex : kConcave);
  if (fState == kConcave) return false;
  size_t n = fVerticies.GetEntries();
  for (size_t i = 0; i < n; ++i) 
    if (!IsOnLeftHand(c, i, (i + 1) % n))
      // If point is on the left hand side of the segment, it's
      // outside the polygon.
      return false;
  return true;
}

//____________________________________________________________________
bool
AliFMDPolygon::Contains(double x, double y) const
{
  TVector2 c(x,y);
  return Contains(&c);
}

//____________________________________________________________________
bool
AliFMDPolygon::ConvexCheck() const
{
  /* 
   * This member function loops through the verticies, and checks if
   * the next-to-next vertex is in between the current vertex and the
   * next vertex.
   * 
   * Suppose we have the polygon 
   *           
   *     2 x----x 1
   *      /      \\
   *    3 x       x 0
   *      \\      /
   *     4 x----x 5
   * 
   * Then the vertex 2 is on the left-hand-side (LHS) of the segment
   * 0->1, 3 is on the LHS of 1->2, ..., and 0 is on the RHS of 4->5,
   * and so the polygon is convex.
   * 
   * If we had a polygon like
   *
   *     2 x----x 1
   *        \\    \\
   *       3 x    x 0
   *        /     /
   *     4 x----x 5
   * 
   * Then, the vertex 4 is NOT on the LHS of the segment 2->3, and so
   * the polygon is NOT convex.
   */
  size_t n = fVerticies.GetEntries();
  // A triangle is always convex. 
  if (n <= 3) return true;
  for (size_t i = 0; i < n; i++) {
    // Get the next, and next-to-next indicies, taking care to go
    // around the polygon.
    size_t j = (i + 1) % n;
    size_t k = (i + 2) % n;
    // Check The next-to-next vertex is on the LHS of the current
    // vertex and the next vertex 
    if (!IsOnLeftHand(static_cast<TVector2*>(fVerticies.At(k)), i, j)) {
      Error("AliFMDPolygon::ConvexCheck", 
	    "AliFMDPolygon is concave at segment %d -> %d" , i, j);
      return false;
    }
  }
  return true;
}
    
//____________________________________________________________________
bool
AliFMDPolygon::IsOnLeftHand(const TVector2* c, size_t i1, size_t i2) const
{
  /* Check if a point is on the left-hand-side (LHS) or
   * right-hand-side (RHS) of the segment defined by the two indicies.
   * 
   * Suppose we have the segment and point 
   * 
   *     1 x
   *        \\    P
   *         x 0  
   *
   * Then, we define the vectors 
   *
   *   v: 0->P 
   *   u: perpendicular to 1->0 
   * 
   * The dot product of u and v is >= 0, meaning that the
   * angle between the two vectors is in [0,pi], and so P is on the
   * RHS of the segment
   *
   * Suppose we had 
   *
   *       1 x
   *    P     \\    
   *           x 0  
   *
   * And defining the vectors u,v as above.  In this case the dot
   * product is less than 0, meaning the angle between u,v is in
   * (pi,2pi], and so P is on the LHS of the segment
   */
  if (!c) return false;
  const TVector2& v1 = GetVertex(i1);
  const TVector2& v2 = GetVertex(i2);
  double dot = (  (c->X()  - v1.X())  * (v2.Y() - v1.Y()) 
		- (c->Y() - v1.Y()) * (v2.X()  - v1.X()));
  return (dot < 0 ? true : false);
}

//____________________________________________________________________
void
AliFMDPolygon::Clear(Option_t*) 
{
  fState = kUnknown;
  fVerticies.Delete();
  // fVerticies.Resize(0);
}

//____________________________________________________________________
void
AliFMDPolygon::Draw(const char* option, const char* name) const 
{
  size_t n = fVerticies.GetEntries();
  TGraph* g = new TGraph(n+1);
  if (name) g->SetName(name);
  g->SetMarkerStyle(20);
  for (size_t i = 0; i < n; i++) {
    const TVector2& v = GetVertex(i);
    g->SetPoint(i, v.X(), v.Y());
  }
  const TVector2& v = GetVertex(0);
  g->SetPoint(n, v.X(), v.Y());
  g->Draw(option);
  TString opt(option);
  if (!opt.Contains("p", TString::kIgnoreCase))
    return;
  for (size_t i = 0; i < n; i++) {
    const TVector2& v = GetVertex(i);
    TText* t = new TText(v.X(), v.Y(), Form("%d", i));
    t->Draw();
  }
}

//____________________________________________________________________
//
// EOf
//
Commit	Line	Data
4347b38f	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	//////////////////////////////////////////////////////////////////////////////
e802be3e	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
4347b38f	33
4347b38f	34	//____________________________________________________________________
925e6570	35	ClassImp(AliFMDPolygon)
4347b38f	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	//