GLC_lib  2.5.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
glc_geomtools.cpp
Go to the documentation of this file.
1 /****************************************************************************
2 
3  This file is part of the GLC-lib library.
4  Copyright (C) 2005-2008 Laurent Ribon (laumaya@users.sourceforge.net)
5  http://glc-lib.sourceforge.net
6 
7  GLC-lib is free software; you can redistribute it and/or modify
8  it under the terms of the GNU Lesser General Public License as published by
9  the Free Software Foundation; either version 3 of the License, or
10  (at your option) any later version.
11 
12  GLC-lib is distributed in the hope that it will be useful,
13  but WITHOUT ANY WARRANTY; without even the implied warranty of
14  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15  GNU Lesser General Public License for more details.
16 
17  You should have received a copy of the GNU Lesser General Public License
18  along with GLC-lib; if not, write to the Free Software
19  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
20 
21 *****************************************************************************/
22 
24 
25 #include "glc_geomtools.h"
26 #include "glc_matrix4x4.h"
27 
28 #include <QtGlobal>
29 
30 
32 
34 //Tools Functions
36 
37 // Test if a polygon is convex
38 bool glc::polygon2DIsConvex(const QList<GLC_Point2d>& vertices)
39 {
40  bool isConvex= true;
41  const int size= vertices.size();
42  if (vertices.size() > 3)
43  {
44  GLC_Point2d s0(vertices.at(0));
45  GLC_Point2d s1(vertices.at(1));
46  GLC_Point2d s2(vertices.at(2));
47  const bool openAngle= ((s1.x() - s0.x()) * (s2.y() - s0.y()) - (s2.x() - s0.x()) * (s1.y() - s0.y())) < 0.0;
48 
49  int i= 3;
50  while ((i < size) && isConvex)
51  {
52  s0= s1;
53  s1= s2;
54  s2= vertices.at(i);
55  isConvex= openAngle == (((s1.x() - s0.x()) * (s2.y() - s0.y()) - (s2.x() - s0.x()) * (s1.y() - s0.y())) < 0.0);
56  ++i;
57  }
58  }
59 
60  return isConvex;
61 }
62 
63 bool glc::polygonIsConvex(QList<GLuint>* pIndexList, const QList<float>& bulkList)
64 {
65  bool isConvex= true;
66  const int size= pIndexList->size();
67  GLuint currentIndex;
68  GLC_Vector3d v0;
69  GLC_Vector3d v1;
70  int i= 0;
71  while ((i < size) && isConvex)
72  {
73  currentIndex= pIndexList->at(i);
74  v0.setVect(bulkList.at(currentIndex * 3), bulkList.at(currentIndex * 3 + 1), bulkList.at(currentIndex * 3 + 2));
75  currentIndex= pIndexList->at((i + 1) % size);
76  v1.setVect(bulkList.at(currentIndex * 3), bulkList.at(currentIndex * 3 + 1), bulkList.at(currentIndex * 3 + 2));
77  isConvex= (v0.angleWithVect(v1) < glc::PI);
78  ++i;
79  }
80  return isConvex;
81 }
82 // find intersection between two 2D segments
83 QVector<GLC_Point2d> glc::findIntersection(const GLC_Point2d& s1p1, const GLC_Point2d& s1p2, const GLC_Point2d& s2p1, const GLC_Point2d& s2p2)
84 {
85  const GLC_Vector2d D0= s1p2 - s1p1;
86  const GLC_Vector2d D1= s2p2 - s2p1;
87  // The QVector of result points
88  QVector<GLC_Point2d> result;
89 
90  const GLC_Vector2d E(s2p1 - s1p1);
91  double kross= D0 ^ D1;
92  double sqrKross= kross * kross;
93  const double sqrLen0= D0.x() * D0.x() + D0.y() * D0.y();
94  const double sqrLen1= D1.x() * D1.x() + D1.y() * D1.y();
95  // Test if the line are nor parallel
96  if (sqrKross > (EPSILON * sqrLen0 * sqrLen1))
97  {
98  const double s= (E ^ D1) / kross;
99  if ((s < 0.0) || (s > 1.0))
100  {
101  // Intersection of lines is not a point on segment s1p1 + s * DO
102  return result; // Return empty QVector
103  }
104  const double t= (E ^ D0) / kross;
105 
106  if ((t < 0.0) || (t > 1.0))
107  {
108  // Intersection of lines is not a point on segment s2p1 + t * D1
109  return result; // Return empty QVector
110  }
111 
112  // Intersection of lines is a point on each segment
113  result << (s1p1 + (D0 * s));
114  return result; // Return a QVector of One Point
115  }
116 
117  // Lines of the segments are parallel
118  const double sqrLenE= E.x() * E.x() + E.y() * E.y();
119  kross= E ^ D0;
120  sqrKross= kross * kross;
121  if (sqrKross > (EPSILON * sqrLen0 * sqrLenE))
122  {
123  // Lines of the segments are different
124  return result; // Return empty QVector
125  }
126 
127  // Lines of the segments are the same. Need to test for overlap of segments.
128  const double s0= (D0 * E) / sqrLen0;
129  const double s1= (D0 * D1) / sqrLen0;
130  const double sMin= qMin(s0, s1);
131  const double sMax= qMax(s0, s1);
132  QVector<double> overlaps= findIntersection(0.0, 1.0, sMin, sMax);
133  const int iMax= overlaps.size();
134  for (int i= 0; i < iMax; ++i)
135  {
136  result.append(s1p1 + (D0 * overlaps[i]));
137  }
138  return result;
139 }
140 
141 // return true if there is an intersection between 2 segments
142 bool glc::isIntersected(const GLC_Point2d& s1p1, const GLC_Point2d& s1p2, const GLC_Point2d& s2p1, const GLC_Point2d& s2p2)
143 {
144  const GLC_Vector2d D0= s1p2 - s1p1;
145  const GLC_Vector2d D1= s2p2 - s2p1;
146 
147  const GLC_Vector2d E(s2p1 - s1p1);
148  double kross= D0 ^ D1;
149  double sqrKross= kross * kross;
150  const double sqrLen0= D0.x() * D0.x() + D0.y() * D0.y();
151  const double sqrLen1= D1.x() * D1.x() + D1.y() * D1.y();
152  // Test if the line are nor parallel
153  if (sqrKross > (EPSILON * sqrLen0 * sqrLen1))
154  {
155  const double s= (E ^ D1) / kross;
156  if ((s < 0.0) || (s > 1.0))
157  {
158  // Intersection of lines is not a point on segment s1p1 + s * DO
159  return false;
160  }
161  const double t= (E ^ D0) / kross;
162 
163  if ((t < 0.0) || (t > 1.0))
164  {
165  // Intersection of lines is not a point on segment s2p1 + t * D1
166  return false;
167  }
168 
169  // Intersection of lines is a point on each segment
170  return true;
171  }
172 
173  // Lines of the segments are parallel
174  const double sqrLenE= E.x() * E.x() + E.y() * E.y();
175  kross= E ^ D0;
176  sqrKross= kross * kross;
177  if (sqrKross > (EPSILON * sqrLen0 * sqrLenE))
178  {
179  // Lines of the segments are different
180  return false;
181  }
182 
183  // Lines of the segments are the same. Need to test for overlap of segments.
184  const double s0= (D0 * E) / sqrLen0;
185  const double s1= s0 + (D0 * D1) / sqrLen0;
186  const double sMin= qMin(s0, s1);
187  const double sMax= qMax(s0, s1);
188  if (findIntersection(0.0, 1.0, sMin, sMax).size() == 0) return false; else return true;
189 
190 }
191 
192 // return true if there is an intersection between a ray and a segment
193 bool glc::isIntersectedRaySegment(const GLC_Point2d& s1p1, const GLC_Vector2d& s1p2, const GLC_Point2d& s2p1, const GLC_Point2d& s2p2)
194 {
195  const GLC_Vector2d D0= s1p2 - s1p1;
196  const GLC_Vector2d D1= s2p2 - s2p1;
197 
198  const GLC_Vector2d E(s2p1 - s1p1);
199  double kross= D0 ^ D1;
200  double sqrKross= kross * kross;
201  const double sqrLen0= D0.x() * D0.x() + D0.y() * D0.y();
202  const double sqrLen1= D1.x() * D1.x() + D1.y() * D1.y();
203  // Test if the line are nor parallel
204  if (sqrKross > (EPSILON * sqrLen0 * sqrLen1))
205  {
206  const double s= (E ^ D1) / kross;
207  if ((s < 0.0))
208  {
209  // Intersection of lines is not a point on segment s1p1 + s * DO
210  return false;
211  }
212  const double t= (E ^ D0) / kross;
213 
214  if ((t < 0.0) || (t > 1.0))
215  {
216  // Intersection of lines is not a point on segment s2p1 + t * D1
217  return false;
218  }
219 
220  // Intersection of lines is a point on each segment
221  return true;
222  }
223 
224  // Lines of the segments are parallel
225  const double sqrLenE= E.x() * E.x() + E.y() * E.y();
226  kross= E ^ D0;
227  sqrKross= kross * kross;
228  if (sqrKross > (EPSILON * sqrLen0 * sqrLenE))
229  {
230  // Lines of are different
231  return false;
232  }
233  else return true;
234 
235 }
236 
237 // find intersection of two intervals [u0, u1] and [v0, v1]
238 QVector<double> glc::findIntersection(const double& u0, const double& u1, const double& v0, const double& v1)
239 {
240  //Q_ASSERT((u0 < u1) and (v0 < v1));
241  QVector<double> result;
242  if (u1 < v0 || u0 > v1) return result; // Return empty QVector
243 
244  if (u1 > v0)
245  {
246  if (u0 < v1)
247  {
248  if (u0 < v0) result.append(v0); else result.append(u0);
249  if (u1 > v1) result.append(v1); else result.append(u1);
250  return result;
251  }
252  else // u0 == v1
253  {
254  result.append(u0);
255  return result;
256  }
257  }
258  else // u1 == v0
259  {
260  result.append(u1);
261  return result;
262  }
263 }
264 
265 // return true if the segment is in polygon cone
266 bool glc::segmentInCone(const GLC_Point2d& V0, const GLC_Point2d& V1, const GLC_Point2d& VM, const GLC_Point2d& VP)
267 {
268  // assert: VM, V0, VP are not collinear
269  const GLC_Vector2d diff(V1 - V0);
270  const GLC_Vector2d edgeL(VM - V0);
271  const GLC_Vector2d edgeR(VP - V0);
272  if ((edgeR ^ edgeL) > 0)
273  {
274  // Vertex is convex
275  return (((diff ^ edgeR) < 0.0) && ((diff ^ edgeL) > 0.0));
276  }
277  else
278  {
279  // Vertex is reflex
280  return (((diff ^ edgeR) < 0.0) || ((diff ^ edgeL) > 0.0));
281  }
282 }
283 
284 // Return true if the segment is a polygon diagonal
285 bool glc::isDiagonal(const QList<GLC_Point2d>& polygon, const int i0, const int i1)
286 {
287  const int size= polygon.size();
288  int iM= (i0 - 1) % size;
289  if (iM < 0) iM= size - 1;
290  int iP= (i0 + 1) % size;
291 
292  if (!segmentInCone(polygon[i0], polygon[i1], polygon[iM], polygon[iP]))
293  {
294  return false;
295  }
296 
297  int j0= 0;
298  int j1= size - 1;
299  // test segment <polygon[i0], polygon[i1]> to see if it is a diagonal
300  while (j0 < size)
301  {
302  if (j0 != i0 && j0 != i1 && j1 != i0 && j1 != i1)
303  {
304  if (isIntersected(polygon[i0], polygon[i1], polygon[j0], polygon[j1]))
305  return false;
306  }
307 
308  j1= j0;
309  ++j0;
310  }
311 
312  return true;
313 }
314 
315 // Triangulate a polygon
316 void glc::triangulate(QList<GLC_Point2d>& polygon, QList<int>& index, QList<int>& tList)
317 {
318  const int size= polygon.size();
319  if (size == 3)
320  {
321  tList << index[0] << index[1] << index[2];
322  return;
323  }
324  int i0= 0;
325  int i1= 1;
326  int i2= 2;
327  while(i0 < size)
328  {
329  if (isDiagonal(polygon, i0, i2))
330  {
331  // Add the triangle before removing the ear.
332  tList << index[i0] << index[i1] << index[i2];
333  // Remove the ear from polygon and index lists
334  polygon.removeAt(i1);
335  index.removeAt(i1);
336  // recurse to the new polygon
337  triangulate(polygon, index, tList);
338  return;
339  }
340  ++i0;
341  i1= (i1 + 1) % size;
342  i2= (i2 + 1) % size;
343  }
344 }
345 
346 // return true if the polygon is couterclockwise ordered
347 bool glc::isCounterclockwiseOrdered(const QList<GLC_Point2d>& polygon)
348 {
349  const int size= polygon.size();
350  int j0= 0;
351  int j1= size - 1;
352  // test segment <polygon[i0], polygon[i1]> to see if it is a diagonal
353  while (j0 < size)
354  {
355  GLC_Vector2d perp((polygon[j0] - polygon[j1]).perp());
356  int j2= 0;
357  int j3= size - 1;
358  bool isIntersect= false;
359  // Application of perp vector
360  GLC_Point2d moy((polygon[j0] + polygon[j1]) * 0.5);
361  while (j2 < size && !isIntersect)
362  {
363  if(j2 != j0 && j3 != j1)
364  {
365  if (isIntersectedRaySegment(moy, (perp + moy), polygon[j2], polygon[j3]))
366  isIntersect= true;
367  }
368  j3= j2;
369  ++j2;
370  }
371  if(!isIntersect) return false;
372  j1= j0;
373  ++j0;
374  }
375 
376  return true;
377 
378 }
379 
380 // Triangulate a no convex polygon
381 void glc::triangulatePolygon(QList<GLuint>* pIndexList, const QList<float>& bulkList)
382 {
383  int size= pIndexList->size();
384  if (polygonIsConvex(pIndexList, bulkList))
385  {
386  QList<GLuint> indexList(*pIndexList);
387  pIndexList->clear();
388  for (int i= 0; i < size - 2; ++i)
389  {
390  pIndexList->append(indexList.at(0));
391  pIndexList->append(indexList.at(i + 1));
392  pIndexList->append(indexList.at(i + 2));
393  }
394  }
395  else
396  {
397  // Get the polygon vertice
398  QList<GLC_Point3d> originPoints;
399  QHash<int, int> indexMap;
400 
401  QList<int> face;
402  GLC_Point3d currentPoint;
403  int delta= 0;
404  for (int i= 0; i < size; ++i)
405  {
406  const int currentIndex= pIndexList->at(i);
407  currentPoint= GLC_Point3d(bulkList.at(currentIndex * 3), bulkList.at(currentIndex * 3 + 1), bulkList.at(currentIndex * 3 + 2));
408  if (!originPoints.contains(currentPoint))
409  {
410  originPoints.append(GLC_Point3d(bulkList.at(currentIndex * 3), bulkList.at(currentIndex * 3 + 1), bulkList.at(currentIndex * 3 + 2)));
411  indexMap.insert(i - delta, currentIndex);
412  face.append(i - delta);
413  }
414  else
415  {
416  qDebug() << "Multi points";
417  ++delta;
418  }
419  }
420  // Values of PindexList must be reset
421  pIndexList->clear();
422 
423  // Update size
424  size= size - delta;
425 
426  // Check new size
427  if (size < 3) return;
428 
429  //-------------- Change frame to mach polygon plane
430  // Compute face normal
431  const GLC_Point3d point1(originPoints[0]);
432  const GLC_Point3d point2(originPoints[1]);
433  const GLC_Point3d point3(originPoints[2]);
434 
435  const GLC_Vector3d edge1(point2 - point1);
436  const GLC_Vector3d edge2(point3 - point2);
437 
438  GLC_Vector3d polygonPlaneNormal(edge1 ^ edge2);
439  polygonPlaneNormal.normalize();
440 
441  // Create the transformation matrix
442  GLC_Matrix4x4 transformation;
443 
444  GLC_Vector3d rotationAxis(polygonPlaneNormal ^ Z_AXIS);
445  if (!rotationAxis.isNull())
446  {
447  const double angle= acos(polygonPlaneNormal * Z_AXIS);
448  transformation.setMatRot(rotationAxis, angle);
449  }
450 
451  QList<GLC_Point2d> polygon;
452  // Transform polygon vertexs
453  for (int i=0; i < size; ++i)
454  {
455  originPoints[i]= transformation * originPoints[i];
456  // Create 2d vector
457  polygon << originPoints[i].toVector2d(Z_AXIS);
458  }
459  // Create the index
460  QList<int> index= face;
461 
462  const bool faceIsCounterclockwise= isCounterclockwiseOrdered(polygon);
463 
464  if(!faceIsCounterclockwise)
465  {
466  //qDebug() << "face Is Not Counterclockwise";
467  const int max= size / 2;
468  for (int i= 0; i < max; ++i)
469  {
470  polygon.swap(i, size - 1 -i);
471  int temp= face[i];
472  face[i]= face[size - 1 - i];
473  face[size - 1 - i]= temp;
474  }
475  }
476 
477  QList<int> tList;
478  triangulate(polygon, index, tList);
479  size= tList.size();
480  for (int i= 0; i < size; i+= 3)
481  {
482  // Avoid normal problem
483  if (faceIsCounterclockwise)
484  {
485  pIndexList->append(indexMap.value(face[tList[i]]));
486  pIndexList->append(indexMap.value(face[tList[i + 1]]));
487  pIndexList->append(indexMap.value(face[tList[i + 2]]));
488  }
489  else
490  {
491  pIndexList->append(indexMap.value(face[tList[i + 2]]));
492  pIndexList->append(indexMap.value(face[tList[i + 1]]));
493  pIndexList->append(indexMap.value(face[tList[i]]));
494  }
495  }
496  Q_ASSERT(size == pIndexList->size());
497  }
498 
499 }
500 
501 bool glc::lineIntersectPlane(const GLC_Line3d& line, const GLC_Plane& plane, GLC_Point3d* pPoint)
502 {
503  const GLC_Vector3d n= plane.normal();
504  const GLC_Point3d p= line.startingPoint();
505  const GLC_Vector3d d= line.direction();
506 
507  const double denominator= d * n;
508  if (qFuzzyCompare(fabs(denominator), 0.0))
509  {
510  qDebug() << " glc::lineIntersectPlane : Line parallel to the plane";
511  // The line is parallel to the plane
512  return false;
513  }
514  else
515  {
516  // The line intersect the plane by one point
517  const double t= -((n * p) + plane.coefD()) / denominator;
518  (*pPoint)= p + (t * d);
519 
520  return true;
521  }
522 }
523 
524 GLC_Point3d glc::project(const GLC_Point3d& point, const GLC_Line3d& line)
525 {
526  const GLC_Vector3d lineDirection(line.direction().normalize());
527  double t= lineDirection * (point - line.startingPoint());
528  GLC_Point3d projectedPoint= line.startingPoint() + (t * lineDirection);
529  return projectedPoint;
530 }
531 
532 double glc::pointLineDistance(const GLC_Point3d& point, const GLC_Line3d& line)
533 {
534  const GLC_Vector3d lineDirection(line.direction().normalize());
535  double t= lineDirection * (point - line.startingPoint());
536  GLC_Point3d projectedPoint= line.startingPoint() + (t * lineDirection);
537  return (point - projectedPoint).length();
538 }
539 
540 bool glc::pointsAreCollinear(const GLC_Point3d& p1, const GLC_Point3d& p2, const GLC_Point3d& p3)
541 {
542  bool subject= false;
543  if (compare(p1, p2) || compare(p1, p3) || compare(p2, p3))
544  {
545  subject= true;
546  }
547  else
548  {
549  GLC_Vector3d p1p2= (p2 - p1).setLength(1.0);
550  GLC_Vector3d p2p3= (p3 - p2).setLength(1.0);
551  subject= (compare(p1p2, p2p3) || compare(p1p2, p2p3.inverted()));
552  }
553  return subject;
554 }
555 
556 bool glc::compare(double p1, double p2)
557 {
558  return qAbs(p1 - p2) <= comparedPrecision;
559 }
560 
561 bool glc::compare(double p1, double p2, double accuracy)
562 {
563  return qAbs(p1 - p2) <= accuracy;
564 }
565 
566 bool glc::compareAngle(double p1, double p2)
567 {
568  const double anglePrecision= toRadian(comparedPrecision);
569  return qAbs(p1 - p2) <= anglePrecision;
570 }
571 
572 bool glc::compare(const GLC_Vector3d& v1, const GLC_Vector3d& v2)
573 {
574  bool compareResult= (qAbs(v1.x() - v2.x()) <= comparedPrecision);
575  compareResult= compareResult && (qAbs(v1.y() - v2.y()) <= comparedPrecision);
576  compareResult= compareResult && (qAbs(v1.z() - v2.z()) <= comparedPrecision);
577 
578  return compareResult;
579 }
580 
581 bool glc::compare(const GLC_Vector3d& v1, const GLC_Vector3d& v2, double accuracy)
582 {
583  bool compareResult= (qAbs(v1.x() - v2.x()) <= accuracy);
584  compareResult= compareResult && (qAbs(v1.y() - v2.y()) <= accuracy);
585  compareResult= compareResult && (qAbs(v1.z() - v2.z()) <= accuracy);
586 
587  return compareResult;
588 }
589 
590 bool glc::compare(const GLC_Vector2d& v1, const GLC_Vector2d& v2)
591 {
592  bool compareResult= (qAbs(v1.x() - v2.x()) <= comparedPrecision);
593  return compareResult && (qAbs(v1.y() - v2.y()) <= comparedPrecision);
594 }
595 
596 bool glc::compare(const GLC_Vector2d& v1, const GLC_Vector2d& v2, double accuracy)
597 {
598  bool compareResult= (qAbs(v1.x() - v2.x()) <= accuracy);
599  return compareResult && (qAbs(v1.y() - v2.y()) <= accuracy);
600 }
601 
602 bool glc::compare(const QPointF& v1, const QPointF& v2)
603 {
604  bool compareResult= (qAbs(v1.x() - v2.x()) <= comparedPrecision);
605  return compareResult && (qAbs(v1.y() - v2.y()) <= comparedPrecision);
606 }
607 
608 bool glc::compare(const QPointF& v1, const QPointF& v2, double accuracy)
609 {
610  bool compareResult= (qAbs(v1.x() - v2.x()) <= accuracy);
611  return compareResult && (qAbs(v1.y() - v2.y()) <= accuracy);
612 }
613 
614 double glc::round(double value)
615 {
616  value= value / comparedPrecision;
617  value= (value >= 0.0 ? floor(value + 0.5) : ceil(value - 0.5));
618  value= value * comparedPrecision;
619  return value;
620 }
621 
622 double glc::round(double value, double accuracy)
623 {
624  value= value / accuracy;
625  value= (value >= 0.0 ? floor(value + 0.5) : ceil(value - 0.5));
626  value= value * accuracy;
627  return value;
628 }
629 
630 QPointF glc::round(const QPointF& point)
631 {
632  QPointF subject(glc::round(static_cast<double>(point.x())), glc::round(static_cast<double>(point.y())));
633  return subject;
634 }
635 
636 QPointF glc::round(const QPointF& point, double accuracy)
637 {
638  QPointF subject(glc::round(static_cast<double>(point.x()), accuracy), glc::round(static_cast<double>(point.y()), accuracy));
639  return subject;
640 }
641 
643 {
644  GLC_Vector2d subject(glc::round(vector.x()), glc::round(vector.y()));
645 
646  return subject;
647 }
648 
649 GLC_Vector2d round(const GLC_Vector2d& vector, double accuracy)
650 {
651  GLC_Vector2d subject(glc::round(vector.x(), accuracy), glc::round(vector.y(), accuracy));
652 
653  return subject;
654 }
655 
657 {
658  GLC_Vector3d subject(glc::round(vector.x()), glc::round(vector.y()), glc::round(vector.z()));
659 
660  return subject;
661 }
662 
663 GLC_Vector3d round(const GLC_Vector3d& vector, double accuracy)
664 {
665  GLC_Vector3d subject(glc::round(vector.x(), accuracy), glc::round(vector.y(), accuracy), glc::round(vector.z(), accuracy));
666 
667  return subject;
668 }
669 
670 bool glc::pointInPolygon(const GLC_Point2d& point, const QList<GLC_Point2d>& polygon)
671 {
672  const int polygonSize= polygon.size();
673  bool inside= false;
674  int i= 0;
675  int j= polygonSize - 1;
676 
677  while (i < polygonSize)
678  {
679  const GLC_Point2d point0= polygon.at(i);
680  const GLC_Point2d point1= polygon.at(j);
681  if (point.y() < point1.y())
682  {
683  //point1 above ray
684  if (point0.y() <= point.y())
685  {
686  //point2 on or below ray
687  const double val1= (point.y() - point0.y()) * (point1.x() - point0.x());
688  const double val2= (point.x() - point0.x()) * (point1.y() - point0.y());
689  if (val1 > val2) inside= !inside;
690  }
691  }
692  else if (point.y() < point0.y())
693  {
694  // point 1 on or below ray, point0 above ray
695  const double val1= (point.y() - point0.y()) * (point1.x() - point0.x());
696  const double val2= (point.x() - point0.x()) * (point1.y() - point0.y());
697  if (val1 < val2) inside= !inside;
698  }
699  j= i;
700  ++i;
701  }
702  return inside;
703 }
704 
705 double glc::zeroTo2PIAngle(double angle)
706 {
707  if (qFuzzyCompare(fabs(angle), glc::PI))
708  {
709  angle= glc::PI;
710  }
711  else if (angle < 0)
712  {
713  angle= (2.0 * glc::PI) + angle;
714  }
715  return angle;
716 }
717 
718 QList<GLC_Point2d> glc::polygonIn2d(QList<GLC_Point3d> polygon3d)
719 {
720  const int count= polygon3d.count();
721  Q_ASSERT(count > 2);
722 
723  // Compute face normal
724  const GLC_Point3d point1(polygon3d[0]);
725  const GLC_Point3d point2(polygon3d[1]);
726  const GLC_Point3d point3(polygon3d[2]);
727 
728  const GLC_Vector3d edge1(point2 - point1);
729  const GLC_Vector3d edge2(point3 - point2);
730 
731  GLC_Vector3d polygonPlaneNormal(edge1 ^ edge2);
732  polygonPlaneNormal.normalize();
733 
734  // Create the transformation matrix
735  GLC_Matrix4x4 transformation;
736 
737  GLC_Vector3d rotationAxis(polygonPlaneNormal ^ Z_AXIS);
738  if (!rotationAxis.isNull())
739  {
740  const double angle= acos(polygonPlaneNormal * Z_AXIS);
741  transformation.setMatRot(rotationAxis, angle);
742  }
743 
744  QList<GLC_Point2d> subject;
745  // Transform polygon vertexs
746  for (int i=0; i < count; ++i)
747  {
748  polygon3d[i]= transformation * polygon3d[i];
749  // Create 2d vector
750  subject << polygon3d[i].toVector2d(Z_AXIS);
751  }
752 
753  return subject;
754 }
755 
756 QList<GLC_Point2d> glc::normalyzePolygon(const QList<GLC_Point2d>& polygon)
757 {
758  QList<GLC_Point2d> subject;
759  const int count= polygon.count();
760  Q_ASSERT(count > 2);
761 
762  GLC_Point2d minPoint= polygon.first();
763  GLC_Point2d maxPoint= minPoint;
764  for (int i= 1; i < count; ++i)
765  {
766  GLC_Point2d point= polygon.at(i);
767  minPoint.setX(qMin(point.x(), minPoint.x()));
768  minPoint.setY(qMin(point.y(), minPoint.y()));
769 
770  maxPoint.setX(qMax(point.x(), maxPoint.x()));
771  maxPoint.setY(qMax(point.y(), maxPoint.y()));
772  }
773  const GLC_Vector2d range= maxPoint - minPoint;
774  Q_ASSERT(range.x() != 0.0);
775  Q_ASSERT(range.y() != 0.0);
776 
777  for (int i= 0; i < count; ++i)
778  {
779  const GLC_Point2d point= polygon.at(i);
780  const GLC_Point2d temp= (point - minPoint);
781 
782  const GLC_Point2d result(temp.x() / range.x(), temp.y() / range.y());
783  subject.append(result);
784  }
785 
786  return subject;
787 }

©2005-2013 Laurent Ribon