xmsgrid  1.0
GmMultiPolyIntersector.cpp
Go to the documentation of this file.
1 //------------------------------------------------------------------------------
6 //------------------------------------------------------------------------------
7 
8 //----- Included files ---------------------------------------------------------
9 
10 // 1. Precompiled header
11 
12 // 2. My own header
13 #include <xmsgrid/geometry/GmMultiPolyIntersector.h>
14 
15 // 3. Standard library headers
16 
17 // 4. External library headers
18 #pragma warning(push)
19 #pragma warning(disable : 4512) // boost code: no assignment operator
20 #include <boost/geometry.hpp>
21 #include <boost/geometry/geometries/linestring.hpp>
22 #include <boost/geometry/geometries/point_xy.hpp>
23 #include <boost/geometry/geometries/polygon.hpp>
24 #include <boost/geometry/index/rtree.hpp>
25 #pragma warning(pop)
26 
27 // 5. Shared code headers
28 #include <xmscore/math/math.h> // GTEQ_TOL
29 #include <xmscore/misc/XmConst.h>
30 #include <xmscore/misc/XmError.h> // XM_ASSERT
31 #include <xmscore/misc/XmLog.h>
32 #include <xmscore/misc/boost_defines.h> // BSHP
33 #include <xmscore/misc/xmstype.h> // XM_NODATA
34 #include <xmscore/points/pt.h> // Pt3d
35 #include <xmscore/stl/set.h> // Set*
36 #include <xmscore/stl/vector.h> // Vec*
37 #include <xmsgrid/geometry/GmBoostTypes.h> // GmBstPoly3d, XmBstRing
38 #include <xmsgrid/geometry/GmMultiPolyIntersectionSorter.h> // GmMultiPolyIntersectionSorter
39 #include <xmsgrid/geometry/GmMultiPolyIntersectorData.h> // GmMultiPolyIntersectorData
40 #include <xmsgrid/geometry/geoms.h> // gmPolygonArea, gmAddToExtents, gmXyDistance
41 
42 //----- Forward declarations ---------------------------------------------------
43 
44 namespace bg = boost::geometry;
45 namespace bgi = boost::geometry::index;
46 
47 //----- External globals -------------------------------------------------------
48 
49 //----- Namespace declaration --------------------------------------------------
50 
51 namespace xms
52 {
53 //----- Constants / Enumerations -----------------------------------------------
54 
55 // Typedefs
56 typedef std::pair<GmBstBox3d, int> ValueBox;
57 typedef bgi::rtree<ValueBox, bgi::quadratic<8>> RtreeBox;
58 
59 //----- Classes / Structs ------------------------------------------------------
60 
62 class GmMultiPolyIntersectorImpl : public GmMultiPolyIntersector
63 {
64 public:
65  GmMultiPolyIntersectorImpl(const VecPt3d& a_points,
66  const VecInt2d& a_polys,
67  BSHP<GmMultiPolyIntersectionSorter> a_sorter,
68  int a_startingId = 1);
69  virtual ~GmMultiPolyIntersectorImpl();
70 
71  virtual void SetQuery(GmMultiPolyIntersectorQueryEnum a_query) override;
72  virtual void TraverseLineSegment(double a_x1,
73  double a_y1,
74  double a_x2,
75  double a_y2,
76  VecInt& a_polyIds,
77  VecDbl& a_tValues) override;
78  virtual void TraverseLineSegment(double a_x1,
79  double a_y1,
80  double a_x2,
81  double a_y2,
82  VecInt& a_polyIds) override;
83  virtual void TraverseLineSegment(double a_x1,
84  double a_y1,
85  double a_x2,
86  double a_y2,
87  VecInt& a_polyIds,
88  VecPt3d& a_pts) override;
89  virtual void TraverseLineSegment(double a_x1,
90  double a_y1,
91  double a_x2,
92  double a_y2,
93  VecInt& a_polyIds,
94  VecDbl& a_tValues,
95  VecPt3d& a_pts) override;
96  virtual int PolygonFromPoint(const Pt3d& a_pt) override;
97 
98 private:
99  void RemoveDuplicateTValues(VecInt& a_polyIds, VecDbl& a_tValues, VecPt3d& a_pts);
100  void CalculateBuffer();
101  void BufferTheBox(GmBstBox3d& box) const;
102  GmBstPoly3d& GetBoostPoly(int a_polyIdx);
103  void BuildBoostPoly(int a_polyIdx, GmBstPoly3d& a_boostPoly) const;
104  void BuildRTree();
105  void CreateLine();
106  void GetPolysForPoint(Pt3d pt, SetInt& poly);
107  void EnsureEndPointsRepresented();
108  void IntersectEachPolyWithLine();
109  void ComputeTValues();
110  void SortIntersections();
111  void OffsetPolyIds(VecInt& polyIds) const;
112  void PointsOnSegment(const GmBstPoly3d& a_poly,
113  const GmBstLine3d& a_line,
114  std::deque<Pt3d>& a_output);
115  // void ValidatePolygons ();
116 
117  GmMultiPolyIntersectorData m_d;
118  Pt3d m_pt1;
119  Pt3d m_pt2;
120  RtreeBox* m_rtree;
121  GmBstLine3d m_line;
122  double m_buffer;
123  double m_xyTol;
124  int m_startingId;
125  std::vector<GmBstPoly3d> m_boostPolys;
126  BSHP<GmMultiPolyIntersectionSorter> m_sorter;
127  GmMultiPolyIntersectorQueryEnum m_query;
128 }; // class GmMultiPolyIntersectorImpl
129 
130 //----- Class / Function definitions -------------------------------------------
131 
136 //------------------------------------------------------------------------------
138 //------------------------------------------------------------------------------
139 GmMultiPolyIntersector::GmMultiPolyIntersector()
140 {
141 } // GmMultiPolyIntersector::GmMultiPolyIntersector
142 //------------------------------------------------------------------------------
144 //------------------------------------------------------------------------------
145 GmMultiPolyIntersector::~GmMultiPolyIntersector()
146 {
147 } // GmMultiPolyIntersector::~GmMultiPolyIntersector
148 //------------------------------------------------------------------------------
158 //------------------------------------------------------------------------------
159 BSHP<GmMultiPolyIntersector> GmMultiPolyIntersector::New(
160  const VecPt3d& a_points,
161  const VecInt2d& a_polys,
162  BSHP<GmMultiPolyIntersectionSorter> a_sorter,
163  int a_startingId /*=1*/)
164 {
165  return BDPC<GmMultiPolyIntersector>(BSHP<GmMultiPolyIntersectorImpl>(
166  new GmMultiPolyIntersectorImpl(a_points, a_polys, a_sorter, a_startingId)));
167 } // GmMultiPolyIntersector::GmMultiPolyIntersector
168 
175 //------------------------------------------------------------------------------
184 //------------------------------------------------------------------------------
185 GmMultiPolyIntersectorImpl::GmMultiPolyIntersectorImpl(const VecPt3d& a_points,
186  const VecInt2d& a_polys,
187  BSHP<GmMultiPolyIntersectionSorter> a_sorter,
188  int a_startingId /*=1*/)
189 : m_d()
190 , m_pt1()
191 , m_pt2()
192 , m_rtree(nullptr)
193 , m_line()
194 , m_buffer(0.0)
195 , m_startingId(a_startingId)
196 , m_boostPolys()
197 , m_sorter(a_sorter)
198 , m_query(GMMPIQ_COVEREDBY)
199 {
200  m_d.m_points = a_points;
201 
202  m_d.m_polys = a_polys;
203  // ValidatePolygons();
204 
205  m_boostPolys.assign(a_polys.size(), GmBstPoly3d());
206 
207  CalculateBuffer();
208  BuildRTree();
209 } // GmMultiPolyIntersectorImpl::GmMultiPolyIntersectorImpl
210 //------------------------------------------------------------------------------
212 //------------------------------------------------------------------------------
213 GmMultiPolyIntersectorImpl::~GmMultiPolyIntersectorImpl()
214 {
215  if (m_rtree)
216  delete (m_rtree);
217 } // GmMultiPolyIntersectorImpl::GmMultiPolyIntersectorImpl
221 // void GmMultiPolyIntersectorImpl::ValidatePolygons ()
222 //{
223 //#ifdef _DEBUG
224 // for (size_t i = 0; i < m_d.m_polys.size(); ++i) {
225 // VecPt3d poly;
226 // for (size_t j = 0; j < m_d.m_polys[i].size(); ++j) {
227 // poly.push_back(m_d.m_points[m_d.m_polys[i][j]]);
228 // }
229 // XM_ASSERT(gmPolygonArea(&poly[0], poly.size()) > 0);
230 // }
231 //#endif
232 //} // GmMultiPolyIntersectorImpl::ValidatePolygons
233 //------------------------------------------------------------------------------
236 //------------------------------------------------------------------------------
237 void GmMultiPolyIntersectorImpl::CalculateBuffer()
238 {
239  // Get min/max of all polys
240  Pt3d mn(XM_DBL_HIGHEST), mx(XM_DBL_LOWEST);
241  for (size_t i = 0; i < m_d.m_polys.size(); ++i)
242  {
243  for (size_t j = 0; j < m_d.m_polys[i].size(); ++j)
244  {
245  gmAddToExtents(m_d.m_points[m_d.m_polys[i][j]], mn, mx);
246  }
247  }
248 
249  // Calculate the buffer as a fraction of the distance between mn and mx
250  const double kFraction = 1e-5; // 0.00001
251  m_buffer = gmXyDistance(mn, mx) * kFraction;
252  m_xyTol = gmComputeXyTol(mn, mx);
253 } // GmMultiPolyIntersectorImpl::CalculateBuffer
254 //------------------------------------------------------------------------------
261 //------------------------------------------------------------------------------
262 void GmMultiPolyIntersectorImpl::BufferTheBox(GmBstBox3d& box) const
263 {
264  box.min_corner().x -= m_buffer;
265  box.min_corner().y -= m_buffer;
266  box.max_corner().x += m_buffer;
267  box.max_corner().y += m_buffer;
268 } // GmMultiPolyIntersectorImpl::BufferTheBox
269 //------------------------------------------------------------------------------
273 //------------------------------------------------------------------------------
274 GmBstPoly3d& GmMultiPolyIntersectorImpl::GetBoostPoly(int a_polyIdx)
275 {
276  if (m_boostPolys[a_polyIdx].outer().empty())
277  {
278  // if (bg::exterior_ring(m_boostPolys[a_polyIdx]).empty()) {
279  BuildBoostPoly(a_polyIdx, m_boostPolys[a_polyIdx]);
280  }
281  return m_boostPolys[a_polyIdx];
282 } // GmMultiPolyIntersectorImpl::GetBoostPoly
283 //------------------------------------------------------------------------------
287 //------------------------------------------------------------------------------
288 void GmMultiPolyIntersectorImpl::BuildBoostPoly(int a_polyIdx, GmBstPoly3d& a_boostPoly) const
289 {
290  const VecInt& poly = m_d.m_polys[a_polyIdx];
291  for (int j = 0; j < (int)poly.size(); ++j)
292  {
293  Pt3d pt = m_d.m_points[poly[j]];
294  bg::exterior_ring(a_boostPoly).push_back(m_d.m_points[poly[j]]);
295  }
296  bg::exterior_ring(a_boostPoly).push_back(m_d.m_points[poly[0]]);
297 } // GmMultiPolyIntersectorImpl::BuildBoostPoly
298 //------------------------------------------------------------------------------
300 //------------------------------------------------------------------------------
301 void GmMultiPolyIntersectorImpl::BuildRTree()
302 {
303  // Changed to use the packing algorithm. See:
304  // http://www.boost.org/doc/libs/1_55_0/libs/geometry/doc/html/geometry/spatial_indexes/introduction.html
305  // We thought this would make it faster but according to the test
306  // GmMultiPolyIntersector2IntermediateTests::testLargeNumPolysAndSegments it
307  // didn't make much difference, and actually may be very slightly slower, but
308  // the test may not be very representative of real scenarios. The old code is
309  // still here but commented out in case we want to bring it back in the
310  // future. -MJK
311 
312  // m_rtree = new RtreeBox(); // Non packing algorithm
313  std::vector<ValueBox> boxen; // Packing algorithm
314 
315  for (int i = 0; i < (int)m_d.m_polys.size(); ++i)
316  {
317  Pt3d mn(XM_DBL_HIGHEST), mx(XM_DBL_LOWEST);
318  for (int j = 0; j < (int)m_d.m_polys[i].size(); ++j)
319  {
320  gmAddToExtents(m_d.m_points[m_d.m_polys[i][j]], mn, mx);
321  }
322  GmBstBox3d box(mn, mx);
323  BufferTheBox(box);
324  // m_rtree->insert(std::make_pair(box, i)); // Non packing algorithm
325  boxen.push_back(std::make_pair(box, i)); // Packing algorithm
326  }
327 
328  // Packing algorithm
329  m_rtree = new RtreeBox(boxen.begin(), boxen.end());
330 
331 } // GmMultiPolyIntersectorImpl::BuildRTree
332 //------------------------------------------------------------------------------
334 //------------------------------------------------------------------------------
335 void GmMultiPolyIntersectorImpl::CreateLine()
336 {
337  m_line.push_back(m_pt1);
338  m_line.push_back(m_pt2);
339 } // GmMultiPolyIntersectorImpl::CreateLine
340 //------------------------------------------------------------------------------
343 //------------------------------------------------------------------------------
344 void GmMultiPolyIntersectorImpl::SetQuery(GmMultiPolyIntersectorQueryEnum a_query)
345 {
346  m_query = a_query;
347 } // GmMultiPolyIntersectorImpl::SetQuery
348 //------------------------------------------------------------------------------
352 //------------------------------------------------------------------------------
353 void GmMultiPolyIntersectorImpl::GetPolysForPoint(Pt3d pt, SetInt& a_poly)
354 {
355  std::vector<ValueBox> result;
356  m_rtree->query(bgi::intersects(pt), std::back_inserter(result));
357 
358  // Find the polygon that the point is inside
359  for (size_t i = 0; i < result.size(); ++i)
360  {
361  GmBstPoly3d& poly = GetBoostPoly(result[i].second);
362  //(bg::within(pt, poly)) { // Seems to return true if inside
363  bool rv = false;
364  switch (m_query)
365  {
366  case GMMPIQ_COVEREDBY:
367  rv = bg::covered_by(pt, poly); // Seems to return true if inside or on
368  break;
369  case GMMPIQ_INTERSECTS:
370  rv = bg::intersects(pt, poly);
371  break;
372  default:
373  XM_ASSERT(false);
374  break;
375  }
376  if (rv)
377  {
378  a_poly.insert(result[i].second + 1);
379  }
380  }
381 
382 } // GmMultiPolyIntersectorImpl::GetPolysForPoint
383 //------------------------------------------------------------------------------
385 //------------------------------------------------------------------------------
386 void GmMultiPolyIntersectorImpl::IntersectEachPolyWithLine()
387 {
388  // Get potential polygons which intersect the line from the rtree
389  std::vector<ValueBox> result;
390  m_rtree->query(bgi::intersects(m_line), std::back_inserter(result));
391  // m_rtree.query(bgi::overlaps(m_line), std::back_inserter(result)); //
392  // doesn't compile m_rtree.query(bgi::covered_by(m_line),
393  // std::back_inserter(result)); // doesn't compile
394  // m_rtree.query(bgi::covers(m_line), std::back_inserter(result)); // doesn't
395  // compile
396 
397  // Go through the potential polygons and try to intersect them
398  for (size_t i = 0; i < result.size(); ++i)
399  {
400  GmBstPoly3d& poly = GetBoostPoly(result[i].second);
401  std::deque<Pt3d> output;
402  bg::intersection(poly, m_line, output);
403  if (2 > output.size())
404  PointsOnSegment(poly, m_line, output);
405  for (size_t j = 0; j < output.size(); ++j)
406  {
407  ix ixn(output[j], result[i].second + 1, XM_NODATA);
408  m_d.m_ixs.push_back(ixn);
409  }
410  }
411 } // GmMultiPolyIntersectorImpl::IntersectEachPolyWithLine
412 //------------------------------------------------------------------------------
418 //------------------------------------------------------------------------------
419 void GmMultiPolyIntersectorImpl::PointsOnSegment(const GmBstPoly3d& a_poly,
420  const GmBstLine3d& a_line,
421  std::deque<Pt3d>& a_output)
422 {
423  double tol = m_buffer * 1e-6;
424  for (size_t i = 0; i < a_poly.outer().size(); ++i)
425  {
426  const Pt3d& p = a_poly.outer()[i];
427  if (gmOnLineAndBetweenEndpointsWithTol(a_line[0], a_line[1], p.x, p.y, tol))
428  { // don't add the point if it is already in the output
429  bool dup = false;
430  for (size_t j = 0; j < a_output.size(); ++j)
431  {
432  if (gmEqualPointsXY(a_output[j], p, tol))
433  dup = true;
434  }
435  if (!dup)
436  a_output.push_back(p);
437  }
438  }
439 } // GmMultiPolyIntersectorImpl::PointsOnSegment
440 //------------------------------------------------------------------------------
445 //------------------------------------------------------------------------------
446 void GmMultiPolyIntersectorImpl::ComputeTValues()
447 {
448  for (size_t i = 0; i < m_d.m_ixs.size(); ++i)
449  {
450  if (m_d.m_ixs[i].m_t == XM_NODATA)
451  {
452  // to fix bug 11722 we changed this from gmXyDistanct to actually compute t
453  m_d.m_ixs[i].m_t = gmPtDistanceAlongSegment(m_pt1, m_pt2, m_d.m_ixs[i].m_pt, gmXyTol());
454  }
455  }
456  // added for bug fix for 11722 (july 2019, AKZ and MJK)
457  // get rid of any points that have a t value outside of the 0.0 to 1.0 range
458  // the boost intersection can find phantom intersections just beyond the segment
459  m_d.m_ixs.erase(std::remove_if(m_d.m_ixs.begin(), m_d.m_ixs.end(),
460  [](const ix& a_ix) {
461  return a_ix.m_t < -gmXyTol() || a_ix.m_t > 1.0 + gmXyTol();
462  }),
463  m_d.m_ixs.end());
464 } // GmMultiPolyIntersectorImpl::ComputeTValues
465 //------------------------------------------------------------------------------
467 //------------------------------------------------------------------------------
468 void GmMultiPolyIntersectorImpl::SortIntersections()
469 {
470  XM_ENSURE_TRUE_VOID_NO_ASSERT(m_d.m_ixs.size() > 1);
471 
472  // Sort intersections by t value
473  std::sort(m_d.m_ixs.begin(), m_d.m_ixs.end(),
474  [](const ix& a, const ix& b) -> bool { return a.m_t < b.m_t; });
475 
476 } // GmMultiPolyIntersectorImpl::SortIntersections
477 //------------------------------------------------------------------------------
480 //------------------------------------------------------------------------------
481 void GmMultiPolyIntersectorImpl::EnsureEndPointsRepresented()
482 {
483  // If 1st point was in or on poly, make sure there's an intersection for it
484  for (SetInt::iterator it = m_d.m_polys1.begin(); it != m_d.m_polys1.end(); ++it)
485  {
486  bool found = false;
487  for (size_t i = 0; i < m_d.m_ixs.size() && !found && m_d.m_ixs[i].m_t == 0.0; ++i)
488  {
489  if (m_d.m_ixs[i].m_i == *it)
490  found = true;
491  }
492  if (!found)
493  m_d.m_ixs.insert(m_d.m_ixs.begin(), ix(m_pt1, *it, 0.0));
494  }
495 
496  // If 2nd point was in or on poly, make sure there's an intersection for it
497  for (SetInt::iterator it = m_d.m_polys2.begin(); it != m_d.m_polys2.end(); ++it)
498  {
499  bool found = false;
500  for (size_t i = m_d.m_ixs.size(); i-- > 0 && !found && m_d.m_ixs[i].m_t == 1.0;)
501  {
502  if (m_d.m_ixs[i].m_i == *it)
503  found = true;
504  }
505  if (!found)
506  m_d.m_ixs.push_back(ix(m_pt2, *it, 1.0));
507  }
508 } // GmMultiPolyIntersectorImpl::EnsureEndPointsRepresented
509 //------------------------------------------------------------------------------
513 //------------------------------------------------------------------------------
514 void GmMultiPolyIntersectorImpl::OffsetPolyIds(VecInt& polyIds) const
515 {
516  if (m_startingId != 1)
517  {
518  int offset = m_startingId - 1;
519  for (int i = 0; i < (int)polyIds.size() - 1; ++i)
520  {
521  if (polyIds[i] != XM_NONE)
522  {
523  polyIds[i] += offset;
524  }
525  }
526  }
527 } // GmMultiPolyIntersectorImpl::OffsetPolyIds
528 //------------------------------------------------------------------------------
544 //------------------------------------------------------------------------------
545 void GmMultiPolyIntersectorImpl::TraverseLineSegment(double a_x1,
546  double a_y1,
547  double a_x2,
548  double a_y2,
549  VecInt& a_polyIds,
550  VecDbl& a_tValues)
551 {
552  VecPt3d pts;
553  TraverseLineSegment(a_x1, a_y1, a_x2, a_y2, a_polyIds, a_tValues, pts);
554 } // GmMultiPolyIntersectorImpl::TraverseLineSegment
555 //------------------------------------------------------------------------------
563 //------------------------------------------------------------------------------
564 void GmMultiPolyIntersectorImpl::TraverseLineSegment(double a_x1,
565  double a_y1,
566  double a_x2,
567  double a_y2,
568  VecInt& a_polyIds)
569 {
570  VecDbl tvalues;
571  VecPt3d pts;
572  TraverseLineSegment(a_x1, a_y1, a_x2, a_y2, a_polyIds, tvalues, pts);
573 } // GmMultiPolyIntersectorImpl::TraverseLineSegment
574 //-----------------------------------------------------------------------------
584 //-----------------------------------------------------------------------------
585 void GmMultiPolyIntersectorImpl::TraverseLineSegment(double a_x1,
586  double a_y1,
587  double a_x2,
588  double a_y2,
589  VecInt& a_polyIds,
590  VecPt3d& a_pts)
591 {
592  VecDbl tvalues;
593  TraverseLineSegment(a_x1, a_y1, a_x2, a_y2, a_polyIds, tvalues, a_pts);
594 } // GmMultiPolyIntersectorImpl::TraverseLineSegment
595 //-----------------------------------------------------------------------------
613 //-----------------------------------------------------------------------------
614 void GmMultiPolyIntersectorImpl::TraverseLineSegment(double a_x1,
615  double a_y1,
616  double a_x2,
617  double a_y2,
618  VecInt& a_polyIds,
619  VecDbl& a_tValues,
620  VecPt3d& a_pts)
621 {
622  double oldTolerance = gmXyTol();
623  gmXyTol(true, m_xyTol);
624  m_pt1.Set(a_x1, a_y1, 0.0);
625  m_pt2.Set(a_x2, a_y2, 0.0);
626  GetPolysForPoint(m_pt1, m_d.m_polys1);
627  GetPolysForPoint(m_pt2, m_d.m_polys2);
628  CreateLine();
629  IntersectEachPolyWithLine();
630  ComputeTValues();
631  SortIntersections();
632  EnsureEndPointsRepresented();
633  if (!m_sorter)
634  {
635  XM_ASSERT(false);
636  }
637  else
638  {
639  double kTol = 1e-13; // Used to compare t values which are always 0.0 - 1.0
640  m_sorter->Sort(m_d, a_polyIds, a_tValues, a_pts, kTol);
641  }
642  OffsetPolyIds(a_polyIds);
643  RemoveDuplicateTValues(a_polyIds, a_tValues, a_pts);
644 
645  m_d.m_ixs.clear();
646  m_d.m_polys1.clear();
647  m_d.m_polys2.clear();
648  m_line.clear();
649  gmXyTol(true, oldTolerance);
650 } // GmMultiPolyIntersectorImpl::TraverseLineSegment
651 //-----------------------------------------------------------------------------
664 //-----------------------------------------------------------------------------
665 void GmMultiPolyIntersectorImpl::RemoveDuplicateTValues(VecInt& a_polyIds,
666  VecDbl& a_tValues,
667  VecPt3d& a_pts)
668 {
669  VecInt indexesToRemove;
670  int size((int)a_tValues.size());
671  for (int i = size - 1; i > 0; --i)
672  {
673  // Check for multiple T-values close to 1.0 (at the end of the line segment).
674  if (GTEQ_TOL(a_tValues[i], 1.0, XM_ZERO_TOL) && GTEQ_TOL(a_tValues[i - 1], 1.0, XM_ZERO_TOL))
675  {
676  for (int j = i - 1; j > 0; --j)
677  {
678  // If the T-values are 1.0 and the polygon IDs are the same (for example, -1), go ahead and
679  // remove these intersections
680  if (GTEQ_TOL(a_tValues[i], 1.0, XM_ZERO_TOL) && GTEQ_TOL(a_tValues[j], 1.0, XM_ZERO_TOL) &&
681  a_polyIds[i] == a_polyIds[j])
682  indexesToRemove.push_back(j);
683  }
684  }
685  else if (a_polyIds[i] == -1 && a_polyIds[i - 1] == -1)
686  {
687  // Remove excess "end" (-1) polygon IDs
688  for (int j = i - 1; j > 0; --j)
689  {
690  // Use 0.1 for the tolerance here because you have multiple end points and
691  // there really should only be a single end point unless your T-value is less
692  // than 0.9 and you've gone outside the mesh.
693  if (GTEQ_TOL(a_tValues[i], 1.0, 0.1) && GTEQ_TOL(a_tValues[j], 1.0, 0.1) &&
694  a_polyIds[j] == -1)
695  indexesToRemove.push_back(j);
696  }
697  }
698  else
699  break;
700  }
701  if (!indexesToRemove.empty())
702  {
703  auto it = std::unique(indexesToRemove.begin(), indexesToRemove.end());
704  indexesToRemove.resize(std::distance(indexesToRemove.begin(), it));
705  for (auto&& i : indexesToRemove)
706  {
707  a_polyIds.erase(a_polyIds.begin() + i);
708  a_tValues.erase(a_tValues.begin() + i);
709  a_pts.erase(a_pts.begin() + i);
710  }
711  }
712 } // GmMultiPolyIntersectorImpl::RemoveDuplicateTValues
713 //-----------------------------------------------------------------------------
717 //-----------------------------------------------------------------------------
718 int GmMultiPolyIntersectorImpl::PolygonFromPoint(const Pt3d& a_pt)
719 {
720  int rval(XM_NONE);
721  SetInt polys;
722  GetPolysForPoint(a_pt, polys);
723  if (!polys.empty())
724  {
725  rval = (int)*polys.begin();
726  }
727  return rval;
728 } // GmMultiPolyIntersectorImpl::PolygonFromPoint
729 } // namespace xms
730 
732 // TESTS
734 #ifdef CXX_TEST
735 
736 #include <xmsgrid/geometry/GmMultiPolyIntersector.t.h>
737 
738 #include <fstream>
739 
740 #include <xmscore/dataio/daStreamIo.h>
741 #include <xmscore/testing/TestTools.h>
742 #include <xmsgrid/geometry/GmMultiPolyIntersectionSorterTerse.h>
743 #include <xmsgrid/triangulate/triangles.h>
744 #include <xmsgrid/ugrid/XmEdge.h>
745 #include <xmsgrid/ugrid/XmUGrid.h>
746 #include <xmsgrid/ugrid/XmUGridUtils.h>
747 
748 //----- Namespace declaration --------------------------------------------------
749 
750 // namespace xms {
751 using namespace xms;
752 
753 namespace // unnamed namespace
754 {
755 //------------------------------------------------------------------------------
757 //------------------------------------------------------------------------------
758 void iRunTest(double x1,
759  double y1,
760  double x2,
761  double y2,
762  const VecPt3d& pts,
763  const VecInt2d& polys,
764  const VecInt& a_expectedPolyIDs,
765  const VecDbl& a_expectedtValues,
766  const VecPt3d& a_expectedPoints)
767 {
768  BSHP<GmMultiPolyIntersectionSorter> sorter =
769  BSHP<GmMultiPolyIntersectionSorter>(new GmMultiPolyIntersectionSorterTerse());
770  BSHP<GmMultiPolyIntersector> mpi = GmMultiPolyIntersector::New(pts, polys, sorter);
771  VecInt polyIds1, polyIds2, polyIds3, polyIds4;
772  VecDbl tValues1, tValues2;
773  VecPt3d points1, points2;
774  mpi->TraverseLineSegment(x1, y1, x2, y2, polyIds1, tValues1);
775  mpi->TraverseLineSegment(x1, y1, x2, y2, polyIds2);
776  mpi->TraverseLineSegment(x1, y1, x2, y2, polyIds3, points1);
777  mpi->TraverseLineSegment(x1, y1, x2, y2, polyIds4, tValues2, points2);
778  TS_ASSERT_EQUALS_VEC(a_expectedPolyIDs, polyIds1);
779  TS_ASSERT_EQUALS_VEC(a_expectedPolyIDs, polyIds2);
780  TS_ASSERT_EQUALS_VEC(a_expectedPolyIDs, polyIds3);
781  TS_ASSERT_EQUALS_VEC(a_expectedPolyIDs, polyIds4);
782  TS_ASSERT_EQUALS(polyIds1.size(), tValues1.size());
783  TS_ASSERT_EQUALS(polyIds1.size(), points1.size());
784  TS_ASSERT_EQUALS(polyIds1.size(), polyIds2.size());
785  TS_ASSERT_EQUALS(polyIds1.size(), polyIds3.size());
786  TS_ASSERT_EQUALS(polyIds1.size(), polyIds4.size());
787  TS_ASSERT_EQUALS(tValues1.size(), tValues2.size());
788  TS_ASSERT_EQUALS(points1.size(), points2.size());
789  const double kDelta = 1e-5;
790  TS_ASSERT_DELTA_VEC(a_expectedtValues, tValues1, kDelta);
791  TS_ASSERT_DELTA_VEC(a_expectedtValues, tValues2, kDelta);
792  TS_ASSERT_DELTA_VECPT3D(a_expectedPoints, points1, kDelta);
793  TS_ASSERT_DELTA_VECPT3D(a_expectedPoints, points2, kDelta);
794 } // iRunTest
795 
796 } // unnamed namespace
797 
802 //------------------------------------------------------------------------------
805 // (10,10)
806 // 3-------------2
807 // | |
808 // 0------------------1
809 // | |
810 // | 1 |
811 // | |
812 // 0-------------1
813 // (0,0)
815 //------------------------------------------------------------------------------
816 void GmMultiPolyIntersectorUnitTests::test1OutOut()
817 {
818  VecPt3d pts = {{0, 0, 0}, {10, 0, 0}, {10, 10, 0}, {0, 10, 0}};
819  VecInt2d polys = {{0, 1, 2, 3}};
820  VecInt expectedIds = {1, -1};
821  VecDbl expectedTvals = {0.0833333, 0.916667};
822  VecPt3d expectedPoints = {{0.0, 5.0, 0.0}, {10.0, 5.0, 0.0}};
823  iRunTest(-1, 5, 11, 5, pts, polys, expectedIds, expectedTvals, expectedPoints);
824 
825 } // GmMultiPolyIntersectorUnitTests::test1OutOut
826 //------------------------------------------------------------------------------
829 // (10,10)
830 // 3-------------2
831 // | |
832 // 0----------1 |
833 // | |
834 // | 1 |
835 // | |
836 // 0-------------1
837 // (0,0)
839 //------------------------------------------------------------------------------
840 void GmMultiPolyIntersectorUnitTests::test1OutIn()
841 {
842  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {10, 10, 0}, {0, 10, 0}};
843  VecInt2d polys{{0, 1, 2, 3}};
844  VecInt expectedIds{1, -1};
845  VecDbl expectedTvals{0.111111, 1.0};
846  VecPt3d expectedPoints = {{0.0, 5.0, 0.0}, {8.0, 5.0, 0.0}};
847  iRunTest(-1, 5, 8, 5, pts, polys, expectedIds, expectedTvals, expectedPoints);
848 
849 } // GmMultiPolyIntersectorUnitTests::test1OutIn
850 //------------------------------------------------------------------------------
853 // (10,10)
854 // 3-------------2
855 // | |
856 // | 0----------1
857 // | |
858 // | 1 |
859 // | |
860 // 0-------------1
861 // (0,0)
863 //------------------------------------------------------------------------------
864 void GmMultiPolyIntersectorUnitTests::test1InOut()
865 {
866  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {10, 10, 0}, {0, 10, 0}};
867  VecInt2d polys = {{0, 1, 2, 3}};
868  VecInt expectedIds{1, -1};
869  VecDbl expectedTvals{0.0, 0.833333};
870  VecPt3d expectedPoints = {{5.0, 5.0, 0.0}, {10.0, 5.0, 0.0}};
871  iRunTest(5, 5, 11, 5, pts, polys, expectedIds, expectedTvals, expectedPoints);
872 
873 } // GmMultiPolyIntersectorUnitTests::test1InOut
874 //------------------------------------------------------------------------------
877 // (10,10)
878 // 3-------------2
879 // | |
880 // | 0--------1 |
881 // | |
882 // | 1 |
883 // | |
884 // 0-------------1
885 // (0,0)
887 //------------------------------------------------------------------------------
888 void GmMultiPolyIntersectorUnitTests::test1InIn()
889 {
890  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {10, 10, 0}, {0, 10, 0}};
891  VecInt2d polys{{0, 1, 2, 3}};
892  VecInt expectedIds{1, -1};
893  VecDbl expectedTvals{0.0, 1.0};
894  VecPt3d expectedPoints = {{2.0, 5.0, 0.0}, {8.0, 5.0, 0.0}};
895  iRunTest(2, 5, 8, 5, pts, polys, expectedIds, expectedTvals, expectedPoints);
896 
897 } // GmMultiPolyIntersectorUnitTests::test1InIn
898 //------------------------------------------------------------------------------
901 // (10,10)
902 // 3-------------2
903 // | |
904 // 0-------------1
905 // | |
906 // | 1 |
907 // | |
908 // 0-------------1
909 // (0,0)
911 //------------------------------------------------------------------------------
912 void GmMultiPolyIntersectorUnitTests::test1OnOn()
913 {
914  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {10, 10, 0}, {0, 10, 0}};
915  VecInt2d polys{{0, 1, 2, 3}};
916  VecInt expectedIds{1, -1};
917  VecDbl expectedTvals{0.0, 1.0};
918  VecPt3d expectedPoints = {{0.0, 5.0, 0.0}, {10.0, 5.0, 0.0}};
919  iRunTest(0, 5, 10, 5, pts, polys, expectedIds, expectedTvals, expectedPoints);
920 
921 } // GmMultiPolyIntersectorUnitTests::test1OnOn
922 //------------------------------------------------------------------------------
925 // (10,10)
926 // 3-------------2
927 // | |
928 // 0------1 |
929 // | |
930 // | 1 |
931 // | |
932 // 0-------------1
933 // (0,0)
935 //------------------------------------------------------------------------------
936 void GmMultiPolyIntersectorUnitTests::test1OnIn()
937 {
938  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {10, 10, 0}, {0, 10, 0}};
939  VecInt2d polys{{0, 1, 2, 3}};
940  VecInt expectedIds{1, -1};
941  VecDbl expectedTvals{0.0, 1.0};
942  VecPt3d expectedPoints = {{0.0, 5.0, 0.0}, {5.0, 5.0, 0.0}};
943  iRunTest(0, 5, 5, 5, pts, polys, expectedIds, expectedTvals, expectedPoints);
944 
945 } // GmMultiPolyIntersectorUnitTests::test1OnIn
946 //------------------------------------------------------------------------------
949 // (10,10)
950 // 3-------------2
951 // | |
952 // | 0------1
953 // | |
954 // | 1 |
955 // | |
956 // 0-------------1
957 // (0,0)
959 //------------------------------------------------------------------------------
960 void GmMultiPolyIntersectorUnitTests::test1InOn()
961 {
962  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {10, 10, 0}, {0, 10, 0}};
963  VecInt2d polys{{0, 1, 2, 3}};
964  VecInt expectedIds{1, -1};
965  VecDbl expectedTvals{0.0, 1.0};
966  VecPt3d expectedPoints = {{5.0, 5.0, 0.0}, {10.0, 5.0, 0.0}};
967  iRunTest(5, 5, 10, 5, pts, polys, expectedIds, expectedTvals, expectedPoints);
968 
969 } // GmMultiPolyIntersectorUnitTests::test1InOn
970 //------------------------------------------------------------------------------
973 // (10,10)
974 // 3-------------2
975 // | |
976 // 0--1 |
977 // | 1 |
978 // | |
979 // | |
980 // 0-------------1
981 // (0,0)
983 //------------------------------------------------------------------------------
984 void GmMultiPolyIntersectorUnitTests::test1OutOn()
985 {
986  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {10, 10, 0}, {0, 10, 0}};
987  VecInt2d polys{{0, 1, 2, 3}};
988  VecInt expectedIds{1, -1};
989  VecDbl expectedTvals{1.0, 1.0};
990  VecPt3d expectedPoints = {{0.0, 5.0, 0.0}, {0.0, 5.0, 0.0}};
991  iRunTest(-1, 5, 0, 5, pts, polys, expectedIds, expectedTvals, expectedPoints);
992 
993 } // GmMultiPolyIntersectorUnitTests::test1OutOn
994 //------------------------------------------------------------------------------
997 // (10,10)
998 // 3-------------2
999 // | |
1000 // | 0--1
1001 // | 1 |
1002 // | |
1003 // | |
1004 // 0-------------1
1005 // (0,0)
1007 //------------------------------------------------------------------------------
1008 void GmMultiPolyIntersectorUnitTests::test1OnOut()
1009 {
1010  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {10, 10, 0}, {0, 10, 0}};
1011  VecInt2d polys{{0, 1, 2, 3}};
1012  VecInt expectedIds{1, -1};
1013  VecDbl expectedTvals{0.0, 0.0};
1014  VecPt3d expectedPoints = {{10.0, 5.0, 0.0}, {10.0, 5.0, 0.0}};
1015  iRunTest(10, 5, 11, 5, pts, polys, expectedIds, expectedTvals, expectedPoints);
1016 
1017 } // GmMultiPolyIntersectorUnitTests::test1OnOut
1018 //------------------------------------------------------------------------------
1021 // (10,10)
1022 // 3----0----1---2
1023 // | |
1024 // | |
1025 // | 1 |
1026 // | |
1027 // | |
1028 // 0-------------1
1029 // (0,0)
1031 //------------------------------------------------------------------------------
1032 void GmMultiPolyIntersectorUnitTests::test1EdgeInIn()
1033 {
1034  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {10, 10, 0}, {0, 10, 0}};
1035  VecInt2d polys{{0, 1, 2, 3}};
1036  VecInt expectedIds{1, -1};
1037  VecDbl expectedTvals{0.0, 1.0};
1038  VecPt3d expectedPoints = {{3.0, 10.0, 0.0}, {7.0, 10.0, 0.0}};
1039  iRunTest(3, 10, 7, 10, pts, polys, expectedIds, expectedTvals, expectedPoints);
1040 
1041 } // GmMultiPolyIntersectorUnitTests::test1EdgeInIn
1042 //------------------------------------------------------------------------------
1045 // (10,10)
1046 // 3|1-----------2|2
1047 // | |
1048 // | |
1049 // | 1 |
1050 // | |
1051 // | |
1052 // 0-------------1
1053 // (0,0)
1055 //------------------------------------------------------------------------------
1056 void GmMultiPolyIntersectorUnitTests::test1EdgePtPt()
1057 {
1058  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {10, 10, 0}, {0, 10, 0}};
1059  VecInt2d polys{{0, 1, 2, 3}};
1060  VecInt expectedIds{1, -1};
1061  VecDbl expectedTvals{0.0, 1.0};
1062  VecPt3d expectedPoints = {{0.0, 10.0, 0.0}, {10.0, 10.0, 0.0}};
1063  iRunTest(0, 10, 10, 10, pts, polys, expectedIds, expectedTvals, expectedPoints);
1064 
1065 } // GmMultiPolyIntersectorUnitTests::test1EdgePtPt
1066 //------------------------------------------------------------------------------
1069 // (10,10)
1070 // 1--3-------------2--2
1071 // | |
1072 // | |
1073 // | 1 |
1074 // | |
1075 // | |
1076 // 0-------------1
1077 // (0,0)
1079 //------------------------------------------------------------------------------
1080 void GmMultiPolyIntersectorUnitTests::test1EdgeOutOut()
1081 {
1082  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {10, 10, 0}, {0, 10, 0}};
1083  VecInt2d polys{{0, 1, 2, 3}};
1084  VecInt expectedIds{1, -1};
1085  VecDbl expectedTvals{0.0833333, 0.9166667};
1086  VecPt3d expectedPoints = {{10.0, 10.0, 0.0}, {0.0, 10.0, 0.0}};
1087  // iRunTest(-1, 10, 11, 10, pts, polys, expectedIds, expectedTvals,
1088  // expectedPoints); // doesn't work
1089  iRunTest(11, 10, -1, 10, pts, polys, expectedIds, expectedTvals, expectedPoints);
1090 
1091 } // GmMultiPolyIntersectorUnitTests::test1EdgeOutOut
1092 //------------------------------------------------------------------------------
1095 // (10,10)
1096 // 1--3------2------2
1097 // | |
1098 // | |
1099 // | 1 |
1100 // | |
1101 // | |
1102 // 0-------------1
1103 // (0,0)
1105 //------------------------------------------------------------------------------
1106 void GmMultiPolyIntersectorUnitTests::test1EdgeOutIn()
1107 {
1108  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {10, 10, 0}, {0, 10, 0}};
1109  VecInt2d polys{{0, 1, 2, 3}};
1110  VecInt expectedIds{1, -1};
1111  VecDbl expectedTvals{0.166667, 1.0};
1112  VecPt3d expectedPoints = {{0.0, 10.0, 0.0}, {5.0, 10.0, 0.0}};
1113  iRunTest(-1, 10, 5, 10, pts, polys, expectedIds, expectedTvals, expectedPoints);
1114  expectedTvals = {0.0, 5 / 6.0};
1115  expectedPoints = {{5.0, 10.0, 0.0}, {0.0, 10.0, 0.0}};
1116  iRunTest(5, 10, -1, 10, pts, polys, expectedIds, expectedTvals, expectedPoints);
1117  // iRunTest(-1, 0, 5, 0, pts, polys, expectedIds, expectedTvals,
1118  // expectedPoints); //works iRunTest(-1, 9.999999999999999, 5, 10, pts, polys,
1119  // expectedIds, expectedTvals, expectedPoints); //works
1120  expectedTvals = {1.0 / 3.0, 1.0};
1121  expectedPoints = {{10.0, 10.0, 0.0}, {0.0, 10.0, 0.0}};
1122  iRunTest(15, 10, 0, 10, pts, polys, expectedIds, expectedTvals, expectedPoints);
1123 } // GmMultiPolyIntersectorUnitTests::test1EdgeOutIn
1124 //------------------------------------------------------------------------------
1127 // (10,10)
1128 // 3------1------2--2
1129 // | |
1130 // | |
1131 // | 1 |
1132 // | |
1133 // | |
1134 // 0-------------1
1135 // (0,0)
1137 //------------------------------------------------------------------------------
1138 void GmMultiPolyIntersectorUnitTests::test1EdgeInOut()
1139 {
1140  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {10, 10, 0}, {0, 10, 0}};
1141  VecInt2d polys{{0, 1, 2, 3}};
1142  VecInt expectedIds{1, -1};
1143  VecDbl expectedTvals{0.0, 0.833333};
1144  VecPt3d expectedPoints = {{5.0, 10.0, 0.0}, {10.0, 10.0, 0.0}};
1145  iRunTest(5, 10, 11, 10, pts, polys, expectedIds, expectedTvals,
1146  expectedPoints); // works
1147  // iRunTest(11, 10, 5, 10, pts, polys, expectedIds, expectedTvals,
1148  // expectedPoints); // doesn't work
1149 
1150 } // GmMultiPolyIntersectorUnitTests::test1EdgeInOut
1151 //------------------------------------------------------------------------------
1154 // (10,10)
1155 // 1-2|3-------------2
1156 // | |
1157 // | |
1158 // | 1 |
1159 // | |
1160 // | |
1161 // 0-------------1
1162 // (0,0)
1164 //------------------------------------------------------------------------------
1165 void GmMultiPolyIntersectorUnitTests::test1OutPt()
1166 {
1167  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {10, 10, 0}, {0, 10, 0}};
1168  VecInt2d polys{{0, 1, 2, 3}};
1169  VecInt expectedIds{1, -1};
1170  VecDbl expectedTvals{1.0, 1.0};
1171  VecPt3d expectedPoints = {{0.0, 10.0, 0.0}, {0.0, 10.0, 0.0}};
1172  iRunTest(-1, 10, 0, 10, pts, polys, expectedIds, expectedTvals, expectedPoints);
1173 
1174 } // GmMultiPolyIntersectorUnitTests::test1OutPt
1175 //------------------------------------------------------------------------------
1178 // 2
1179 // / (10,10)
1180 // 3-------------2
1181 // /| |
1182 // 1 | |
1183 // | 1 |
1184 // | |
1185 // | |
1186 // 0-------------1
1187 // (0,0)
1189 //------------------------------------------------------------------------------
1190 void GmMultiPolyIntersectorUnitTests::test1OutPtOut()
1191 {
1192  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {10, 10, 0}, {0, 10, 0}};
1193  VecInt2d polys{{0, 1, 2, 3}};
1194  VecInt expectedIds{1, -1};
1195  VecDbl expectedTvals{0.5, 0.5};
1196  VecPt3d expectedPoints = {{0.0, 10.0, 0.0}, {0.0, 10.0, 0.0}};
1197  iRunTest(-1, 9, 1, 11, pts, polys, expectedIds, expectedTvals, expectedPoints);
1198 
1199 } // GmMultiPolyIntersectorUnitTests::test1OutPtOut
1200 //------------------------------------------------------------------------------
1203 // 2
1204 // / (10,10)
1205 // 1 3-------------2
1206 // | |
1207 // | |
1208 // | 1 |
1209 // | |
1210 // | |
1211 // 0-------------1
1212 // (0,0)
1214 //------------------------------------------------------------------------------
1215 void GmMultiPolyIntersectorUnitTests::test1AllOut()
1216 {
1217  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {10, 10, 0}, {0, 10, 0}};
1218  VecInt2d polys{{0, 1, 2, 3}};
1219  VecInt expectedIds;
1220  VecDbl expectedTvals;
1221  VecPt3d expectedPoints = {};
1222  iRunTest(-1, 10, 0, 11, pts, polys, expectedIds, expectedTvals, expectedPoints);
1223 
1224 } // GmMultiPolyIntersectorUnitTests::test1AllOut
1225 //------------------------------------------------------------------------------
1228 // (10,10)
1229 // 3|1-----2------2
1230 // | |
1231 // | |
1232 // | 1 |
1233 // | |
1234 // | |
1235 // 0-------------1
1236 // (0,0)
1238 //------------------------------------------------------------------------------
1239 void GmMultiPolyIntersectorUnitTests::test1PtIn()
1240 {
1241  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {10, 10, 0}, {0, 10, 0}};
1242  VecInt2d polys{{0, 1, 2, 3}};
1243  VecInt expectedIds{1, -1};
1244  VecDbl expectedTvals{0.0, 1.0};
1245  VecPt3d expectedPoints = {{0.0, 10.0, 0.0}, {5.0, 10.0, 0.0}};
1246  iRunTest(0, 10, 5, 10, pts, polys, expectedIds, expectedTvals, expectedPoints);
1247 
1248 } // GmMultiPolyIntersectorUnitTests::test1PtIn
1249 //------------------------------------------------------------------------------
1252 // (10,10)
1253 // 3|------1-----2|2
1254 // | |
1255 // | |
1256 // | 1 |
1257 // | |
1258 // | |
1259 // 0-------------1
1260 // (0,0)
1262 //------------------------------------------------------------------------------
1263 void GmMultiPolyIntersectorUnitTests::test1InPt()
1264 {
1265  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {10, 10, 0}, {0, 10, 0}};
1266  VecInt2d polys{{0, 1, 2, 3}};
1267  VecInt expectedIds{1, -1};
1268  VecDbl expectedTvals{0.0, 1.0};
1269  VecPt3d expectedPoints = {{5.0, 10.0, 0.0}, {10.0, 10.0, 0.0}};
1270  iRunTest(5, 10, 10, 10, pts, polys, expectedIds, expectedTvals, expectedPoints);
1271 
1272 } // GmMultiPolyIntersectorUnitTests::test1InPt
1273 //------------------------------------------------------------------------------
1276 // (0,10)
1277 // 3-------------4-------------5
1278 // | | |
1279 // 0-------------1 |
1280 // | | |
1281 // | 1 | 2 |
1282 // | | |
1283 // 0-------------1-------------2
1284 // (0,0) (20,0)
1286 //------------------------------------------------------------------------------
1287 void GmMultiPolyIntersectorUnitTests::test2OnOn()
1288 {
1289  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {20, 0, 0}, {0, 10, 0}, {10, 10, 0}, {20, 10, 0}};
1290  VecInt2d polys{{0, 1, 4, 3}};
1291  VecInt expectedIds{1, -1}; // old: (1)
1292  VecDbl expectedTvals{0.0, 1.0};
1293  VecPt3d expectedPoints = {{0.0, 5.0, 0.0}, {10.0, 5.0, 0.0}};
1294  iRunTest(0, 5, 10, 5, pts, polys, expectedIds, expectedTvals, expectedPoints);
1295 
1296 } // GmMultiPolyIntersectorUnitTests::test2OnOn
1297 //------------------------------------------------------------------------------
1300 // (0,10)
1301 // 3-------------4-------------5
1302 // | | |
1303 // | 0-------1 |
1304 // | | |
1305 // | 1 | 2 |
1306 // | | |
1307 // 0-------------1-------------2
1308 // (0,0) (20,0)
1310 //------------------------------------------------------------------------------
1311 void GmMultiPolyIntersectorUnitTests::test2InOn()
1312 {
1313  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {20, 0, 0}, {0, 10, 0}, {10, 10, 0}, {20, 10, 0}};
1314  VecInt2d polys{{0, 1, 4, 3}};
1315  VecInt expectedIds{1, -1}; // old: (1)
1316  VecDbl expectedTvals{0.0, 1.0};
1317  VecPt3d expectedPoints = {{5.0, 5.0, 0.0}, {10.0, 5.0, 0.0}};
1318  iRunTest(5, 5, 10, 5, pts, polys, expectedIds, expectedTvals, expectedPoints);
1319 
1320 } // GmMultiPolyIntersectorUnitTests::test2InOn
1321 //------------------------------------------------------------------------------
1324 // (0,10)
1325 // 3-------------4-------------5
1326 // | | |
1327 // | 0-------1 |
1328 // | | |
1329 // | 1 | 2 |
1330 // | | |
1331 // 0-------------1-------------2
1332 // (0,0) (20,0)
1334 //------------------------------------------------------------------------------
1335 void GmMultiPolyIntersectorUnitTests::test2OnIn()
1336 {
1337  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {20, 0, 0}, {0, 10, 0}, {10, 10, 0}, {20, 10, 0}};
1338  VecInt2d polys = {{0, 1, 4, 3}, {1, 2, 5, 4}};
1339  VecInt expectedIds{1, -1}; // old: (1)
1340  VecDbl expectedTvals{0.0, 1.0};
1341  VecPt3d expectedPoints = {{5.0, 5.0, 0.0}, {10.0, 5.0, 0.0}};
1342  iRunTest(5, 5, 10, 5, pts, polys, expectedIds, expectedTvals, expectedPoints);
1343 
1344 } // GmMultiPolyIntersectorUnitTests::test2OnIn
1345 //------------------------------------------------------------------------------
1348 // (0,10)
1349 // 3-------------4-------------5
1350 // | | |
1351 // 0--------------------------------1
1352 // | | |
1353 // | 1 | 2 |
1354 // | | |
1355 // 0-------------1-------------2
1356 // (0,0) (20,0)
1358 //------------------------------------------------------------------------------
1359 void GmMultiPolyIntersectorUnitTests::test2OutOut()
1360 {
1361  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {20, 0, 0}, {0, 10, 0}, {10, 10, 0}, {20, 10, 0}};
1362  VecInt2d polys = {{0, 1, 4, 3}, {1, 2, 5, 4}};
1363  VecInt expectedIds{1, 2, -1}; // old: (1)(2)
1364  VecDbl expectedTvals{0.0454545, 0.5, 0.954545};
1365  VecPt3d expectedPoints = {{0.0, 5.0, 0.0}, {10.0, 5.0, 0.0}, {20.0, 5.0, 0.0}};
1366  iRunTest(-1, 5, 21, 5, pts, polys, expectedIds, expectedTvals, expectedPoints);
1367 
1368 } // GmMultiPolyIntersectorUnitTests::test2OutOut
1369 //------------------------------------------------------------------------------
1372 // (0,10)
1373 // 3-------------4-------------5
1374 // | | |
1375 // 0------------------------1 |
1376 // | | |
1377 // | 1 | 2 |
1378 // | | |
1379 // 0-------------1-------------2
1380 // (0,0) (20,0)
1382 //------------------------------------------------------------------------------
1383 void GmMultiPolyIntersectorUnitTests::test2OutIn()
1384 {
1385  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {20, 0, 0}, {0, 10, 0}, {10, 10, 0}, {20, 10, 0}};
1386  VecInt2d polys = {{{0, 1, 4, 3}}, {1, 2, 5, 4}};
1387  VecInt expectedIds{1, 2, -1}; // old: (1)(2)
1388  VecDbl expectedTvals{0.0625, 0.6875, 1.0};
1389  VecPt3d expectedPoints = {{0.0, 5.0, 0.0}, {10.0, 5.0, 0.0}, {15.0, 5.0, 0.0}};
1390  iRunTest(-1, 5, 15, 5, pts, polys, expectedIds, expectedTvals, expectedPoints);
1391 
1392 } // GmMultiPolyIntersectorUnitTests::test2OutIn
1393 //------------------------------------------------------------------------------
1396 // (0,10)
1397 // 3-------------4-------------5
1398 // | | |
1399 // | 0---------------------1
1400 // | | |
1401 // | 1 | 2 |
1402 // | | |
1403 // 0-------------1-------------2
1404 // (0,0) (20,0)
1406 //------------------------------------------------------------------------------
1407 void GmMultiPolyIntersectorUnitTests::test2InOut()
1408 {
1409  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {20, 0, 0}, {0, 10, 0}, {10, 10, 0}, {20, 10, 0}};
1410  VecInt2d polys = {{0, 1, 4, 3}, {1, 2, 5, 4}};
1411  VecInt expectedIds{1, 2, -1}; // old: (1)(2)
1412  VecDbl expectedTvals{0.0, 0.3125, 0.9375};
1413  VecPt3d expectedPoints = {{5.0, 5.0, 0.0}, {10.0, 5.0, 0.0}, {20.0, 5.0, 0.0}};
1414  iRunTest(5, 5, 21, 5, pts, polys, expectedIds, expectedTvals, expectedPoints);
1415 
1416 } // GmMultiPolyIntersectorUnitTests::test2InOut
1417 //------------------------------------------------------------------------------
1420 // (0,10)
1421 // 3-------------4-------------5
1422 // | | |
1423 // | 0-------------1 |
1424 // | | |
1425 // | 1 | 2 |
1426 // | | |
1427 // 0-------------1-------------2
1428 // (0,0) (20,0)
1430 //------------------------------------------------------------------------------
1431 void GmMultiPolyIntersectorUnitTests::test2InIn()
1432 {
1433  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {20, 0, 0}, {0, 10, 0}, {10, 10, 0}, {20, 10, 0}};
1434  VecInt2d polys = {{0, 1, 4, 3}, {1, 2, 5, 4}};
1435  VecInt expectedIds{1, 2, -1}; // old: (1)(2)
1436  VecDbl expectedTvals{0.0, 0.5, 1.0};
1437  VecPt3d expectedPoints = {{5.0, 5.0, 0.0}, {10.0, 5.0, 0.0}, {15.0, 5.0, 0.0}};
1438  iRunTest(5, 5, 15, 5, pts, polys, expectedIds, expectedTvals, expectedPoints);
1439 } // GmMultiPolyIntersectorUnitTests::test2InIn
1440 //------------------------------------------------------------------------------
1443 // (0,10)
1444 // 3------1-----2|4-------------5
1445 // | | |
1446 // | | |
1447 // | 1 | 2 |
1448 // | | |
1449 // | | |
1450 // 0-------------1-------------2
1451 // (0,0) (20,0)
1453 //------------------------------------------------------------------------------
1454 void GmMultiPolyIntersectorUnitTests::test2InPt()
1455 {
1456  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {20, 0, 0}, {0, 10, 0}, {10, 10, 0}, {20, 10, 0}};
1457  VecInt2d polys = {{0, 1, 4, 3}, {1, 2, 5, 4}};
1458  VecInt expectedIds{1, -1}; // old: (1)(2)
1459  VecDbl expectedTvals{0.0, 1.0};
1460  VecPt3d expectedPoints = {{5.0, 10.0, 0.0}, {10.0, 10.0, 0.0}};
1461  iRunTest(5, 10, 10, 10, pts, polys, expectedIds, expectedTvals, expectedPoints);
1462 } // GmMultiPolyIntersectorUnitTests::test2InPt
1463 //------------------------------------------------------------------------------
1466 // (0,10)
1467 // 3------------4|1-----2------5
1468 // | | |
1469 // | | |
1470 // | 1 | 2 |
1471 // | | |
1472 // | | |
1473 // 0-------------1-------------2
1474 // (0,0) (20,0)
1476 //------------------------------------------------------------------------------
1477 void GmMultiPolyIntersectorUnitTests::test2PtIn()
1478 {
1479  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {20, 0, 0}, {0, 10, 0}, {10, 10, 0}, {20, 10, 0}};
1480  VecInt2d polys = {{0, 1, 4, 3}, {1, 2, 5, 4}};
1481  VecInt expectedIds{2, -1}; // old: (1)(2)
1482  VecDbl expectedTvals{0.0, 1.0};
1483  VecPt3d expectedPoints = {{10.0, 10.0, 0.0}, {15.0, 10.0, 0.0}};
1484  iRunTest(10, 10, 15, 10, pts, polys, expectedIds, expectedTvals, expectedPoints);
1485 } // GmMultiPolyIntersectorUnitTests::test2PtIn
1486 //------------------------------------------------------------------------------
1489 // (0,10)
1490 // 3------1-----4|-------------5 2
1491 // | | |
1492 // | | |
1493 // | 1 | 2 |
1494 // | | |
1495 // | | |
1496 // 0-------------1-------------2
1497 // (0,0) (20,0)
1499 //------------------------------------------------------------------------------
1500 void GmMultiPolyIntersectorUnitTests::test2InEdgePt()
1501 {
1502  // The comment below is not true. Check
1503  // GmMultiPolyIntersectorImpl::GmMultiPolyIntersectorImpl to see that we don't
1504  // set z's to 0.0 and this test works. We are using Pt3d as a 2D boost
1505  // geometry so z's don't come into play.
1506  // // The non-equal z values would cause this test to fail but now we
1507  // // set them all to 0.0.
1508  VecPt3d pts{{0, 0, 100}, {10, 0, 110}, {20, 0, 105}, {0, 10, 104}, {10, 10, 103}, {20, 10, 106}};
1509  VecInt2d polys = {{0, 1, 4, 3}, {1, 2, 5, 4}};
1510  VecInt expectedIds{1, 2, -1};
1511  VecDbl expectedTvals = {0.0, 1 / 3.0, 1};
1512  VecPt3d expectedPoints = {{5.0, 10.0, 0.0}, {10.0, 10.0, 0.0}, {20.0, 10.0, 0.0}};
1513  iRunTest(5, 10, 20, 10, pts, polys, expectedIds, expectedTvals, expectedPoints);
1514  expectedIds = {2, 1, -1};
1515  expectedPoints = {{15.0, 10.0, 0.0}, {10.0, 10.0, 0.0}, {0.0, 10.0, 0.0}};
1516  iRunTest(15, 10, 0, 10, pts, polys, expectedIds, expectedTvals, expectedPoints);
1517 } // GmMultiPolyIntersectorUnitTests::test2InEdgePt
1518 //------------------------------------------------------------------------------
1521 // (0,10)
1522 // 3-------------4-------------5
1523 // | | |
1524 // | | |
1525 // | 1|1 | 2 |
1526 // | | |
1527 // | | |
1528 // 0------------2|1------------2
1529 // (0,0) (20,0)
1531 //------------------------------------------------------------------------------
1532 void GmMultiPolyIntersectorUnitTests::testCorners()
1533 {
1534  VecPt3d pts{{0, 0, 100}, {10, 0, 110}, {20, 0, 105}, {0, 10, 104}, {10, 10, 103}, {20, 10, 106}};
1535  VecInt2d polys = {{0, 1, 4, 3}, {1, 2, 5, 4}};
1536  VecInt expectedIds{1, -1};
1537  VecDbl expectedTvals = {0.0, 1};
1538  VecPt3d expectedPoints = {{5.0, 5.0, 0.0}, {10.0, 0.0, 0.0}};
1539  iRunTest(5, 5, 10, 0, pts, polys, expectedIds, expectedTvals, expectedPoints);
1540  expectedIds = {2, -1};
1541  expectedPoints = {{15.0, 5.0, 0.0}, {10.0, 10.0, 0.0}};
1542  iRunTest(15, 5, 10, 10, pts, polys, expectedIds, expectedTvals, expectedPoints);
1543 } // GmMultiPolyIntersectorUnitTests::testCorners
1544 //------------------------------------------------------------------------------
1547 // Pt 0: (104.346,-300.604,48.558)
1548 // Pt 1: (105.148,-298.88,48.225)
1549 // Pt 2: (105.994,-297.142,47.225)
1550 // Pt 3: (110.439,-299.669,48.533)
1551 // Pt 4: (109.543,-301.391,47.2)
1552 // Pt 5: (108.738,-303.082,47.867)
1553 // Pt 6: (113.06,-305.811,47.175)
1554 // Pt 7: (113.886,-304.089,48.175)
1555 // 2-------------3
1556 // | | \
1557 // | | \
1558 // | 2 | \
1559 // | | 3 \
1560 // | | \
1561 // 1-------------4-------------7
1562 // | | |
1563 // | | |
1564 // | 1 | 4 |
1565 // | | |
1566 // | | |
1567 // 0-------------5-------------6
1568 // (0,0) (20,0)
1570 //------------------------------------------------------------------------------
1571 void GmMultiPolyIntersectorUnitTests::testQuadCorners()
1572 {
1573  VecPt3d pts{{104.346, -300.604, 48.558}, {105.148, -298.88, 48.225}, {105.994, -297.142, 47.225},
1574  {110.439, -299.669, 48.533}, {109.543, -301.391, 47.2}, {108.738, -303.082, 47.867},
1575  {113.06, -305.811, 47.175}, {113.886, -304.089, 48.175}};
1576  VecInt2d polys = {{0, 5, 4, 1}, {1, 4, 3, 2}, {4, 7, 3}, {5, 6, 7, 4}};
1577  VecInt expectedIds{2, -1};
1578  VecDbl expectedTvals = {0.0, 1};
1579  VecPt3d expectedPoints = {{107.769, -299.267, 0.0}, {109.543, -301.391, 0.0}};
1580  iRunTest(107.769, -299.267, 109.543, -301.391, pts, polys, expectedIds, expectedTvals,
1581  expectedPoints);
1582  expectedIds = {4, -1};
1583  expectedPoints = {{109.543, -301.391, 0.0}, {111.302, -303.601, 0.0}};
1584  iRunTest(109.543, -301.391, 111.302, -303.601, pts, polys, expectedIds, expectedTvals,
1585  expectedPoints);
1586 } // GmMultiPolyIntersectorUnitTests::testQuadCorners
1587 //------------------------------------------------------------------------------
1590 // Pt 0: (263.313, -361.915, 47.375)
1591 // Pt 1: (263.914, -360.497, 46.375)
1592 // Pt 2: (264.582, -358.729, 48.375)
1593 // Pt 3: (269.892, -359.609, 48.35)
1594 // Pt 4: (269.228, -361.033, 46.35)
1595 // Pt 5: (268.569, -362.502, 47.35)
1596 // Pt 6: (273.694, -363.319, 47.325)
1597 // Pt 7: (274.372, -361.835, 46.325)
1598 // Pt 8: (275.054, -360.401, 48.325)
1599 // 2-------------3-------------8
1600 // | | |
1601 // | | |
1602 // | 2 | 3 |
1603 // | | |
1604 // | | |
1605 // 1------p0---p1|4------------7
1606 // | | |
1607 // | | |
1608 // | 1 | 4 |
1609 // | | |
1610 // | | |
1611 // 0-------------5-------------6
1613 //------------------------------------------------------------------------------
1614 void GmMultiPolyIntersectorUnitTests::testQuadCornersBug12396()
1615 {
1616  VecPt3d pts{
1617  {263.313, -361.915, 47.375}, {263.914, -360.497, 46.375}, {264.582, -358.729, 48.375},
1618  {269.892, -359.609, 48.35}, {269.228, -361.033, 46.35}, {268.569, -362.502, 47.35},
1619  {273.694, -363.319, 47.325}, {274.372, -361.835, 46.325}, {275.054, -360.401, 48.325}};
1620  VecInt2d polys = {{0, 5, 4, 1}, {1, 4, 3, 2}, {4, 7, 8, 3}, {5, 6, 7, 4}};
1621  VecInt expectedIds{2, -1};
1622  VecDbl expectedTvals = {0.0, 1};
1623  VecPt3d expectedPoints = {{266.571, -360.765, 0.0}, {269.228, -361.033, 46.35}};
1624  iRunTest(266.57100000000003, -360.76499999999999, 269.22800000000001, -361.03300000000002, pts,
1625  polys, expectedIds, expectedTvals, expectedPoints);
1626 } // GmMultiPolyIntersectorUnitTests::testQuadCornersBug12396
1627 //------------------------------------------------------------------------------
1630 // (0,20)
1631 // 3-------------2
1632 // | 1 |
1633 // | \|
1634 // | 1 \
1635 // | |\
1636 // | | \
1637 // 0-------------1--\----------6
1638 // | \ |
1639 // | 2 |
1640 // | |
1641 // | 2 |
1642 // | |
1643 // 4-------------5
1644 // (0,0) (20,0)
1646 //------------------------------------------------------------------------------
1647 void GmMultiPolyIntersectorUnitTests::test2InOutIn()
1648 {
1649  VecPt3d pts{{0, 10, 0}, {10, 10, 0}, {10, 20, 0}, {0, 20, 0},
1650  {10, 0, 0}, {20, 0, 0}, {20, 10, 0}};
1651  VecInt2d polys = {{0, 1, 2, 3}, {4, 5, 6, 1}};
1652  VecInt expectedIds = {1, -1, 2, -1}; // old: (1)(2)
1653  VecDbl expectedTvals = {0.0, 0.2, 0.8, 1.0};
1654  VecPt3d expectedPoints = {
1655  {8.0, 18.0, 0.0}, {10.0, 16.0, 0.0}, {16.0, 10.0, 0.0}, {18.0, 8.0, 0.0}};
1656  iRunTest(8, 18, 18, 8, pts, polys, expectedIds, expectedTvals, expectedPoints);
1657 } // GmMultiPolyIntersectorUnitTests::test2InOutIn
1658 //------------------------------------------------------------------------------
1662 //
1663 // (0, 0)
1664 // 0-------------1-------------2
1665 // |\ 4 /|\ 8 /|
1666 // | \ 1 / | \ / |
1667 // | \ / | \ / |
1668 // | 1 3 3 | 5 4 7 |
1669 // | / \ | / \ |
1670 // | / \ | / 2 \ |
1671 // |/ 2 \|/ 6 \|
1672 // 5-------------6-------------7
1673 // (20, -10)
1675 //------------------------------------------------------------------------------
1676 void GmMultiPolyIntersectorUnitTests::testInsideToInside()
1677 {
1678  VecPt3d pts;
1679  VecInt2d polys;
1680  trBuildGridTrianglePolys(1, 2, pts, polys);
1681 
1682  VecInt expectedIds{4, 3, 5, 6, -1};
1683  VecDbl expectedTvals{0.0, 0.166666, 0.5, 0.833333, 1.0};
1684  VecPt3d expectedPoints = {{5.0, -2.5, 0.0},
1685  {6.6666666666667, -3.333333333333, 0.0},
1686  {10.0, -5.0, 0.0},
1687  {13.333333333333, -6.666666666667, 0.0},
1688  {15.0, -7.5, 0.0}};
1689  iRunTest(5, -2.5, 15, -7.5, pts, polys, expectedIds, expectedTvals, expectedPoints);
1690 } // GmMultiPolyIntersectorUnitTests::testInsideToInside
1691 //------------------------------------------------------------------------------
1695 //
1696 // (0, 0)
1697 // 1 0-------------1-------------2
1698 // |\ 4 /|\ 8 /|
1699 // | \ / | \ / |
1700 // | \ / | \ / |
1701 // | 1 3 3 | 5 4 7 |
1702 // | / \ | / \ |
1703 // | / \ | / \ |
1704 // |/ 2 \|/ 6 \|
1705 // 5-------------6-------------7 2
1706 // (20, -10)
1708 //------------------------------------------------------------------------------
1709 void GmMultiPolyIntersectorUnitTests::testOutsideToOutside()
1710 {
1711  VecPt3d pts;
1712  VecInt2d polys;
1713  trBuildGridTrianglePolys(1, 2, pts, polys);
1714 
1715  VecInt expectedIds{1, 4, 3, 5, 6, 7, -1};
1716  VecDbl expectedTvals{0.0454545, 0.0833333, 0.34375, 0.5, 0.65625, 0.916667, 0.954545};
1717  VecPt3d expectedPoints = {{0.0, -0.454545454545, 0.0}, {0.8333333333333, -0.833333333333, 0.0},
1718  {6.5625, -3.4375, 0.0}, {10.0, -5.0, 0.0},
1719  {13.4375, -6.5625, 0.0}, {19.166666666667, -9.166666666667, 0.0},
1720  {20.0, -9.545454545455, 0.0}};
1721  iRunTest(-1, 0, 21, -10, pts, polys, expectedIds, expectedTvals, expectedPoints);
1722 } // GmMultiPolyIntersectorUnitTests::testOutsideToOutside
1723 //------------------------------------------------------------------------------
1727 //
1728 // 1
1729 //(0,0) /
1730 // 0-------------1-------------2
1731 // /|\ 4 /|\ 8 /|
1732 // 2 | \ / | \ / |
1733 // | \ / | \ / |
1734 // | 1 3 3 | 5 4 7 |
1735 // | / \ | / \ |
1736 // | / \ | / \ |
1737 // |/ 2 \|/ 6 \|
1738 // 5-------------6-------------7 2
1739 // (20, -10)
1741 //------------------------------------------------------------------------------
1742 void GmMultiPolyIntersectorUnitTests::testTouchesVertex()
1743 {
1744  VecPt3d pts;
1745  VecInt2d polys;
1746  trBuildGridTrianglePolys(1, 2, pts, polys);
1747  // SurfaceIter crashes on this. We return no intersection.
1748  VecInt expectedIds;
1749  VecDbl expectedTvals;
1750  VecPt3d expectedPoints = {};
1751  iRunTest(1, 1, -1, -1, pts, polys, expectedIds, expectedTvals, expectedPoints);
1752 } // GmMultiPolyIntersectorUnitTests::testTouchesVertex
1753 //------------------------------------------------------------------------------
1757 //
1758 // (0, 0)
1759 // 0-------------1-------------2
1760 // 1 |\ 4 /|\ 8 /|
1761 // \ | \ / | \ / |
1762 // 2| \ / | \ / |
1763 // | 1 3 3 | 5 4 7 |
1764 // | / \ | / \ |
1765 // | / \ | / \ |
1766 // |/ 2 \|/ 6 \|
1767 // 5-------------6-------------7 2
1768 // (20, -10)
1770 //------------------------------------------------------------------------------
1771 void GmMultiPolyIntersectorUnitTests::testTouchesEdge()
1772 {
1773 #ifdef __linux__
1774  TS_SKIP("GREENBUILD: This test does not pass on Linux builds.");
1775 #endif
1776  VecPt3d pts;
1777  VecInt2d polys;
1778  trBuildGridTrianglePolys(1, 2, pts, polys);
1779  VecInt expectedIds{1, -1};
1780  VecDbl expectedTvals{1.0, 1.0};
1781  VecPt3d expectedPoints = {{0.0, -2.0, 0.0}, {0.0, -2.0, 0.0}};
1782  iRunTest(-1, -1, 0, -2, pts, polys, expectedIds, expectedTvals, expectedPoints);
1783 } // GmMultiPolyIntersectorUnitTests::testTouchesEdge
1784 //------------------------------------------------------------------------------
1788 //
1789 // (0, 0)
1790 // +-------------+-------------+-------------+
1791 // |\ 4 /|\ 8 /|\ 12 /|
1792 // | \ / | \ / | \ / |
1793 // | \ / | \ / | \ / |
1794 // | 1 x 3 | 5 x 7 | 9 x 11 |
1795 // | / 1 | / \ | / \ |
1796 // | / \ | / \ | / \ |
1797 // |/ 2 \|/ 6 \|/ 10 \|
1798 // +-------------+-------------+-------------+
1799 // |\ 16 /|\ 20 /|\ 24 /|
1800 // | \ / | \ / | \ / |
1801 // | \ / | \ / | \ / |
1802 // | 13 x 15 | 17 x 19 | 21 x 23 |
1803 // | / \ | / \ | / \ |
1804 // | / \ | / \ | / \ |
1805 // |/ 14 \|/ 18 \|/ 22 \|
1806 // +-------------+-------------+-------------+
1807 // |\ 28 /|\ 32 /|\ 36 /|
1808 // | \ / | \ / | \ / |
1809 // | \ / | \ / | 2 / |
1810 // | 25 x 27 | 29 x 31 | 33 x 35 |
1811 // | / \ | / \ | / \ |
1812 // | / \ | / \ | / \ |
1813 // |/ 26 \|/ 30 \|/ 34 \|
1814 // +-------------+-------------+-------------+
1815 // (30, -30)
1817 //------------------------------------------------------------------------------
1818 void GmMultiPolyIntersectorUnitTests::testAlongEdgesInsideToInside()
1819 {
1820  // TS_FAIL("GmMultiPolyIntersectorUnitTests::testAlongEdgesInsideToInside");
1821 
1822  VecPt3d pts;
1823  VecInt2d polys;
1824  trBuildGridTrianglePolys(3, 3, pts, polys);
1825 
1826  // MfMapLayerUGridImp::TraverseLineSegment results
1827  // VecInt expectedIds = {3,17,18,33,-1};
1828  // VecDbl expectedTvals = {0.0,0.22222,0.5,0.777778,1.0};
1829  VecInt expectedIds{2, 17, 18, 33, -1};
1830  VecDbl expectedTvals{0.0, 0.22222, 0.5, 0.777778, 1.0};
1831  VecPt3d expectedPoints = {{6.0, -6.0, 0.0},
1832  {10.0, -10.0, 0.0},
1833  {15.0, -15.0, 0.0},
1834  {20.0, -20.0, 0.0},
1835  {24.0, -24.0, 0.0}};
1836  iRunTest(6, -6, 24, -24, pts, polys, expectedIds, expectedTvals, expectedPoints);
1837 
1838 } // GmMultiPolyIntersectorUnitTests::testAlongEdgesInsideToInside
1839 //------------------------------------------------------------------------------
1843 //
1844 // (0, 0)
1845 // 0-------------1-------------2-------------3
1846 // |\ 4 /|\ 8 /|\ 12 /|
1847 // | \ / | \ / | \ / |
1848 // | \ / | \ / | \ / |
1849 // | 1 12 3 | 5 13 7 | 9 14 11 |
1850 // | / \ | / \ | / \ |
1851 // | / \ | / \ | / \ |
1852 // |/ 2 \|/ 6 \|/ 10 \|
1853 // 1 4-------------5-------------6-------------7 2
1854 // |\ 16 /|\ 20 /|\ 24 /|
1855 // | \ / | \ / | \ / |
1856 // | \ / | \ / | \ / |
1857 // | 13 15 15 | 17 16 19 | 21 17 23 |
1858 // | / \ | / \ | / \ |
1859 // | / \ | / \ | / \ |
1860 // |/ 14 \|/ 18 \|/ 22 \|
1861 // 8-------------9------------10------------11
1862 // (30, -20)
1864 //------------------------------------------------------------------------------
1865 void GmMultiPolyIntersectorUnitTests::testAlongEdgesOutsideToOutside()
1866 {
1867  VecPt3d pts;
1868  VecInt2d polys;
1869  trBuildGridTrianglePolys(2, 3, pts, polys);
1870 
1871  // VecInt expectedIds = {16,20,24,23,-1}; SurfaceIter results
1872  // MfMapLayerUGridImp::TraverseLineSegment results:
1873  VecInt expectedIds{16, 20, 24, -1};
1874  VecDbl expectedTvals{0.016129032258064516, 0.33870967741935482, 0.66129032258064513,
1875  0.98387096774193550};
1876  VecPt3d expectedPoints = {
1877  {0.0, -10.0, 0.0}, {10.0, -10.0, 0.0}, {20.0, -10.0, 0.0}, {30.0, -10.0, 0.0}};
1878  iRunTest(-0.5, -10, 30.5, -10, pts, polys, expectedIds, expectedTvals, expectedPoints);
1879 } // GmMultiPolyIntersectorUnitTests::testAlongEdgesOutsideToOutside
1880 //------------------------------------------------------------------------------
1884 //
1885 // (0, 0)
1886 // +-------------+-------------+
1887 // |\ 4 /|\ 8 /|
1888 // | \ / | \ / |
1889 // | \ / 1 | \ / |
1890 // | 1 x 3 | 5 x 7 |
1891 // | / \ | / \ | 2
1892 // | / \ | / \ |
1893 // |/ 2 \|/ 6 \|
1894 // +-------------+-------------+
1895 // (20, -10)
1897 //------------------------------------------------------------------------------
1898 void GmMultiPolyIntersectorUnitTests::testEdgeThroughOppositeVertexAtAngle()
1899 {
1900  // TS_FAIL("GmMultiPolyIntersectorUnitTests::testEdgeThroughOppositeVertexAtAngle");
1901 
1902  VecPt3d pts;
1903  VecInt2d polys;
1904  trBuildGridTrianglePolys(1, 2, pts, polys);
1905 
1906  // MfMapLayerUGridImp::TraverseLineSegment results
1907  // VecInt expectedIds = {3,5,7,-1};
1908  // VecDbl expectedTvals = {0.0,0.14285714285714288,0.5,0.85714285714285721};
1909  VecInt expectedIds{3, 5, 7, -1};
1910  VecDbl expectedTvals{0.0, 0.14285714285714288, 0.5, 0.85714285714285721};
1911  VecPt3d expectedPoints = {{8.0, -2.5, 0.0},
1912  {10.0, -3.214285714286, 0.0},
1913  {15.0, -5.0, 0.0},
1914  {20.0, -6.785714285714, 0.0}};
1915  iRunTest(8, -2.5, 22, -7.5, pts, polys, expectedIds, expectedTvals, expectedPoints);
1916 
1917 } // GmMultiPolyIntersectorUnitTests::testEdgeThroughOppositeVertexAtAngle
1918 //------------------------------------------------------------------------------
1922 //
1923 // (0, 0) 2
1924 // +-------------+-------------+
1925 // |\ 4 /|\ 8 /|
1926 // | \ / | \ / |
1927 // | \ / | \ / |
1928 // | 1 x 3 | 5 x 7 |
1929 // | / \ | / \ |
1930 // | / \ 1 / \ |
1931 // |/ 2 \|/ 6 \|
1932 // +-------------+-------------+
1933 // (20, -10)
1935 //------------------------------------------------------------------------------
1936 void GmMultiPolyIntersectorUnitTests::testStartAtEdgeThroughAdjacent()
1937 {
1938  // TS_FAIL("GmMultiPolyIntersectorUnitTests::testStartAtEdgeThroughAdjacent");
1939 
1940  VecPt3d pts;
1941  VecInt2d polys;
1942  trBuildGridTrianglePolys(1, 2, pts, polys);
1943 
1944  // MfMapLayerUGridImp::TraverseLineSegment results
1945  // VecInt expectedIds = {5,8,-1};
1946  // VecDbl expectedTvals = {0.0,0.4,0.8};
1947  VecInt expectedIds{5, 8, -1};
1948  VecDbl expectedTvals{0.0, 0.4, 0.8};
1949  VecPt3d expectedPoints = {{10.0, -8.0, 0.0}, {14.0, -4.0, 0.0}, {18.0, 0.0, 0.0}};
1950  iRunTest(10, -8, 20, 2, pts, polys, expectedIds, expectedTvals, expectedPoints);
1951 } // GmMultiPolyIntersectorUnitTests::testStartAtEdgeThroughAdjacent
1952 //------------------------------------------------------------------------------
1958 //
1959 // (0, 0)
1960 // +-------------+-------------+
1961 // |\ 4 /|\ 8 /|
1962 // | \ / | \ / |
1963 // | \ / | \ / |
1964 // | 1 x 3 | 5 x 7 |
1965 // | / \ | / \ |
1966 // | / \ | / \ |
1967 // |/ 2 \|/ 6 \|
1968 // +-------------+-------------+
1969 // (20, -10)
1971 //------------------------------------------------------------------------------
1972 void GmMultiPolyIntersectorUnitTests::testInsideToEdgeThenThroughAdjacent()
1973 {
1974 // TS_FAIL("GmMultiPolyIntersectorUnitTests::testInsideToEdgeThenThroughAdjacent");
1975 #ifdef __linux__
1976  TS_SKIP("GREENBUILD: This test does not pass on Linux builds.");
1977 #endif
1978  VecPt3d pts;
1979  VecInt2d polys;
1980  trBuildGridTrianglePolys(1, 2, pts, polys);
1981 
1982  // MfMapLayerUGridImp::TraverseLineSegment results
1983  // VecInt expectedIds = {3,-1};
1984  // VecDbl expectedTvals = {0.0,1.0};
1985  VecInt expectedIds{3, -1};
1986  VecDbl expectedTvals{0.0, 1.0};
1987  VecPt3d expectedPoints = {{9.0, -5.0, 0.0}, {10.0, -8.0, 0.0}};
1988  iRunTest(9, -5, 10, -8, pts, polys, expectedIds, expectedTvals, expectedPoints);
1989 } // GmMultiPolyIntersectorUnitTests::testInsideToEdgeThenThroughAdjacent
1990 //------------------------------------------------------------------------------
1994 //------------------------------------------------------------------------------
1995 void GmMultiPolyIntersectorUnitTests::testMap2MfBug()
1996 {
1997  VecPt3d pts{{1937.0003414079, 11829.937474193, 0.0}, {1947.0331979019, 11744.658193995, 0.0},
1998  {1806.3085553039, 11640.957366058, 0.0}, {1827.8055464927, 11817.091027732, 0.0},
1999  {2046.1951363232, 11842.783920654, 0.0}, {2155.4908205085, 11854.643944679, 0.0},
2000  {2160.8354359402, 11805.390806652, 0.0}, {2070.1604445251, 11710.224742147, 0.0}};
2001  VecInt2d polys(2);
2002  polys[0] = {0, 3, 2, 1};
2003  polys[1] = {0, 1, 7, 6, 5, 4};
2004 
2005  const double t = 0.41350462827872492;
2006  VecInt expectedIds{2, 1, -1};
2007  VecDbl expectedTvals{0.0, .5, 1.0};
2008  VecPt3d expectedPoints = {{2046.1951363232, 11842.783920654, 0.00000000000000000},
2009  {1937.0003414079, 11829.937474193, 0.00000000000000000},
2010  {1827.8055464927, 11817.091027732, 0.00000000000000000}};
2011  iRunTest(2046.1951363232, 11842.783920654, 1827.8055464927, 11817.091027732, pts, polys,
2012  expectedIds, expectedTvals, expectedPoints);
2013  expectedIds = {1, 2, -1};
2014  expectedTvals = {0.0, .5, 1};
2015  expectedPoints = {{1827.8055464927, 11817.091027732, 0.0},
2016  {1937.0003414079, 11829.937474193, 0.0},
2017  {2046.1951363232, 11842.783920654, 0.0}};
2018  iRunTest(1827.8055464927, 11817.091027732, 2046.1951363232, 11842.783920654, pts, polys,
2019  expectedIds, expectedTvals, expectedPoints);
2020 } // GmMultiPolyIntersectorUnitTests::testInsideToEdgeThenThroughAdjacent
2021 //------------------------------------------------------------------------------
2025 //
2026 // (0, 0)
2027 // +-------------+-------------+
2028 // |\ 4 /|\ 8 /|
2029 // | \ / | \ / |
2030 // | \ / | \ / |
2031 // | 1 x 3 | 5 x 7 |
2032 // | / \ | / \ |
2033 // | / \ | / \ |
2034 // |/ 2 \|/ 6 \|
2035 // +-------------+-------------+
2036 // (20, -10)
2038 //------------------------------------------------------------------------------
2039 void GmMultiPolyIntersectorUnitTests::testEndAtEdgeFromAdjacent()
2040 {
2041  // TS_FAIL("GmMultiPolyIntersectorUnitTests::testEndAtEdgeFromAdjacent");
2042 
2043  VecPt3d pts;
2044  VecInt2d polys;
2045  trBuildGridTrianglePolys(1, 2, pts, polys);
2046 
2047  // MfMapLayerUGridImp::TraverseLineSegment results
2048  // VecInt expectedIds = {8,5,-1};
2049  // VecDbl expectedTvals = {0.2,0.6,1.0};
2050  VecInt expectedIds{8, 5, -1};
2051  VecDbl expectedTvals{0.2, 0.6, 1.0};
2052  VecPt3d expectedPoints = {{18.0, 0.0}, {14.0, -4.0, 0.0}, {10.0, -8.0, 0.0}};
2053  iRunTest(20, 2, 10, -8, pts, polys, expectedIds, expectedTvals, expectedPoints);
2054 } // GmMultiPolyIntersectorUnitTests::testEndAtEdgeFromAdjacent
2055 //------------------------------------------------------------------------------
2057 //------------------------------------------------------------------------------
2058 void GmMultiPolyIntersectorUnitTests::testSmsCase1()
2059 {
2060  VecPt3d pts{
2061  {-39.719999999999999, 90.079999999999998, 0.0}, {-21.129999999999999, 90.469999999999999, 1.0},
2062  {-38.930000000000000, 75.840000000000003, 2.0}, {-20.539999999999999, 76.629999999999995, 3.0},
2063  {-39.719999999999999, 62.000000000000000, 4.0}, {-20.539999999999999, 61.609999999999999, 5.0},
2064  {-40.509999999999998, 47.770000000000003, 6.0}, {-20.150000000000002, 46.579999999999998, 7.0},
2065  {-41.100000000000001, 30.370000000000001, 8.0}, {-19.550000000000001, 29.379999999999999, 9.0}};
2066  VecInt2d polys(8);
2067  polys[0] = {7, 5, 6};
2068  polys[1] = {3, 2, 5};
2069  polys[2] = {2, 3, 1};
2070  polys[3] = {9, 7, 8};
2071  polys[4] = {7, 6, 8};
2072  polys[5] = {0, 2, 1};
2073  polys[6] = {5, 2, 4};
2074  polys[7] = {4, 6, 5};
2075 
2076  VecInt expectedIds{6, 3, 2, 7, 8, 1, 5, 4, -1};
2077  VecDbl expectedTvals{0.065777232109665892, 0.18968813237387866, 0.26837085508795250,
2078  0.35199491192297022, 0.47395399691316503, 0.58799734941084614,
2079  0.68358069055240822, 0.81969307266961533, 0.93250275302111885};
2080  VecPt3d expectedPoints = {
2081  {-31.97119143306, 90.242562417488, 0.0}, {-31.8980840019, 81.619602868102, 0.0},
2082  {-31.8516611955, 76.144072194429, 0.0}, {-31.80232300197, 70.32467407928, 0.0},
2083  {-31.73036714182, 61.837541354813, 0.0}, {-31.66308156385, 53.901264454499, 0.0},
2084  {-31.60668739257, 47.249619744458, 0.0}, {-31.52638108712, 37.777559072921, 0.0},
2085  {-31.45982337572, 29.92713341726, 0.0}};
2086  iRunTest(-32.009999999999998, 94.819999999999993, -31.420000000000002, 25.230000000000000, pts,
2087  polys, expectedIds, expectedTvals, expectedPoints);
2088 } // GmMultiPolyIntersectorUnitTests::testSmsCase1
2089 
2094 //------------------------------------------------------------------------------
2096 //------------------------------------------------------------------------------
2097 void GmMultiPolyIntersector2IntermediateTests::testLargeNumPolys()
2098 {
2099 #ifndef _DEBUG
2100  // TS_FAIL("GmMultiPolyIntersectorUnitTests::testHuge");
2101 
2102  // Like testAlongEdgesInsideToInside but with many more polygons
2103 
2104  VecPt3d pts;
2105  VecInt2d polys;
2106  trBuildGridTrianglePolys(1000, 3, pts, polys);
2107  // Results in 120,000 polygons, 70,004 points
2108 
2109  // MfMapLayerUGridImp::TraverseLineSegment results
2110  // VecInt expectedIds = {3,17,18,33,-1};
2111  // VecDbl expectedTvals = {0.0,0.22222,0.5,0.777778,1.0};
2112  VecInt expectedIds{2, 17, 18, 33, -1};
2113  VecDbl expectedTvals{0.0, 0.22222, 0.5, 0.777778, 1.0};
2114  VecPt3d expectedPoints = {{6.0, -6.0, 0.0},
2115  {10.0, -10.0, 0.0},
2116  {15.0, -15.0, 0.0},
2117  {20.0, -20.0, 0.0},
2118  {24.0, -24.0, 0.0}};
2119  iRunTest(6, -6, 24, -24, pts, polys, expectedIds, expectedTvals, expectedPoints);
2120 #endif
2121 } // GmMultiPolyIntersector2IntermediateTests::testLargeNumPolys
2122 //------------------------------------------------------------------------------
2124 //------------------------------------------------------------------------------
2125 void GmMultiPolyIntersector2IntermediateTests::testLargeNumPolysAndSegments()
2126 {
2127 #ifndef _DEBUG
2128  // TS_FAIL("GmMultiPolyIntersectorUnitTests::testHuge");
2129 
2130  // Like testAlongEdgesInsideToInside but with many more polygons
2131 
2132  VecPt3d pts;
2133  VecInt2d polys;
2134  trBuildGridTrianglePolys(1000, 3, pts, polys);
2135  // Results in 120,000 polygons, 70,004 points
2136 
2137  VecInt expectedIds = {2, 17, 18, 33, -1};
2138  VecDbl expectedTvals = {0.0, 0.22222, 0.5, 0.777778, 1.0};
2139  BSHP<GmMultiPolyIntersectionSorter> sorter =
2140  BSHP<GmMultiPolyIntersectionSorter>(new GmMultiPolyIntersectionSorterTerse());
2141  BSHP<GmMultiPolyIntersector> mpi = GmMultiPolyIntersector::New(pts, polys, sorter);
2142  VecInt polyIds;
2143  VecDbl tValues;
2144  const int nIntersectingLines =
2145  /*1e5*/ 1000; // Go big for serious timing testing
2146  for (size_t i = 0; i < nIntersectingLines; ++i)
2147  {
2148  // 3 different segments repeated
2149  mpi->TraverseLineSegment(6, -6, 24, -24, polyIds, tValues);
2150  mpi->TraverseLineSegment(7, -6, 25, -24, polyIds, tValues);
2151  mpi->TraverseLineSegment(25, -6, 6, -24, polyIds, tValues);
2152  // Don't need to check that the values are correct. That is done in
2153  // testLargeNumPolys
2154  }
2155 #endif
2156 } // GmMultiPolyIntersector2IntermediateTests::testLargeNumPolysAndSegments
2157 
2158 //------------------------------------------------------------------------------
2160 //------------------------------------------------------------------------------
2161 void GmMultiPolyIntersector2IntermediateTests::testBug12586()
2162 {
2163  std::string testFilesPath(XMS_TEST_PATH);
2164  std::ifstream input(testFilesPath + "bug12586.xmc", std::ios_base::binary);
2165  bool binary = daLineBeginsWith(input, "Binary");
2166  std::string header = binary ? "Binary " : "ASCII ";
2167  header += "UGrid2d Version 1";
2168  daReadNamedLine(input, header.c_str());
2169 
2170  DaStreamReader reader(input, binary);
2171  std::shared_ptr<XmUGrid> xmGrid = XmReadUGridFromStream(input);
2172 
2173  xms::VecInt2d cellPolys;
2174  cellPolys.assign(xmGrid->GetCellCount(), xms::VecInt());
2175  for (int cellIdx = 0; cellIdx < xmGrid->GetCellCount(); ++cellIdx)
2176  {
2177  xms::VecInt& polygon = cellPolys[cellIdx];
2178  polygon.reserve(xmGrid->GetCellEdgeCount(cellIdx));
2179  for (int edgeIdx = 0; edgeIdx < xmGrid->GetCellEdgeCount(cellIdx); ++edgeIdx)
2180  {
2181  // int idx1, idx2;
2182  xms::XmEdge pairIdx = xmGrid->GetCellEdge(cellIdx, edgeIdx);
2183  polygon.push_back(pairIdx.GetFirst());
2184  }
2185  }
2186 
2187 #ifdef _WIN32
2188  std::vector<int> expectedIds = {15802, 7949, 15802, 15955, 7949, 7948, 15955, 16108, 7948,
2189  7947, 16108, 16261, 7946, 7947, 7946, -1};
2190 #elif __linux__
2191  std::vector<int> expectedIds = {15802, 7949, 15802, 15955, 7949, 7948, 15955, 16108, 7947,
2192  7948, 16108, 16261, 7946, 7947, 7946, -1};
2193 #else
2194  std::vector<int> expectedIds = {15802, 7949, 15802, 15955, 7948, 7949, 15955, 16108, 7947,
2195  7948, 16261, 16108, 7946, 7947, 7946, -1};
2196 #endif
2197  std::vector<xms::Pt3d> expectedPoints =
2198  {{1538860.1699999999, 7379636.5400000000, 0.00000000000000000},
2199  {1538860.1700000018, 7379636.5399999982, 4549.3574218750000},
2200  {1538860.6799999995, 7379637.6599999992, 0.00000000000000000},
2201  {1538860.6799999995, 7379637.6599999992, 0.00000000000000000},
2202  {1538860.6800000020, 7379637.6599999983, 4548.8906250000000},
2203  {1538860.6800000020, 7379637.6599999983, 4548.8906250000000},
2204  {1538861.1899999988, 7379638.7799999975, 0.00000000000000000},
2205  {1538861.1899999988, 7379638.7799999975, 0.00000000000000000},
2206  {1538861.1900000013, 7379638.7799999965, 4548.8012695312500},
2207  {1538861.1900000013, 7379638.7799999965, 4548.8012695312500},
2208  {1538861.6999999990, 7379639.8999999976, 0.00000000000000000},
2209  {1538861.6999999990, 7379639.8999999976, 0.00000000000000000},
2210  {1538861.7000000027, 7379639.8999999966, 4548.7114257812500},
2211  {1538861.7000000027, 7379639.8999999966, 4548.7114257812500},
2212  {1538862.2100000030, 7379641.0199999977, 4548.6220703125000},
2213  {1538862.2099999995, 7379641.0199999986, 0.00000000000000000}};
2214  std::vector<double> expectedTvals = {0.00000000000000000, -1.8755588329223459e-010,
2215  0.24999999983166091, 0.24999999983166091, 0.24999999987509086, 0.24999999987509086,
2216  0.49999999947153817, 0.49999999947153817, 0.49999999951496815, 0.49999999951496815,
2217  0.74999999953418495, 0.74999999953418495, 0.74999999967562048, 0.74999999967562048,
2218  0.99999999991044985, 0.99999999978861531};
2219  iRunTest(1538860.17, 7379636.54, 1538862.21, 7379641.02,
2220  xmGrid->GetLocations(), cellPolys, expectedIds, expectedTvals, expectedPoints);
2221 } // GmMultiPolyIntersector2IntermediateTests::testBug12586
2222 
2223 //} // namespace xms
2224 
2225 #endif
xms::GmMultiPolyIntersectorImpl::GetBoostPoly
GmBstPoly3d & GetBoostPoly(int a_polyIdx)
Create and return a boost polygon given a polygon index.
Definition: GmMultiPolyIntersector.cpp:274
xms::GmMultiPolyIntersectorData::m_polys
std::vector< std::vector< int > > m_polys
0-based? indices into m_points to form polygons
Definition: GmMultiPolyIntersectorData.h:51
xms::GmMultiPolyIntersectorImpl::m_query
GmMultiPolyIntersectorQueryEnum m_query
Type of query (intersect, covered by...)
Definition: GmMultiPolyIntersector.cpp:127
xms::GmMultiPolyIntersectorImpl::GetPolysForPoint
void GetPolysForPoint(Pt3d pt, SetInt &poly)
Find the set of polygons intersected (in or on) by the point.
Definition: GmMultiPolyIntersector.cpp:353
xms::GmMultiPolyIntersector
See GmMultiPolyIntersectorImpl comments.
Definition: GmMultiPolyIntersector.h:33
GmMultiPolyIntersector.h
XmUGrid.h
Contains the XmUGrid Class and supporting data types.
VecInt
std::vector< int > VecInt
xms::box
bg::model::box< bPt > box
box
Definition: GmPtSearch.cpp:85
GmMultiPolyIntersectorUnitTests::testSmsCase1
void testSmsCase1()
This case revealed the need for a tolerance when comparing t values.
Definition: GmMultiPolyIntersector.cpp:2058
GmMultiPolyIntersectorUnitTests::testMap2MfBug
void testMap2MfBug()
We only do the first part: inside to edge.
Definition: GmMultiPolyIntersector.cpp:1995
xms::gmXyDistance
double gmXyDistance(double x1, double y1, double x2, double y2)
Compute the 2d distance between 2 points.
Definition: geoms.cpp:832
XM_NONE
#define XM_NONE
xms::gmOnLineAndBetweenEndpointsWithTol
bool gmOnLineAndBetweenEndpointsWithTol(const Pt3d &a_pt1, const Pt3d &a_pt2, const double a_x, const double a_y, double a_tol)
determines if (x,y) is on the line passing through p1 & p2 and between p1 & p2.
Definition: geoms.cpp:767
xms::GmMultiPolyIntersectorImpl::BufferTheBox
void BufferTheBox(GmBstBox3d &box) const
Because the rtree intersection fails in some cases where the line is on an edge, we slightly expand t...
Definition: GmMultiPolyIntersector.cpp:262
xms::GmMultiPolyIntersectorQueryEnum
GmMultiPolyIntersectorQueryEnum
Type of query.
Definition: GmMultiPolyIntersector.h:30
xms::XmReadUGridFromStream
std::shared_ptr< XmUGrid > XmReadUGridFromStream(std::istream &a_inStream)
Read an XmUGrid from ASCII text from an input stream.
Definition: XmUGridUtils.cpp:574
triangles.h
Functions dealing with triangles.
VecDbl
std::vector< double > VecDbl
TS_ASSERT_DELTA_VECPT3D
#define TS_ASSERT_DELTA_VECPT3D(a, b, delta)
xms::GmMultiPolyIntersectorImpl::ComputeTValues
void ComputeTValues()
Compute t values (0.0 - 1.0) from the intersection.
Definition: GmMultiPolyIntersector.cpp:446
xms::GmMultiPolyIntersectorImpl::m_rtree
RtreeBox * m_rtree
Rtree used to find polygons.
Definition: GmMultiPolyIntersector.cpp:120
xms::GmMultiPolyIntersectorImpl::m_line
GmBstLine3d m_line
Current line segment.
Definition: GmMultiPolyIntersector.cpp:121
xms::GmMultiPolyIntersectorImpl
Used to intersect a line segment with any number of polygons in 2D. Returns the intersected polygons ...
Definition: GmMultiPolyIntersector.cpp:62
XmUGridUtils.h
Contains IO functions as well as several utility functions for XmUGrid.
GmBoostTypes.h
boost::geometry types
xms::GmMultiPolyIntersectorImpl::CalculateBuffer
void CalculateBuffer()
Calculate a small buffer distance by which we expand all polygon bounding boxes.
Definition: GmMultiPolyIntersector.cpp:237
xms::gmEqualPointsXY
bool gmEqualPointsXY(double x1, double y1, double x2, double y2, double tolerance)
Returns true if the points are equal to within gmXyTol().
Definition: geoms.cpp:1308
xms::GmMultiPolyIntersectorImpl::SetQuery
virtual void SetQuery(GmMultiPolyIntersectorQueryEnum a_query) override
Set the query to use (covered by, intersects...).
Definition: GmMultiPolyIntersector.cpp:344
xms::GmMultiPolyIntersector::New
static boost::shared_ptr< GmMultiPolyIntersector > New(const std::vector< Pt3d > &a_points, const std::vector< std::vector< int > > &a_polys, boost::shared_ptr< GmMultiPolyIntersectionSorter > a_sorter, int a_startingId=1)
Creates a new GmMultiPolyIntersectorImpl object.
Definition: GmMultiPolyIntersector.cpp:159
xms::GmMultiPolyIntersectorImpl::IntersectEachPolyWithLine
void IntersectEachPolyWithLine()
Go through results (potential polygons) and intersect each one.
Definition: GmMultiPolyIntersector.cpp:386
daReadNamedLine
bool daReadNamedLine(std::istream &a_inStream, const char *a_name)
xms::GmMultiPolyIntersectorImpl::TraverseLineSegment
virtual void TraverseLineSegment(double a_x1, double a_y1, double a_x2, double a_y2, VecInt &a_polyIds, VecDbl &a_tValues) override
Intersect segment with polys and save intersected polys and t-values.
Definition: GmMultiPolyIntersector.cpp:545
xms::GmMultiPolyIntersectorImpl::m_d
GmMultiPolyIntersectorData m_d
Point and poly data.
Definition: GmMultiPolyIntersector.cpp:117
GmMultiPolyIntersectorUnitTests::testInsideToInside
void testInsideToInside()
Given 1 x 2 2D grid turned into triangles with point at poly center triangles numbered as follows: ...
Definition: GmMultiPolyIntersector.cpp:1676
GmMultiPolyIntersectorUnitTests::testOutsideToOutside
void testOutsideToOutside()
Given 1 x 2 2D grid turned into triangles with point at poly center triangles numbered as follows: ...
Definition: GmMultiPolyIntersector.cpp:1709
xms::ix
An intersection point of a line with a polygon.
Definition: GmMultiPolyIntersectorData.h:23
xms::GmMultiPolyIntersectorData::m_polys2
std::set< int > m_polys2
polygon IDs (1-based) that 2nd point is inside on on
Definition: GmMultiPolyIntersectorData.h:53
GmMultiPolyIntersectorUnitTests::testAlongEdgesInsideToInside
void testAlongEdgesInsideToInside()
Given 3 x 3 2D grid turned into triangles with point at poly center triangles numbered as follows: ...
Definition: GmMultiPolyIntersector.cpp:1818
GmMultiPolyIntersectorUnitTests::testEndAtEdgeFromAdjacent
void testEndAtEdgeFromAdjacent()
Given 1 x 2 2D grid turned into triangles with point at poly center triangles numbered as follows: ...
Definition: GmMultiPolyIntersector.cpp:2039
xms::GmMultiPolyIntersectorImpl::SortIntersections
void SortIntersections()
Does a preliminary sort of the intersections by t value.
Definition: GmMultiPolyIntersector.cpp:468
XM_ZERO_TOL
#define XM_ZERO_TOL
xms::GmMultiPolyIntersectorImpl::CreateLine
void CreateLine()
Creates a boost geom line of the current line segment.
Definition: GmMultiPolyIntersector.cpp:335
xms::GmBstLine3d
boost::geometry::model::linestring< Pt3d > GmBstLine3d
Boost line 3d.
Definition: GmBoostTypes.h:43
xms::GmMultiPolyIntersectorImpl::m_xyTol
double m_xyTol
XY tolerance for computing t-values.
Definition: GmMultiPolyIntersector.cpp:123
xms::gmPtDistanceAlongSegment
double gmPtDistanceAlongSegment(const Pt3d &a_pt1, const Pt3d &a_pt2, const Pt3d &a_pt, const double a_tol)
Finds the distance along a segment for the location closest to a_pt.
Definition: geoms.cpp:1749
xms::GmMultiPolyIntersectorImpl::m_boostPolys
std::vector< GmBstPoly3d > m_boostPolys
Polygons as boost geom polygons.
Definition: GmMultiPolyIntersector.cpp:125
VecInt2d
std::vector< VecInt > VecInt2d
xms::GmMultiPolyIntersectorImpl::BuildRTree
void BuildRTree()
Create a boost rtree of polygon extents.
Definition: GmMultiPolyIntersector.cpp:301
GmMultiPolyIntersectionSorterTerse.h
boost_defines.h
xms::ix::m_t
double m_t
t values
Definition: GmMultiPolyIntersectorData.h:43
geoms.h
Functions dealing with geometry.
XmConst.h
xms::GmMultiPolyIntersectorImpl::m_startingId
int m_startingId
Offset if polys start at something other than one.
Definition: GmMultiPolyIntersector.cpp:124
GTEQ_TOL
bool GTEQ_TOL(_T A, _U B, _V tol)
xms::GmMultiPolyIntersectorImpl::m_buffer
double m_buffer
Small buffer around each bounding box.
Definition: GmMultiPolyIntersector.cpp:122
xms::GmMultiPolyIntersectorData::m_polys1
std::set< int > m_polys1
polygon IDs (1-based) that 1st point is inside or on
Definition: GmMultiPolyIntersectorData.h:52
daLineBeginsWith
bool daLineBeginsWith(std::istream &a_inStream, const std::string &a_text)
xms::trBuildGridTrianglePolys
void trBuildGridTrianglePolys(int rows, int cols, VecPt3d &a_points, VecInt2d &a_polys)
Create something like this:
Definition: triangles.cpp:72
GmMultiPolyIntersectorUnitTests::testTouchesVertex
void testTouchesVertex()
Given 1 x 2 2D grid turned into triangles with point at poly center triangles numbered as follows: ...
Definition: GmMultiPolyIntersector.cpp:1742
xms::GmMultiPolyIntersectorImpl::GmMultiPolyIntersectorImpl
GmMultiPolyIntersectorImpl(const VecPt3d &a_points, const VecInt2d &a_polys, BSHP< GmMultiPolyIntersectionSorter > a_sorter, int a_startingId=1)
constructor
Definition: GmMultiPolyIntersector.cpp:185
xms::GmMultiPolyIntersectorImpl::PolygonFromPoint
virtual int PolygonFromPoint(const Pt3d &a_pt) override
Finds the polygon containing the point.
Definition: GmMultiPolyIntersector.cpp:718
xms::GmMultiPolyIntersectorImpl::m_sorter
BSHP< GmMultiPolyIntersectionSorter > m_sorter
Sorter used to process results.
Definition: GmMultiPolyIntersector.cpp:126
GmMultiPolyIntersector2IntermediateTests::testBug12586
void testBug12586()
Test a case where the line is on the points and edges.
Definition: GmMultiPolyIntersector.cpp:2161
xms::gmComputeXyTol
double gmComputeXyTol(const Pt3d &a_mn, const Pt3d &a_mx)
Given extents (min, max), compute a tolerance for the xy plane to be used with geometric functions...
Definition: geoms.cpp:1262
XM_ENSURE_TRUE_VOID_NO_ASSERT
#define XM_ENSURE_TRUE_VOID_NO_ASSERT(...)
SetInt
std::set< int > SetInt
xms::GmMultiPolyIntersectorImpl::PointsOnSegment
void PointsOnSegment(const GmBstPoly3d &a_poly, const GmBstLine3d &a_line, std::deque< Pt3d > &a_output)
Check if the points on the outside of the polygon lie on the line segment.
Definition: GmMultiPolyIntersector.cpp:419
XM_NODATA
#define XM_NODATA
xms::XmEdge
Two integer values representing an edge of an XmUGrid. By default has a direction. Can be sorted to have minimum index first.
Definition: XmEdge.h:33
xms::gmXyTol
double gmXyTol(bool a_set, double a_value)
Get or set (set first time) global xy tolerance for float operations.
Definition: geoms.cpp:1279
xms::GmMultiPolyIntersectorData::m_ixs
std::vector< ix > m_ixs
Intersections.
Definition: GmMultiPolyIntersectorData.h:54
xms::Pt3::Set
void Set(T a_x, T a_y, T a_z)
GmMultiPolyIntersector2IntermediateTests::testLargeNumPolysAndSegments
void testLargeNumPolysAndSegments()
This test can be used for speed comparisons.
Definition: GmMultiPolyIntersector.cpp:2125
xms::GmBstPoly3d
boost::geometry::model::polygon< Pt3d > GmBstPoly3d
Boost polygon 3d.
Definition: GmBoostTypes.h:39
XM_ASSERT
#define XM_ASSERT(x)
xms::GmBstBox3d
boost::geometry::model::box< Pt3d > GmBstBox3d
Boost box 3d.
Definition: GmBoostTypes.h:41
xms::GmMultiPolyIntersectorData
Struct used by GmMultiPolyIntersector.
Definition: GmMultiPolyIntersectorData.h:48
xms
XMS Namespace.
Definition: geoms.cpp:34
GmMultiPolyIntersectorData.h
xms::GmMultiPolyIntersectorImpl::RemoveDuplicateTValues
void RemoveDuplicateTValues(VecInt &a_polyIds, VecDbl &a_tValues, VecPt3d &a_pts)
Removes duplicate T Values and updates the polygon ID and point vectors.
Definition: GmMultiPolyIntersector.cpp:665
GmMultiPolyIntersector2IntermediateTests::testLargeNumPolys
void testLargeNumPolys()
Test a large number of polygons for speed.
Definition: GmMultiPolyIntersector.cpp:2097
xms::GmMultiPolyIntersectorImpl::BuildBoostPoly
void BuildBoostPoly(int a_polyIdx, GmBstPoly3d &a_boostPoly) const
Build a boost polygon given a polygon index.
Definition: GmMultiPolyIntersector.cpp:288
xms::GmMultiPolyIntersectorImpl::OffsetPolyIds
void OffsetPolyIds(VecInt &polyIds) const
If polygon IDs should start at something other than 1, we handle that here.
Definition: GmMultiPolyIntersector.cpp:514
XmError.h
XmLog.h
xms::gmAddToExtents
void gmAddToExtents(const Pt3d &a_pt, Pt3d &a_min, Pt3d &a_max)
Compares a_pt to a_min and a_max. If a_pt is less than a_min or greater than a_max, a_min and a_max are updated.
Definition: geoms.cpp:787
xms::ValueBox
std::pair< GmBstBox3d, int > ValueBox
Pair used in rtree.
Definition: GmMultiPolyIntersector.cpp:56
xms::GmMultiPolyIntersectorImpl::EnsureEndPointsRepresented
void EnsureEndPointsRepresented()
Because unfortunately intersecting the line with the poly doesn&#39;t always create an intersection if a ...
Definition: GmMultiPolyIntersector.cpp:481
GmMultiPolyIntersectorUnitTests::testStartAtEdgeThroughAdjacent
void testStartAtEdgeThroughAdjacent()
Given 1 x 2 2D grid turned into triangles with point at poly center triangles numbered as follows: ...
Definition: GmMultiPolyIntersector.cpp:1936
GmMultiPolyIntersectionSorter.h
xms::RtreeBox
bgi::rtree< ValueBox, bgi::quadratic< 8 > > RtreeBox
Rtree typedef.
Definition: GmMultiPolyIntersector.cpp:57
xms::GmMultiPolyIntersectionSorterTerse
Class for sorting intersections from GmMultiPolyIntersector in a terse way (with no duplicate info)...
Definition: GmMultiPolyIntersectionSorterTerse.h:31
TS_ASSERT_EQUALS_VEC
#define TS_ASSERT_EQUALS_VEC(a, b)
GmMultiPolyIntersector.t.h
GmMultiPolyIntersectorUnitTests::testInsideToEdgeThenThroughAdjacent
void testInsideToEdgeThenThroughAdjacent()
Given 1 x 2 2D grid turned into triangles with point at poly center triangles numbered as follows: ...
Definition: GmMultiPolyIntersector.cpp:1972
TestTools.h
GmMultiPolyIntersectorUnitTests::testTouchesEdge
void testTouchesEdge()
Given 1 x 2 2D grid turned into triangles with point at poly center triangles numbered as follows: ...
Definition: GmMultiPolyIntersector.cpp:1771
GmMultiPolyIntersectorUnitTests::testAlongEdgesOutsideToOutside
void testAlongEdgesOutsideToOutside()
Given 3 x 3 2D grid turned into triangles with point at poly center triangles numbered as follows: ...
Definition: GmMultiPolyIntersector.cpp:1865
xms::XmEdge::GetFirst
int GetFirst() const
Get the first index.
Definition: XmEdge.cpp:103
TS_ASSERT_DELTA_VEC
#define TS_ASSERT_DELTA_VEC(a, b, delta)
VecPt3d
std::vector< Pt3d > VecPt3d
GmMultiPolyIntersectorUnitTests::testEdgeThroughOppositeVertexAtAngle
void testEdgeThroughOppositeVertexAtAngle()
Given 1 x 2 2D grid turned into triangles with point at poly center triangles numbered as follows: ...
Definition: GmMultiPolyIntersector.cpp:1898
xms::GmMultiPolyIntersectorData::m_points
std::vector< Pt3d > m_points
All points used by all polygons.
Definition: GmMultiPolyIntersectorData.h:50