gwnavruntime/queries/utils/polygonintersector.h Source File

polygonintersector.h
Go to the documentation of this file.
1 /*
2 * Copyright 2015 Autodesk, Inc. All rights reserved.
3 * Use of this software is subject to the terms of the Autodesk license agreement and any attachments or Appendices thereto provided at the time of installation or download,
4 * or which otherwise accompanies this software in either electronic or hard copy form, or which is signed by you and accepted by Autodesk.
5 */
6 
7 
8 // Primary contact: JUBA - secondary contact: NOBODY
9 #ifndef Navigation_PolygonIntersector_H
10 #define Navigation_PolygonIntersector_H
11 
15 
16 namespace Kaim
17 {
18 
19 /*
20 class PolygonIntersector
21 */
22 class PolygonIntersector
23 {
24  KY_DEFINE_NEW_DELETE_OPERATORS(MemStat_Query)
25 
26 public:
27  PolygonIntersector(const Vec2f* points, KyUInt32 pointCount, KyFloat32 integerPrecision)
28  {
29  if (pointCount > 0)
30  {
31  bool inputPolylineIsClosed = points[0] == points[pointCount-1];
32  m_points.Resize(inputPolylineIsClosed ? pointCount : pointCount+1);
33 
34  for(KyUInt32 i = 0; i < pointCount; ++i)
35  {
36  m_points[i] = points[i];
37  m_box2f.ExpandByVec2(points[i]);
38  }
39 
40  if (inputPolylineIsClosed == false)
41  m_points[pointCount] = points[0];
42  }
43 
44  m_integerPrecision = integerPrecision;
45  }
46 
47  bool DoesIntersectEdge(const CoordPos64& startEdgeCoordPos, const CoordPos64& endEdgeCoordPos)
48  {
49  const Vec2f startEdgePos(startEdgeCoordPos.x * m_integerPrecision, startEdgeCoordPos.y * m_integerPrecision);
50  const Vec2f endEdgePos(endEdgeCoordPos.x * m_integerPrecision, endEdgeCoordPos.y * m_integerPrecision);
51 
52  Box2f edgeBox(
53  Kaim::Min(startEdgePos.x, endEdgePos.x), Kaim::Min(startEdgePos.y, endEdgePos.y),
54  Kaim::Max(startEdgePos.x, endEdgePos.x), Kaim::Max(startEdgePos.y, endEdgePos.y));
55 
56  if (Intersections::AABBVsAABB2d(m_box2f, edgeBox) == false)
57  return false;
58 
59  if (IsPointInsidePolyline(startEdgePos))
60  return true;
61 
62  if (IsPointInsidePolyline(endEdgePos))
63  return true;
64 
65  return DoesEdgeIntersectOnePolylineBorder(startEdgePos, endEdgePos);
66  }
67 
68  bool IsPointInsidePolyline(const Vec2f& point)
69  {
70  if (m_box2f.IsPoint2DInside(point) == false)
71  return false;
72 
73  return GeometryFunctions::IsInside2d_Polyline(point, m_points.GetDataPtr(), m_points.GetCount());
74  }
75 
76  bool DoesEdgeIntersectOnePolylineBorder(const Vec2f& startEdgePos, const Vec2f& endEdgePos)
77  {
78  KyUInt32 pointCount = m_points.GetCount();
79  for(KyUInt32 i = 0; i < pointCount - 1; ++i)
80  {
81  if (Intersections::SegmentVsSegment2d(m_points[i], m_points[i+1], startEdgePos, endEdgePos))
82  return true;
83  }
84 
85  return false;
86  }
87 private:
88  KyArrayPOD<Vec2f> m_points;
89  Box2f m_box2f;
90  KyFloat32 m_integerPrecision;
91 };
92 
93 
94 }
95 
96 
97 #endif //Navigation_PolygonIntersector_H
98 
T Min(const T &a, const T &b)
Returns the lesser of the two specified values.
Definition: fastmath.h:113
Vec2LL CoordPos64
A type that represents the position of a point within the 2D integer grid.
Definition: navmeshtypes.h:19
T Max(const T &a, const T &b)
Returns the greater of the two specified values.
Definition: fastmath.h:121
Definition: gamekitcrowddispersion.h:20
#define KY_DEFINE_NEW_DELETE_OPERATORS(MemStat)
This macro defines new and delete operators.
Definition: memory.h:137
unsigned int KyUInt32
Type used internally to represent an unsigned 32-bit integer.
Definition: types.h:36
float KyFloat32
Type used internally to represent a 32-bit floating-point number.
Definition: types.h:43