xmsgeom  1.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
GmMultiPolyIntersector.cpp
Go to the documentation of this file.
1 //------------------------------------------------------------------------------
7 //------------------------------------------------------------------------------
8 
9 //----- Included files ---------------------------------------------------------
10 
11 // 1. Precompiled header
12 
13 // 2. My own header
14 #include <xmsgeom/geometry/GmMultiPolyIntersector.h>
15 
16 // 3. Standard library headers
17 
18 // 4. External library headers
19 #pragma warning(push)
20 #pragma warning(disable : 4512) // boost code: no assignment operator
21 #include <boost/geometry.hpp>
22 #include <boost/geometry/geometries/linestring.hpp>
23 #include <boost/geometry/geometries/point_xy.hpp>
24 #include <boost/geometry/geometries/polygon.hpp>
25 #include <boost/geometry/index/rtree.hpp>
26 #pragma warning(pop)
27 
28 // 5. Shared code headers
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 <xmsgeom/geometry/GmBoostTypes.h> // GmBstPoly3d, XmBstRing
38 #include <xmsgeom/geometry/GmMultiPolyIntersectionSorter.h> // GmMultiPolyIntersectionSorter
39 #include <xmsgeom/geometry/GmMultiPolyIntersectorData.h> // GmMultiPolyIntersectorData
40 #include <xmsgeom/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 //----- Constants / Enumerations -----------------------------------------------
53 
54 // Typedefs
55 typedef std::pair<GmBstBox3d, int> ValueBox;
56 typedef bgi::rtree<ValueBox, bgi::quadratic<8>> RtreeBox;
57 
58 //----- Classes / Structs ------------------------------------------------------
59 
61 class GmMultiPolyIntersectorImpl : public GmMultiPolyIntersector {
62 public:
63  GmMultiPolyIntersectorImpl(const VecPt3d &a_points, const VecInt2d &a_polys,
64  BSHP<GmMultiPolyIntersectionSorter> a_sorter,
65  int a_startingId = 1);
66  virtual ~GmMultiPolyIntersectorImpl();
67 
68  virtual void SetQuery(GmMultiPolyIntersectorQueryEnum a_query) override;
69  virtual void TraverseLineSegment(double x1, double y1, double x2, double y2,
70  VecInt &polyids, VecDbl &tvalues) override;
71  virtual void TraverseLineSegment(double x1, double y1, double x2, double y2,
72  VecInt &polyids) override;
73  virtual void TraverseLineSegment(double a_x1, double a_y1, double a_x2,
74  double a_y2, VecInt &a_polyids,
75  std::vector<Pt3d> &a_pts) override;
76  virtual int PolygonFromPoint(const Pt3d &a_pt) override;
77 
78 private:
79  void CalculateBuffer();
80  void BufferTheBox(GmBstBox3d &box) const;
81  GmBstPoly3d &GetBoostPoly(int a_polyIdx);
82  void BuildBoostPoly(int a_polyIdx, GmBstPoly3d &a_boostPoly) const;
83  void BuildRTree();
84  void CreateLine();
85  void GetPolysForPoint(Pt3d pt, SetInt &poly);
86  void EnsureEndPointsRepresented();
87  void IntersectEachPolyWithLine();
88  void ComputeTValues();
89  void SortIntersections();
90  void OffsetPolyIds(VecInt &polyIds) const;
91  void PointsOnSegment(const GmBstPoly3d &a_poly, const GmBstLine3d &a_line,
92  std::deque<Pt3d> &a_output);
93  // void ValidatePolygons ();
94  void TraverseLineSegmentAll(double a_x1, double a_y1, double a_x2,
95  double a_y2, VecInt &a_polyids, VecDbl &a_tvalues,
96  std::vector<Pt3d> &a_pts);
97 
98  GmMultiPolyIntersectorData m_d;
99  Pt3d m_pt1;
100  Pt3d m_pt2;
101  RtreeBox *m_rtree;
102  GmBstLine3d m_line;
103  double m_buffer;
104  int m_startingId;
105  std::vector<GmBstPoly3d> m_boostPolys;
106  BSHP<GmMultiPolyIntersectionSorter>
107  m_sorter;
108  GmMultiPolyIntersectorQueryEnum
109  m_query;
110 }; // class GmMultiPolyIntersectorImpl
111 
112 //----- Class / Function definitions -------------------------------------------
113 
118 //------------------------------------------------------------------------------
120 //------------------------------------------------------------------------------
121 GmMultiPolyIntersector::GmMultiPolyIntersector() {
122 } // GmMultiPolyIntersector::GmMultiPolyIntersector
123 //------------------------------------------------------------------------------
125 //------------------------------------------------------------------------------
126 GmMultiPolyIntersector::~GmMultiPolyIntersector() {
127 } // GmMultiPolyIntersector::~GmMultiPolyIntersector
128 //------------------------------------------------------------------------------
138 //------------------------------------------------------------------------------
139 BSHP<GmMultiPolyIntersector>
140 GmMultiPolyIntersector::New(const VecPt3d &a_points, const VecInt2d &a_polys,
141  BSHP<GmMultiPolyIntersectionSorter> a_sorter,
142  int a_startingId /*=1*/) {
143  return BDPC<GmMultiPolyIntersector>(
144  BSHP<GmMultiPolyIntersectorImpl>(new GmMultiPolyIntersectorImpl(
145  a_points, a_polys, a_sorter, a_startingId)));
146 } // GmMultiPolyIntersector::GmMultiPolyIntersector
147 
154 //------------------------------------------------------------------------------
163 //------------------------------------------------------------------------------
164 GmMultiPolyIntersectorImpl::GmMultiPolyIntersectorImpl(
165  const VecPt3d &a_points, const VecInt2d &a_polys,
166  BSHP<GmMultiPolyIntersectionSorter> a_sorter, int a_startingId /*=1*/)
167  : m_d(), m_pt1(), m_pt2(), m_rtree(nullptr), m_line(), m_buffer(0.0),
168  m_startingId(a_startingId), m_boostPolys(), m_sorter(a_sorter),
169  m_query(GMMPIQ_COVEREDBY) {
170  m_d.m_points = a_points;
171 
172  m_d.m_polys = a_polys;
173  // ValidatePolygons();
174 
175  m_boostPolys.assign(a_polys.size(), GmBstPoly3d());
176 
177  CalculateBuffer();
178  BuildRTree();
179 } // GmMultiPolyIntersectorImpl::GmMultiPolyIntersectorImpl
180 //------------------------------------------------------------------------------
182 //------------------------------------------------------------------------------
183 GmMultiPolyIntersectorImpl::~GmMultiPolyIntersectorImpl() {
184  if (m_rtree)
185  delete (m_rtree);
186 } // GmMultiPolyIntersectorImpl::GmMultiPolyIntersectorImpl
190 // void GmMultiPolyIntersectorImpl::ValidatePolygons ()
191 //{
192 //#ifdef _DEBUG
193 // for (size_t i = 0; i < m_d.m_polys.size(); ++i) {
194 // VecPt3d poly;
195 // for (size_t j = 0; j < m_d.m_polys[i].size(); ++j) {
196 // poly.push_back(m_d.m_points[m_d.m_polys[i][j]]);
197 // }
198 // XM_ASSERT(gmPolygonArea(&poly[0], poly.size()) > 0);
199 // }
200 //#endif
201 //} // GmMultiPolyIntersectorImpl::ValidatePolygons
202 //------------------------------------------------------------------------------
205 //------------------------------------------------------------------------------
206 void GmMultiPolyIntersectorImpl::CalculateBuffer() {
207  // Get min/max of all polys
208  Pt3d mn(XM_DBL_HIGHEST), mx(XM_DBL_LOWEST);
209  for (size_t i = 0; i < m_d.m_polys.size(); ++i) {
210  for (size_t j = 0; j < m_d.m_polys[i].size(); ++j) {
211  gmAddToExtents(m_d.m_points[m_d.m_polys[i][j]], mn, mx);
212  }
213  }
214 
215  // Calculate the buffer as a fraction of the distance between mn and mx
216  const double kFraction = 1e-5; // 0.00001
217  m_buffer = gmXyDistance(mn, mx) * kFraction;
218 } // GmMultiPolyIntersectorImpl::CalculateBuffer
219 //------------------------------------------------------------------------------
226 //------------------------------------------------------------------------------
227 void GmMultiPolyIntersectorImpl::BufferTheBox(GmBstBox3d &box) const {
228  box.min_corner().x -= m_buffer;
229  box.min_corner().y -= m_buffer;
230  box.max_corner().x += m_buffer;
231  box.max_corner().y += m_buffer;
232 } // GmMultiPolyIntersectorImpl::BufferTheBox
233 //------------------------------------------------------------------------------
237 //------------------------------------------------------------------------------
238 GmBstPoly3d &GmMultiPolyIntersectorImpl::GetBoostPoly(int a_polyIdx) {
239  if (m_boostPolys[a_polyIdx].outer().empty()) {
240  // if (bg::exterior_ring(m_boostPolys[a_polyIdx]).empty()) {
241  BuildBoostPoly(a_polyIdx, m_boostPolys[a_polyIdx]);
242  }
243  return m_boostPolys[a_polyIdx];
244 } // GmMultiPolyIntersectorImpl::GetBoostPoly
245 //------------------------------------------------------------------------------
249 //------------------------------------------------------------------------------
250 void GmMultiPolyIntersectorImpl::BuildBoostPoly(
251  int a_polyIdx, GmBstPoly3d &a_boostPoly) const {
252  const VecInt &poly = m_d.m_polys[a_polyIdx];
253  for (int j = 0; j < (int)poly.size(); ++j) {
254  Pt3d pt = m_d.m_points[poly[j]];
255  bg::exterior_ring(a_boostPoly).push_back(m_d.m_points[poly[j]]);
256  }
257  bg::exterior_ring(a_boostPoly).push_back(m_d.m_points[poly[0]]);
258 } // GmMultiPolyIntersectorImpl::BuildBoostPoly
259 //------------------------------------------------------------------------------
261 //------------------------------------------------------------------------------
262 void GmMultiPolyIntersectorImpl::BuildRTree() {
263  // Changed to use the packing algorithm. See:
264  // http://www.boost.org/doc/libs/1_55_0/libs/geometry/doc/html/geometry/spatial_indexes/introduction.html
265  // We thought this would make it faster but according to the test
266  // GmMultiPolyIntersector2IntermediateTests::testLargeNumPolysAndSegments it
267  // didn't make much difference, and actually may be very slightly slower, but
268  // the test may not be very representative of real scenarios. The old code is
269  // still here but commented out in case we want to bring it back in the
270  // future. -MJK
271 
272  // m_rtree = new RtreeBox(); // Non packing algorithm
273  std::vector<ValueBox> boxen; // Packing algorithm
274 
275  for (int i = 0; i < (int)m_d.m_polys.size(); ++i) {
276  Pt3d mn(XM_DBL_HIGHEST), mx(XM_DBL_LOWEST);
277  for (int j = 0; j < (int)m_d.m_polys[i].size(); ++j) {
278  gmAddToExtents(m_d.m_points[m_d.m_polys[i][j]], mn, mx);
279  }
280  GmBstBox3d box(mn, mx);
281  BufferTheBox(box);
282  // m_rtree->insert(std::make_pair(box, i)); // Non packing algorithm
283  boxen.push_back(std::make_pair(box, i)); // Packing algorithm
284  }
285 
286  // Packing algorithm
287  m_rtree = new RtreeBox(boxen.begin(), boxen.end());
288 
289 } // GmMultiPolyIntersectorImpl::BuildRTree
290 //------------------------------------------------------------------------------
292 //------------------------------------------------------------------------------
293 void GmMultiPolyIntersectorImpl::CreateLine() {
294  m_line.push_back(m_pt1);
295  m_line.push_back(m_pt2);
296 } // GmMultiPolyIntersectorImpl::CreateLine
297 //------------------------------------------------------------------------------
300 //------------------------------------------------------------------------------
301 void GmMultiPolyIntersectorImpl::SetQuery(
302  GmMultiPolyIntersectorQueryEnum a_query) {
303  m_query = a_query;
304 } // GmMultiPolyIntersectorImpl::SetQuery
305 //------------------------------------------------------------------------------
309 //------------------------------------------------------------------------------
310 void GmMultiPolyIntersectorImpl::GetPolysForPoint(Pt3d pt, SetInt &a_poly) {
311  std::vector<ValueBox> result;
312  m_rtree->query(bgi::intersects(pt), std::back_inserter(result));
313 
314  // Find the polygon that the point is inside
315  for (size_t i = 0; i < result.size(); ++i) {
316  GmBstPoly3d &poly = GetBoostPoly(result[i].second);
317  //(bg::within(pt, poly)) { // Seems to return true if inside
318  bool rv = false;
319  switch (m_query) {
320  case GMMPIQ_COVEREDBY:
321  rv = bg::covered_by(pt, poly); // Seems to return true if inside or on
322  break;
323  case GMMPIQ_INTERSECTS:
324  rv = bg::intersects(pt, poly);
325  break;
326  default:
327  XM_ASSERT(false);
328  break;
329  }
330  if (rv) {
331  a_poly.insert(result[i].second + 1);
332  }
333  }
334 
335 } // GmMultiPolyIntersectorImpl::GetPolysForPoint
336 //------------------------------------------------------------------------------
338 //------------------------------------------------------------------------------
339 void GmMultiPolyIntersectorImpl::IntersectEachPolyWithLine() {
340  // Get potential polygons which intersect the line from the rtree
341  std::vector<ValueBox> result;
342  m_rtree->query(bgi::intersects(m_line), std::back_inserter(result));
343  // m_rtree.query(bgi::overlaps(m_line), std::back_inserter(result)); //
344  // doesn't compile m_rtree.query(bgi::covered_by(m_line),
345  // std::back_inserter(result)); // doesn't compile
346  // m_rtree.query(bgi::covers(m_line), std::back_inserter(result)); // doesn't
347  // compile
348 
349  // Go through the potential polygons and try to intersect them
350  for (size_t i = 0; i < result.size(); ++i) {
351  GmBstPoly3d &poly = GetBoostPoly(result[i].second);
352  std::deque<Pt3d> output;
353  bg::intersection(poly, m_line, output);
354  if (2 > output.size())
355  PointsOnSegment(poly, m_line, output);
356  for (size_t j = 0; j < output.size(); ++j) {
357  ix ixn(output[j], result[i].second + 1, XM_NODATA);
358  m_d.m_ixs.push_back(ixn);
359  }
360  }
361 } // GmMultiPolyIntersectorImpl::IntersectEachPolyWithLine
362 //------------------------------------------------------------------------------
368 //------------------------------------------------------------------------------
369 void GmMultiPolyIntersectorImpl::PointsOnSegment(const GmBstPoly3d &a_poly,
370  const GmBstLine3d &a_line,
371  std::deque<Pt3d> &a_output) {
372  double tol = m_buffer * 1e-6;
373  for (size_t i = 0; i < a_poly.outer().size(); ++i) {
374  const Pt3d &p = a_poly.outer()[i];
375  if (gmOnLineAndBetweenEndpointsWithTol(
376  a_line[0], a_line[1], p.x, p.y,
377  tol)) { // don't add the point if it is already in the output
378  bool dup = false;
379  for (size_t j = 0; j < a_output.size(); ++j) {
380  if (gmEqualPointsXY(a_output[j], p, tol))
381  dup = true;
382  }
383  if (!dup)
384  a_output.push_back(p);
385  }
386  }
387 } // GmMultiPolyIntersectorImpl::PointsOnSegment
388 //------------------------------------------------------------------------------
393 //------------------------------------------------------------------------------
394 void GmMultiPolyIntersectorImpl::ComputeTValues() {
395  double totalLength = gmXyDistance(m_pt1, m_pt2);
396  for (size_t i = 0; i < m_d.m_ixs.size(); ++i) {
397  if (m_d.m_ixs[i].m_t == XM_NODATA) {
398  m_d.m_ixs[i].m_t = gmXyDistance(m_pt1, m_d.m_ixs[i].m_pt) / totalLength;
399  }
400  }
401 } // GmMultiPolyIntersectorImpl::ComputeTValues
402 //------------------------------------------------------------------------------
404 //------------------------------------------------------------------------------
405 void GmMultiPolyIntersectorImpl::SortIntersections() {
406  XM_ENSURE_TRUE_VOID_NO_ASSERT(m_d.m_ixs.size() > 1);
407 
408  // Sort intersections by t value
409  std::sort(m_d.m_ixs.begin(), m_d.m_ixs.end(),
410  [](const ix &a, const ix &b) -> bool { return a.m_t < b.m_t; });
411 
412 } // GmMultiPolyIntersectorImpl::SortIntersections
413 //------------------------------------------------------------------------------
416 //------------------------------------------------------------------------------
417 void GmMultiPolyIntersectorImpl::EnsureEndPointsRepresented() {
418  // If 1st point was in or on poly, make sure there's an intersection for it
419  for (SetInt::iterator it = m_d.m_polys1.begin(); it != m_d.m_polys1.end();
420  ++it) {
421  bool found = false;
422  for (size_t i = 0;
423  i < m_d.m_ixs.size() && !found && m_d.m_ixs[i].m_t == 0.0; ++i) {
424  if (m_d.m_ixs[i].m_i == *it)
425  found = true;
426  }
427  if (!found)
428  m_d.m_ixs.insert(m_d.m_ixs.begin(), ix(m_pt1, *it, 0.0));
429  }
430 
431  // If 2nd point was in or on poly, make sure there's an intersection for it
432  for (SetInt::iterator it = m_d.m_polys2.begin(); it != m_d.m_polys2.end();
433  ++it) {
434  bool found = false;
435  for (size_t i = m_d.m_ixs.size();
436  i-- > 0 && !found && m_d.m_ixs[i].m_t == 1.0;) {
437  if (m_d.m_ixs[i].m_i == *it)
438  found = true;
439  }
440  if (!found)
441  m_d.m_ixs.push_back(ix(m_pt2, *it, 1.0));
442  }
443 } // GmMultiPolyIntersectorImpl::EnsureEndPointsRepresented
444 //------------------------------------------------------------------------------
448 //------------------------------------------------------------------------------
449 void GmMultiPolyIntersectorImpl::OffsetPolyIds(VecInt &polyIds) const {
450  if (m_startingId != 1) {
451  int offset = m_startingId - 1;
452  for (int i = 0; i < (int)polyIds.size() - 1; ++i) {
453  if (polyIds[i] != XM_NONE) {
454  polyIds[i] += offset;
455  }
456  }
457  }
458 } // GmMultiPolyIntersectorImpl::OffsetPolyIds
459 //------------------------------------------------------------------------------
474 //------------------------------------------------------------------------------
475 void GmMultiPolyIntersectorImpl::TraverseLineSegment(double x1, double y1,
476  double x2, double y2,
477  VecInt &polyids,
478  VecDbl &tvalues) {
479  VecPt3d pts;
480  TraverseLineSegmentAll(x1, y1, x2, y2, polyids, tvalues, pts);
481 } // GmMultiPolyIntersectorImpl::TraverseLineSegment
482 //------------------------------------------------------------------------------
489 //------------------------------------------------------------------------------
490 void GmMultiPolyIntersectorImpl::TraverseLineSegment(double x1, double y1,
491  double x2, double y2,
492  VecInt &polyids) {
493  VecDbl tvalues;
494  VecPt3d pts;
495  TraverseLineSegmentAll(x1, y1, x2, y2, polyids, tvalues, pts);
496 } // GmMultiPolyIntersectorImpl::TraverseLineSegment
497 //-----------------------------------------------------------------------------
506 //-----------------------------------------------------------------------------
507 void GmMultiPolyIntersectorImpl::TraverseLineSegment(double a_x1, double a_y1,
508  double a_x2, double a_y2,
509  VecInt &a_polyids,
510  std::vector<Pt3d> &a_pts) {
511  VecDbl tvalues;
512  TraverseLineSegmentAll(a_x1, a_y1, a_x2, a_y2, a_polyids, tvalues, a_pts);
513 } // GmMultiPolyIntersectorImpl::TraverseLineSegment
514 //-----------------------------------------------------------------------------
518 //-----------------------------------------------------------------------------
519 int GmMultiPolyIntersectorImpl::PolygonFromPoint(const Pt3d &a_pt) {
520  int rval(XM_NONE);
521  SetInt polys;
522  GetPolysForPoint(a_pt, polys);
523  if (!polys.empty()) {
524  rval = (int)*polys.begin();
525  }
526  return rval;
527 } // GmMultiPolyIntersectorImpl::PolygonFromPoint
528 //-----------------------------------------------------------------------------
545 //-----------------------------------------------------------------------------
546 void GmMultiPolyIntersectorImpl::TraverseLineSegmentAll(
547  double a_x1, double a_y1, double a_x2, double a_y2, VecInt &a_polyids,
548  VecDbl &a_tvalues, std::vector<Pt3d> &a_pts) {
549  m_pt1.Set(a_x1, a_y1, 0.0);
550  m_pt2.Set(a_x2, a_y2, 0.0);
551  GetPolysForPoint(m_pt1, m_d.m_polys1);
552  GetPolysForPoint(m_pt2, m_d.m_polys2);
553  CreateLine();
554  IntersectEachPolyWithLine();
555  ComputeTValues();
556  SortIntersections();
557  EnsureEndPointsRepresented();
558  if (!m_sorter) {
559  XM_ASSERT(false);
560  } else {
561  double kTol = 1e-13; // Used to compare t values which are always 0.0 - 1.0
562  m_sorter->Sort(m_d, a_polyids, a_tvalues, a_pts, kTol);
563  }
564  OffsetPolyIds(a_polyids);
565 
566  m_d.m_ixs.clear();
567  m_d.m_polys1.clear();
568  m_d.m_polys2.clear();
569  m_line.clear();
570 } // GmMultiPolyIntersectorImpl::TraverseLineSegmentAll
571 } // namespace xms
572 
574 // TESTS
576 #ifdef CXX_TEST
577 
578 #include <xmsgeom/geometry/GmMultiPolyIntersector.t.h>
579 
580 #include <xmscore/testing/TestTools.h>
581 #include <xmsgeom/geometry/GmMultiPolyIntersectionSorterTerse.h>
582 #include <xmsgeom/triangulate/triangles.h>
583 
584 //----- Namespace declaration --------------------------------------------------
585 
586 // namespace xms {
587 using namespace xms;
588 
589 namespace // unnamed namespace
590 {
591 //------------------------------------------------------------------------------
593 //------------------------------------------------------------------------------
594 void iRunTest(double x1, double y1, double x2, double y2, const VecPt3d &pts,
595  const VecInt2d &polys, const VecInt &a_expectedPolyIDs,
596  const VecDbl &a_expectedtValues,
597  const VecPt3d &a_expectedPoints) {
598  BSHP<GmMultiPolyIntersectionSorter> sorter =
599  BSHP<GmMultiPolyIntersectionSorter>(
600  new GmMultiPolyIntersectionSorterTerse());
601  BSHP<GmMultiPolyIntersector> mpi =
602  GmMultiPolyIntersector::New(pts, polys, sorter);
603  VecInt polyIds1, polyIds2, polyIds3;
604  VecDbl tValues;
605  VecPt3d points;
606  mpi->TraverseLineSegment(x1, y1, x2, y2, polyIds1, tValues);
607  mpi->TraverseLineSegment(x1, y1, x2, y2, polyIds2);
608  mpi->TraverseLineSegment(x1, y1, x2, y2, polyIds3, points);
609  TS_ASSERT_EQUALS_VEC(a_expectedPolyIDs, polyIds1);
610  TS_ASSERT_EQUALS_VEC(a_expectedPolyIDs, polyIds2);
611  TS_ASSERT_EQUALS_VEC(a_expectedPolyIDs, polyIds3);
612  TS_ASSERT_EQUALS(polyIds1.size(), tValues.size());
613  TS_ASSERT_EQUALS(polyIds1.size(), points.size());
614  const double kDelta = 1e-5;
615  TS_ASSERT_DELTA_VEC(a_expectedtValues, tValues, kDelta);
616  TS_ASSERT_DELTA_VECPT3D(a_expectedPoints, points, kDelta);
617 } // iRunTest
618 
619 } // unnamed namespace
620 
625 //------------------------------------------------------------------------------
628 // (10,10)
629 // 3-------------2
630 // | |
631 // 0------------------1
632 // | |
633 // | 1 |
634 // | |
635 // 0-------------1
636 // (0,0)
638 //------------------------------------------------------------------------------
639 void GmMultiPolyIntersectorUnitTests::test1OutOut() {
640  VecPt3d pts = {{0, 0, 0}, {10, 0, 0}, {10, 10, 0}, {0, 10, 0}};
641  VecInt2d polys = {{0, 1, 2, 3}};
642  VecInt expectedIds = {1, -1};
643  VecDbl expectedTvals = {0.0833333, 0.916667};
644  VecPt3d expectedPoints = {{0.0, 5.0, 0.0}, {10.0, 5.0, 0.0}};
645  iRunTest(-1, 5, 11, 5, pts, polys, expectedIds, expectedTvals,
646  expectedPoints);
647 
648 } // GmMultiPolyIntersectorUnitTests::test1OutOut
649 //------------------------------------------------------------------------------
652 // (10,10)
653 // 3-------------2
654 // | |
655 // 0----------1 |
656 // | |
657 // | 1 |
658 // | |
659 // 0-------------1
660 // (0,0)
662 //------------------------------------------------------------------------------
663 void GmMultiPolyIntersectorUnitTests::test1OutIn() {
664  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {10, 10, 0}, {0, 10, 0}};
665  VecInt2d polys{{0, 1, 2, 3}};
666  VecInt expectedIds{1, -1};
667  VecDbl expectedTvals{0.111111, 1.0};
668  VecPt3d expectedPoints = {{0.0, 5.0, 0.0}, {8.0, 5.0, 0.0}};
669  iRunTest(-1, 5, 8, 5, pts, polys, expectedIds, expectedTvals, expectedPoints);
670 
671 } // GmMultiPolyIntersectorUnitTests::test1OutIn
672 //------------------------------------------------------------------------------
675 // (10,10)
676 // 3-------------2
677 // | |
678 // | 0----------1
679 // | |
680 // | 1 |
681 // | |
682 // 0-------------1
683 // (0,0)
685 //------------------------------------------------------------------------------
686 void GmMultiPolyIntersectorUnitTests::test1InOut() {
687  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {10, 10, 0}, {0, 10, 0}};
688  VecInt2d polys = {{0, 1, 2, 3}};
689  VecInt expectedIds{1, -1};
690  VecDbl expectedTvals{0.0, 0.833333};
691  VecPt3d expectedPoints = {{5.0, 5.0, 0.0}, {10.0, 5.0, 0.0}};
692  iRunTest(5, 5, 11, 5, pts, polys, expectedIds, expectedTvals, expectedPoints);
693 
694 } // GmMultiPolyIntersectorUnitTests::test1InOut
695 //------------------------------------------------------------------------------
698 // (10,10)
699 // 3-------------2
700 // | |
701 // | 0--------1 |
702 // | |
703 // | 1 |
704 // | |
705 // 0-------------1
706 // (0,0)
708 //------------------------------------------------------------------------------
709 void GmMultiPolyIntersectorUnitTests::test1InIn() {
710  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {10, 10, 0}, {0, 10, 0}};
711  VecInt2d polys{{0, 1, 2, 3}};
712  VecInt expectedIds{1, -1};
713  VecDbl expectedTvals{0.0, 1.0};
714  VecPt3d expectedPoints = {{2.0, 5.0, 0.0}, {8.0, 5.0, 0.0}};
715  iRunTest(2, 5, 8, 5, pts, polys, expectedIds, expectedTvals, expectedPoints);
716 
717 } // GmMultiPolyIntersectorUnitTests::test1InIn
718 //------------------------------------------------------------------------------
721 // (10,10)
722 // 3-------------2
723 // | |
724 // 0-------------1
725 // | |
726 // | 1 |
727 // | |
728 // 0-------------1
729 // (0,0)
731 //------------------------------------------------------------------------------
732 void GmMultiPolyIntersectorUnitTests::test1OnOn() {
733  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {10, 10, 0}, {0, 10, 0}};
734  VecInt2d polys{{0, 1, 2, 3}};
735  VecInt expectedIds{1, -1};
736  VecDbl expectedTvals{0.0, 1.0};
737  VecPt3d expectedPoints = {{0.0, 5.0, 0.0}, {10.0, 5.0, 0.0}};
738  iRunTest(0, 5, 10, 5, pts, polys, expectedIds, expectedTvals, expectedPoints);
739 
740 } // GmMultiPolyIntersectorUnitTests::test1OnOn
741 //------------------------------------------------------------------------------
744 // (10,10)
745 // 3-------------2
746 // | |
747 // 0------1 |
748 // | |
749 // | 1 |
750 // | |
751 // 0-------------1
752 // (0,0)
754 //------------------------------------------------------------------------------
755 void GmMultiPolyIntersectorUnitTests::test1OnIn() {
756  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {10, 10, 0}, {0, 10, 0}};
757  VecInt2d polys{{0, 1, 2, 3}};
758  VecInt expectedIds{1, -1};
759  VecDbl expectedTvals{0.0, 1.0};
760  VecPt3d expectedPoints = {{0.0, 5.0, 0.0}, {5.0, 5.0, 0.0}};
761  iRunTest(0, 5, 5, 5, pts, polys, expectedIds, expectedTvals, expectedPoints);
762 
763 } // GmMultiPolyIntersectorUnitTests::test1OnIn
764 //------------------------------------------------------------------------------
767 // (10,10)
768 // 3-------------2
769 // | |
770 // | 0------1
771 // | |
772 // | 1 |
773 // | |
774 // 0-------------1
775 // (0,0)
777 //------------------------------------------------------------------------------
778 void GmMultiPolyIntersectorUnitTests::test1InOn() {
779  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {10, 10, 0}, {0, 10, 0}};
780  VecInt2d polys{{0, 1, 2, 3}};
781  VecInt expectedIds{1, -1};
782  VecDbl expectedTvals{0.0, 1.0};
783  VecPt3d expectedPoints = {{5.0, 5.0, 0.0}, {10.0, 5.0, 0.0}};
784  iRunTest(5, 5, 10, 5, pts, polys, expectedIds, expectedTvals, expectedPoints);
785 
786 } // GmMultiPolyIntersectorUnitTests::test1InOn
787 //------------------------------------------------------------------------------
790 // (10,10)
791 // 3-------------2
792 // | |
793 // 0--1 |
794 // | 1 |
795 // | |
796 // | |
797 // 0-------------1
798 // (0,0)
800 //------------------------------------------------------------------------------
801 void GmMultiPolyIntersectorUnitTests::test1OutOn() {
802  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {10, 10, 0}, {0, 10, 0}};
803  VecInt2d polys{{0, 1, 2, 3}};
804  VecInt expectedIds{1, -1};
805  VecDbl expectedTvals{1.0, 1.0};
806  VecPt3d expectedPoints = {{0.0, 5.0, 0.0}, {0.0, 5.0, 0.0}};
807  iRunTest(-1, 5, 0, 5, pts, polys, expectedIds, expectedTvals, expectedPoints);
808 
809 } // GmMultiPolyIntersectorUnitTests::test1OutOn
810 //------------------------------------------------------------------------------
813 // (10,10)
814 // 3-------------2
815 // | |
816 // | 0--1
817 // | 1 |
818 // | |
819 // | |
820 // 0-------------1
821 // (0,0)
823 //------------------------------------------------------------------------------
824 void GmMultiPolyIntersectorUnitTests::test1OnOut() {
825  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {10, 10, 0}, {0, 10, 0}};
826  VecInt2d polys{{0, 1, 2, 3}};
827  VecInt expectedIds{1, -1};
828  VecDbl expectedTvals{0.0, 0.0};
829  VecPt3d expectedPoints = {{10.0, 5.0, 0.0}, {10.0, 5.0, 0.0}};
830  iRunTest(10, 5, 11, 5, pts, polys, expectedIds, expectedTvals,
831  expectedPoints);
832 
833 } // GmMultiPolyIntersectorUnitTests::test1OnOut
834 //------------------------------------------------------------------------------
837 // (10,10)
838 // 3----0----1---2
839 // | |
840 // | |
841 // | 1 |
842 // | |
843 // | |
844 // 0-------------1
845 // (0,0)
847 //------------------------------------------------------------------------------
848 void GmMultiPolyIntersectorUnitTests::test1EdgeInIn() {
849  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {10, 10, 0}, {0, 10, 0}};
850  VecInt2d polys{{0, 1, 2, 3}};
851  VecInt expectedIds{1, -1};
852  VecDbl expectedTvals{0.0, 1.0};
853  VecPt3d expectedPoints = {{3.0, 10.0, 0.0}, {7.0, 10.0, 0.0}};
854  iRunTest(3, 10, 7, 10, pts, polys, expectedIds, expectedTvals,
855  expectedPoints);
856 
857 } // GmMultiPolyIntersectorUnitTests::test1EdgeInIn
858 //------------------------------------------------------------------------------
861 // (10,10)
862 // 3|1-----------2|2
863 // | |
864 // | |
865 // | 1 |
866 // | |
867 // | |
868 // 0-------------1
869 // (0,0)
871 //------------------------------------------------------------------------------
872 void GmMultiPolyIntersectorUnitTests::test1EdgePtPt() {
873  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {10, 10, 0}, {0, 10, 0}};
874  VecInt2d polys{{0, 1, 2, 3}};
875  VecInt expectedIds{1, -1};
876  VecDbl expectedTvals{0.0, 1.0};
877  VecPt3d expectedPoints = {{0.0, 10.0, 0.0}, {10.0, 10.0, 0.0}};
878  iRunTest(0, 10, 10, 10, pts, polys, expectedIds, expectedTvals,
879  expectedPoints);
880 
881 } // GmMultiPolyIntersectorUnitTests::test1EdgePtPt
882 //------------------------------------------------------------------------------
885 // (10,10)
886 // 1--3-------------2--2
887 // | |
888 // | |
889 // | 1 |
890 // | |
891 // | |
892 // 0-------------1
893 // (0,0)
895 //------------------------------------------------------------------------------
896 void GmMultiPolyIntersectorUnitTests::test1EdgeOutOut() {
897  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {10, 10, 0}, {0, 10, 0}};
898  VecInt2d polys{{0, 1, 2, 3}};
899  VecInt expectedIds{1, -1};
900  VecDbl expectedTvals{0.0833333, 0.9166667};
901  VecPt3d expectedPoints = {{10.0, 10.0, 0.0}, {0.0, 10.0, 0.0}};
902  // iRunTest(-1, 10, 11, 10, pts, polys, expectedIds, expectedTvals,
903  // expectedPoints); // doesn't work
904  iRunTest(11, 10, -1, 10, pts, polys, expectedIds, expectedTvals,
905  expectedPoints);
906 
907 } // GmMultiPolyIntersectorUnitTests::test1EdgeOutOut
908 //------------------------------------------------------------------------------
911 // (10,10)
912 // 1--3------2------2
913 // | |
914 // | |
915 // | 1 |
916 // | |
917 // | |
918 // 0-------------1
919 // (0,0)
921 //------------------------------------------------------------------------------
922 void GmMultiPolyIntersectorUnitTests::test1EdgeOutIn() {
923  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {10, 10, 0}, {0, 10, 0}};
924  VecInt2d polys{{0, 1, 2, 3}};
925  VecInt expectedIds{1, -1};
926  VecDbl expectedTvals{0.166667, 1.0};
927  VecPt3d expectedPoints = {{0.0, 10.0, 0.0}, {5.0, 10.0, 0.0}};
928  iRunTest(-1, 10, 5, 10, pts, polys, expectedIds, expectedTvals,
929  expectedPoints);
930  expectedTvals = {0.0, 5 / 6.0};
931  expectedPoints = {{5.0, 10.0, 0.0}, {0.0, 10.0, 0.0}};
932  iRunTest(5, 10, -1, 10, pts, polys, expectedIds, expectedTvals,
933  expectedPoints);
934  // iRunTest(-1, 0, 5, 0, pts, polys, expectedIds, expectedTvals,
935  // expectedPoints); //works iRunTest(-1, 9.999999999999999, 5, 10, pts, polys,
936  // expectedIds, expectedTvals, expectedPoints); //works
937  expectedTvals = {1.0 / 3.0, 1.0};
938  expectedPoints = {{10.0, 10.0, 0.0}, {0.0, 10.0, 0.0}};
939  iRunTest(15, 10, 0, 10, pts, polys, expectedIds, expectedTvals,
940  expectedPoints);
941 } // GmMultiPolyIntersectorUnitTests::test1EdgeOutIn
942 //------------------------------------------------------------------------------
945 // (10,10)
946 // 3------1------2--2
947 // | |
948 // | |
949 // | 1 |
950 // | |
951 // | |
952 // 0-------------1
953 // (0,0)
955 //------------------------------------------------------------------------------
956 void GmMultiPolyIntersectorUnitTests::test1EdgeInOut() {
957  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {10, 10, 0}, {0, 10, 0}};
958  VecInt2d polys{{0, 1, 2, 3}};
959  VecInt expectedIds{1, -1};
960  VecDbl expectedTvals{0.0, 0.833333};
961  VecPt3d expectedPoints = {{5.0, 10.0, 0.0}, {10.0, 10.0, 0.0}};
962  iRunTest(5, 10, 11, 10, pts, polys, expectedIds, expectedTvals,
963  expectedPoints); // works
964  // iRunTest(11, 10, 5, 10, pts, polys, expectedIds, expectedTvals,
965  // expectedPoints); // doesn't work
966 
967 } // GmMultiPolyIntersectorUnitTests::test1EdgeInOut
968 //------------------------------------------------------------------------------
971 // (10,10)
972 // 1-2|3-------------2
973 // | |
974 // | |
975 // | 1 |
976 // | |
977 // | |
978 // 0-------------1
979 // (0,0)
981 //------------------------------------------------------------------------------
982 void GmMultiPolyIntersectorUnitTests::test1OutPt() {
983  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {10, 10, 0}, {0, 10, 0}};
984  VecInt2d polys{{0, 1, 2, 3}};
985  VecInt expectedIds{1, -1};
986  VecDbl expectedTvals{1.0, 1.0};
987  VecPt3d expectedPoints = {{0.0, 10.0, 0.0}, {0.0, 10.0, 0.0}};
988  iRunTest(-1, 10, 0, 10, pts, polys, expectedIds, expectedTvals,
989  expectedPoints);
990 
991 } // GmMultiPolyIntersectorUnitTests::test1OutPt
992 //------------------------------------------------------------------------------
995 // 2
996 // / (10,10)
997 // 3-------------2
998 // /| |
999 // 1 | |
1000 // | 1 |
1001 // | |
1002 // | |
1003 // 0-------------1
1004 // (0,0)
1006 //------------------------------------------------------------------------------
1007 void GmMultiPolyIntersectorUnitTests::test1OutPtOut() {
1008  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {10, 10, 0}, {0, 10, 0}};
1009  VecInt2d polys{{0, 1, 2, 3}};
1010  VecInt expectedIds{1, -1};
1011  VecDbl expectedTvals{0.5, 0.5};
1012  VecPt3d expectedPoints = {{0.0, 10.0, 0.0}, {0.0, 10.0, 0.0}};
1013  iRunTest(-1, 9, 1, 11, pts, polys, expectedIds, expectedTvals,
1014  expectedPoints);
1015 
1016 } // GmMultiPolyIntersectorUnitTests::test1OutPtOut
1017 //------------------------------------------------------------------------------
1020 // 2
1021 // / (10,10)
1022 // 1 3-------------2
1023 // | |
1024 // | |
1025 // | 1 |
1026 // | |
1027 // | |
1028 // 0-------------1
1029 // (0,0)
1031 //------------------------------------------------------------------------------
1032 void GmMultiPolyIntersectorUnitTests::test1AllOut() {
1033  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {10, 10, 0}, {0, 10, 0}};
1034  VecInt2d polys{{0, 1, 2, 3}};
1035  VecInt expectedIds;
1036  VecDbl expectedTvals;
1037  VecPt3d expectedPoints = {};
1038  iRunTest(-1, 10, 0, 11, pts, polys, expectedIds, expectedTvals,
1039  expectedPoints);
1040 
1041 } // GmMultiPolyIntersectorUnitTests::test1AllOut
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::test1PtIn() {
1057  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {10, 10, 0}, {0, 10, 0}};
1058  VecInt2d polys{{0, 1, 2, 3}};
1059  VecInt expectedIds{1, -1};
1060  VecDbl expectedTvals{0.0, 1.0};
1061  VecPt3d expectedPoints = {{0.0, 10.0, 0.0}, {5.0, 10.0, 0.0}};
1062  iRunTest(0, 10, 5, 10, pts, polys, expectedIds, expectedTvals,
1063  expectedPoints);
1064 
1065 } // GmMultiPolyIntersectorUnitTests::test1PtIn
1066 //------------------------------------------------------------------------------
1069 // (10,10)
1070 // 3|------1-----2|2
1071 // | |
1072 // | |
1073 // | 1 |
1074 // | |
1075 // | |
1076 // 0-------------1
1077 // (0,0)
1079 //------------------------------------------------------------------------------
1080 void GmMultiPolyIntersectorUnitTests::test1InPt() {
1081  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {10, 10, 0}, {0, 10, 0}};
1082  VecInt2d polys{{0, 1, 2, 3}};
1083  VecInt expectedIds{1, -1};
1084  VecDbl expectedTvals{0.0, 1.0};
1085  VecPt3d expectedPoints = {{5.0, 10.0, 0.0}, {10.0, 10.0, 0.0}};
1086  iRunTest(5, 10, 10, 10, pts, polys, expectedIds, expectedTvals,
1087  expectedPoints);
1088 
1089 } // GmMultiPolyIntersectorUnitTests::test1InPt
1090 //------------------------------------------------------------------------------
1093 // (0,10)
1094 // 3-------------4-------------5
1095 // | | |
1096 // 0-------------1 |
1097 // | | |
1098 // | 1 | 2 |
1099 // | | |
1100 // 0-------------1-------------2
1101 // (0,0) (20,0)
1103 //------------------------------------------------------------------------------
1104 void GmMultiPolyIntersectorUnitTests::test2OnOn() {
1105  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {20, 0, 0},
1106  {0, 10, 0}, {10, 10, 0}, {20, 10, 0}};
1107  VecInt2d polys{{0, 1, 4, 3}};
1108  VecInt expectedIds{1, -1}; // old: (1)
1109  VecDbl expectedTvals{0.0, 1.0};
1110  VecPt3d expectedPoints = {{0.0, 5.0, 0.0}, {10.0, 5.0, 0.0}};
1111  iRunTest(0, 5, 10, 5, pts, polys, expectedIds, expectedTvals, expectedPoints);
1112 
1113 } // GmMultiPolyIntersectorUnitTests::test2OnOn
1114 //------------------------------------------------------------------------------
1117 // (0,10)
1118 // 3-------------4-------------5
1119 // | | |
1120 // | 0-------1 |
1121 // | | |
1122 // | 1 | 2 |
1123 // | | |
1124 // 0-------------1-------------2
1125 // (0,0) (20,0)
1127 //------------------------------------------------------------------------------
1128 void GmMultiPolyIntersectorUnitTests::test2InOn() {
1129  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {20, 0, 0},
1130  {0, 10, 0}, {10, 10, 0}, {20, 10, 0}};
1131  VecInt2d polys{{0, 1, 4, 3}};
1132  VecInt expectedIds{1, -1}; // old: (1)
1133  VecDbl expectedTvals{0.0, 1.0};
1134  VecPt3d expectedPoints = {{5.0, 5.0, 0.0}, {10.0, 5.0, 0.0}};
1135  iRunTest(5, 5, 10, 5, pts, polys, expectedIds, expectedTvals, expectedPoints);
1136 
1137 } // GmMultiPolyIntersectorUnitTests::test2InOn
1138 //------------------------------------------------------------------------------
1141 // (0,10)
1142 // 3-------------4-------------5
1143 // | | |
1144 // | 0-------1 |
1145 // | | |
1146 // | 1 | 2 |
1147 // | | |
1148 // 0-------------1-------------2
1149 // (0,0) (20,0)
1151 //------------------------------------------------------------------------------
1152 void GmMultiPolyIntersectorUnitTests::test2OnIn() {
1153  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {20, 0, 0},
1154  {0, 10, 0}, {10, 10, 0}, {20, 10, 0}};
1155  VecInt2d polys = {{0, 1, 4, 3}, {1, 2, 5, 4}};
1156  VecInt expectedIds{1, -1}; // old: (1)
1157  VecDbl expectedTvals{0.0, 1.0};
1158  VecPt3d expectedPoints = {{5.0, 5.0, 0.0}, {10.0, 5.0, 0.0}};
1159  iRunTest(5, 5, 10, 5, pts, polys, expectedIds, expectedTvals, expectedPoints);
1160 
1161 } // GmMultiPolyIntersectorUnitTests::test2OnIn
1162 //------------------------------------------------------------------------------
1165 // (0,10)
1166 // 3-------------4-------------5
1167 // | | |
1168 // 0--------------------------------1
1169 // | | |
1170 // | 1 | 2 |
1171 // | | |
1172 // 0-------------1-------------2
1173 // (0,0) (20,0)
1175 //------------------------------------------------------------------------------
1176 void GmMultiPolyIntersectorUnitTests::test2OutOut() {
1177  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {20, 0, 0},
1178  {0, 10, 0}, {10, 10, 0}, {20, 10, 0}};
1179  VecInt2d polys = {{0, 1, 4, 3}, {1, 2, 5, 4}};
1180  VecInt expectedIds{1, 2, -1}; // old: (1)(2)
1181  VecDbl expectedTvals{0.0454545, 0.5, 0.954545};
1182  VecPt3d expectedPoints = {
1183  {0.0, 5.0, 0.0}, {10.0, 5.0, 0.0}, {20.0, 5.0, 0.0}};
1184  iRunTest(-1, 5, 21, 5, pts, polys, expectedIds, expectedTvals,
1185  expectedPoints);
1186 
1187 } // GmMultiPolyIntersectorUnitTests::test2OutOut
1188 //------------------------------------------------------------------------------
1191 // (0,10)
1192 // 3-------------4-------------5
1193 // | | |
1194 // 0------------------------1 |
1195 // | | |
1196 // | 1 | 2 |
1197 // | | |
1198 // 0-------------1-------------2
1199 // (0,0) (20,0)
1201 //------------------------------------------------------------------------------
1202 void GmMultiPolyIntersectorUnitTests::test2OutIn() {
1203  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {20, 0, 0},
1204  {0, 10, 0}, {10, 10, 0}, {20, 10, 0}};
1205  VecInt2d polys = {{{0, 1, 4, 3}}, {1, 2, 5, 4}};
1206  VecInt expectedIds{1, 2, -1}; // old: (1)(2)
1207  VecDbl expectedTvals{0.0625, 0.6875, 1.0};
1208  VecPt3d expectedPoints = {
1209  {0.0, 5.0, 0.0}, {10.0, 5.0, 0.0}, {15.0, 5.0, 0.0}};
1210  iRunTest(-1, 5, 15, 5, pts, polys, expectedIds, expectedTvals,
1211  expectedPoints);
1212 
1213 } // GmMultiPolyIntersectorUnitTests::test2OutIn
1214 //------------------------------------------------------------------------------
1217 // (0,10)
1218 // 3-------------4-------------5
1219 // | | |
1220 // | 0---------------------1
1221 // | | |
1222 // | 1 | 2 |
1223 // | | |
1224 // 0-------------1-------------2
1225 // (0,0) (20,0)
1227 //------------------------------------------------------------------------------
1228 void GmMultiPolyIntersectorUnitTests::test2InOut() {
1229  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {20, 0, 0},
1230  {0, 10, 0}, {10, 10, 0}, {20, 10, 0}};
1231  VecInt2d polys = {{0, 1, 4, 3}, {1, 2, 5, 4}};
1232  VecInt expectedIds{1, 2, -1}; // old: (1)(2)
1233  VecDbl expectedTvals{0.0, 0.3125, 0.9375};
1234  VecPt3d expectedPoints = {
1235  {5.0, 5.0, 0.0}, {10.0, 5.0, 0.0}, {20.0, 5.0, 0.0}};
1236  iRunTest(5, 5, 21, 5, pts, polys, expectedIds, expectedTvals, expectedPoints);
1237 
1238 } // GmMultiPolyIntersectorUnitTests::test2InOut
1239 //------------------------------------------------------------------------------
1242 // (0,10)
1243 // 3-------------4-------------5
1244 // | | |
1245 // | 0-------------1 |
1246 // | | |
1247 // | 1 | 2 |
1248 // | | |
1249 // 0-------------1-------------2
1250 // (0,0) (20,0)
1252 //------------------------------------------------------------------------------
1253 void GmMultiPolyIntersectorUnitTests::test2InIn() {
1254  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {20, 0, 0},
1255  {0, 10, 0}, {10, 10, 0}, {20, 10, 0}};
1256  VecInt2d polys = {{0, 1, 4, 3}, {1, 2, 5, 4}};
1257  VecInt expectedIds{1, 2, -1}; // old: (1)(2)
1258  VecDbl expectedTvals{0.0, 0.5, 1.0};
1259  VecPt3d expectedPoints = {
1260  {5.0, 5.0, 0.0}, {10.0, 5.0, 0.0}, {15.0, 5.0, 0.0}};
1261  iRunTest(5, 5, 15, 5, pts, polys, expectedIds, expectedTvals, expectedPoints);
1262 } // GmMultiPolyIntersectorUnitTests::test2InIn
1263 //------------------------------------------------------------------------------
1266 // (0,10)
1267 // 3------1-----2|4-------------5
1268 // | | |
1269 // | | |
1270 // | 1 | 2 |
1271 // | | |
1272 // | | |
1273 // 0-------------1-------------2
1274 // (0,0) (20,0)
1276 //------------------------------------------------------------------------------
1277 void GmMultiPolyIntersectorUnitTests::test2InPt() {
1278  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {20, 0, 0},
1279  {0, 10, 0}, {10, 10, 0}, {20, 10, 0}};
1280  VecInt2d polys = {{0, 1, 4, 3}, {1, 2, 5, 4}};
1281  VecInt expectedIds{1, -1}; // old: (1)(2)
1282  VecDbl expectedTvals{0.0, 1.0};
1283  VecPt3d expectedPoints = {{5.0, 10.0, 0.0}, {10.0, 10.0, 0.0}};
1284  iRunTest(5, 10, 10, 10, pts, polys, expectedIds, expectedTvals,
1285  expectedPoints);
1286 } // GmMultiPolyIntersectorUnitTests::test2InPt
1287 //------------------------------------------------------------------------------
1290 // (0,10)
1291 // 3------------4|1-----2------5
1292 // | | |
1293 // | | |
1294 // | 1 | 2 |
1295 // | | |
1296 // | | |
1297 // 0-------------1-------------2
1298 // (0,0) (20,0)
1300 //------------------------------------------------------------------------------
1301 void GmMultiPolyIntersectorUnitTests::test2PtIn() {
1302  VecPt3d pts{{0, 0, 0}, {10, 0, 0}, {20, 0, 0},
1303  {0, 10, 0}, {10, 10, 0}, {20, 10, 0}};
1304  VecInt2d polys = {{0, 1, 4, 3}, {1, 2, 5, 4}};
1305  VecInt expectedIds{2, -1}; // old: (1)(2)
1306  VecDbl expectedTvals{0.0, 1.0};
1307  VecPt3d expectedPoints = {{10.0, 10.0, 0.0}, {15.0, 10.0, 0.0}};
1308  iRunTest(10, 10, 15, 10, pts, polys, expectedIds, expectedTvals,
1309  expectedPoints);
1310 } // GmMultiPolyIntersectorUnitTests::test2PtIn
1311 //------------------------------------------------------------------------------
1314 // (0,10)
1315 // 3------1-----4|-------------5 2
1316 // | | |
1317 // | | |
1318 // | 1 | 2 |
1319 // | | |
1320 // | | |
1321 // 0-------------1-------------2
1322 // (0,0) (20,0)
1324 //------------------------------------------------------------------------------
1325 void GmMultiPolyIntersectorUnitTests::test2InEdgePt() {
1326  // The comment below is not true. Check
1327  // GmMultiPolyIntersectorImpl::GmMultiPolyIntersectorImpl to see that we don't
1328  // set z's to 0.0 and this test works. We are using Pt3d as a 2D boost
1329  // geometry so z's don't come into play.
1330  // // The non-equal z values would cause this test to fail but now we
1331  // // set them all to 0.0.
1332  VecPt3d pts{{0, 0, 100}, {10, 0, 110}, {20, 0, 105},
1333  {0, 10, 104}, {10, 10, 103}, {20, 10, 106}};
1334  VecInt2d polys = {{0, 1, 4, 3}, {1, 2, 5, 4}};
1335  VecInt expectedIds{1, 2, -1};
1336  VecDbl expectedTvals = {0.0, 1 / 3.0, 1};
1337  VecPt3d expectedPoints = {
1338  {5.0, 10.0, 0.0}, {10.0, 10.0, 0.0}, {20.0, 10.0, 0.0}};
1339  iRunTest(5, 10, 20, 10, pts, polys, expectedIds, expectedTvals,
1340  expectedPoints);
1341  expectedIds = {2, 1, -1};
1342  expectedPoints = {{15.0, 10.0, 0.0}, {10.0, 10.0, 0.0}, {0.0, 10.0, 0.0}};
1343  iRunTest(15, 10, 0, 10, pts, polys, expectedIds, expectedTvals,
1344  expectedPoints);
1345 } // GmMultiPolyIntersectorUnitTests::test2PtIn
1346 //------------------------------------------------------------------------------
1349 // (0,20)
1350 // 3-------------2
1351 // | 1 |
1352 // | \|
1353 // | 1 \
1354 // | |\
1355 // | | \
1356 // 0-------------1--\----------6
1357 // | \ |
1358 // | 2 |
1359 // | |
1360 // | 2 |
1361 // | |
1362 // 4-------------5
1363 // (0,0) (20,0)
1365 //------------------------------------------------------------------------------
1366 void GmMultiPolyIntersectorUnitTests::test2InOutIn() {
1367  VecPt3d pts{{0, 10, 0}, {10, 10, 0}, {10, 20, 0}, {0, 20, 0},
1368  {10, 0, 0}, {20, 0, 0}, {20, 10, 0}};
1369  VecInt2d polys = {{0, 1, 2, 3}, {4, 5, 6, 1}};
1370  VecInt expectedIds = {1, -1, 2, -1}; // old: (1)(2)
1371  VecDbl expectedTvals = {0.0, 0.2, 0.8, 1.0};
1372  VecPt3d expectedPoints = {
1373  {8.0, 18.0, 0.0}, {10.0, 16.0, 0.0}, {16.0, 10.0, 0.0}, {18.0, 8.0, 0.0}};
1374  iRunTest(8, 18, 18, 8, pts, polys, expectedIds, expectedTvals,
1375  expectedPoints);
1376 } // GmMultiPolyIntersectorUnitTests::test2InOutIn
1377 //------------------------------------------------------------------------------
1381 //
1382 // (0, 0)
1383 // 0-------------1-------------2
1384 // |\ 4 /|\ 8 /|
1385 // | \ 1 / | \ / |
1386 // | \ / | \ / |
1387 // | 1 3 3 | 5 4 7 |
1388 // | / \ | / \ |
1389 // | / \ | / 2 \ |
1390 // |/ 2 \|/ 6 \|
1391 // 5-------------6-------------7
1392 // (20, -10)
1394 //------------------------------------------------------------------------------
1395 void GmMultiPolyIntersectorUnitTests::testInsideToInside() {
1396  VecPt3d pts;
1397  VecInt2d polys;
1398  trBuildGridTrianglePolys(1, 2, pts, polys);
1399 
1400  VecInt expectedIds{4, 3, 5, 6, -1};
1401  VecDbl expectedTvals{0.0, 0.166666, 0.5, 0.833333, 1.0};
1402  VecPt3d expectedPoints = {{5.0, -2.5, 0.0},
1403  {6.6666666666667, -3.333333333333, 0.0},
1404  {10.0, -5.0, 0.0},
1405  {13.333333333333, -6.666666666667, 0.0},
1406  {15.0, -7.5, 0.0}};
1407  iRunTest(5, -2.5, 15, -7.5, pts, polys, expectedIds, expectedTvals,
1408  expectedPoints);
1409 } // GmMultiPolyIntersectorUnitTests::testInsideToInside
1410 //------------------------------------------------------------------------------
1414 //
1415 // (0, 0)
1416 // 1 0-------------1-------------2
1417 // |\ 4 /|\ 8 /|
1418 // | \ / | \ / |
1419 // | \ / | \ / |
1420 // | 1 3 3 | 5 4 7 |
1421 // | / \ | / \ |
1422 // | / \ | / \ |
1423 // |/ 2 \|/ 6 \|
1424 // 5-------------6-------------7 2
1425 // (20, -10)
1427 //------------------------------------------------------------------------------
1428 void GmMultiPolyIntersectorUnitTests::testOutsideToOutside() {
1429  VecPt3d pts;
1430  VecInt2d polys;
1431  trBuildGridTrianglePolys(1, 2, pts, polys);
1432 
1433  VecInt expectedIds{1, 4, 3, 5, 6, 7, -1};
1434  VecDbl expectedTvals{0.0454545, 0.0833333, 0.34375, 0.5,
1435  0.65625, 0.916667, 0.954545};
1436  VecPt3d expectedPoints = {
1437  {0.0, -0.454545454545, 0.0}, {0.8333333333333, -0.833333333333, 0.0},
1438  {6.5625, -3.4375, 0.0}, {10.0, -5.0, 0.0},
1439  {13.4375, -6.5625, 0.0}, {19.166666666667, -9.166666666667, 0.0},
1440  {20.0, -9.545454545455, 0.0}};
1441  iRunTest(-1, 0, 21, -10, pts, polys, expectedIds, expectedTvals,
1442  expectedPoints);
1443 } // GmMultiPolyIntersectorUnitTests::testOutsideToOutside
1444 //------------------------------------------------------------------------------
1448 //
1449 // 1
1450 //(0,0) /
1451 // 0-------------1-------------2
1452 // /|\ 4 /|\ 8 /|
1453 // 2 | \ / | \ / |
1454 // | \ / | \ / |
1455 // | 1 3 3 | 5 4 7 |
1456 // | / \ | / \ |
1457 // | / \ | / \ |
1458 // |/ 2 \|/ 6 \|
1459 // 5-------------6-------------7 2
1460 // (20, -10)
1462 //------------------------------------------------------------------------------
1463 void GmMultiPolyIntersectorUnitTests::testTouchesVertex() {
1464  VecPt3d pts;
1465  VecInt2d polys;
1466  trBuildGridTrianglePolys(1, 2, pts, polys);
1467  // SurfaceIter crashes on this. We return no intersection.
1468  VecInt expectedIds;
1469  VecDbl expectedTvals;
1470  VecPt3d expectedPoints = {};
1471  iRunTest(1, 1, -1, -1, pts, polys, expectedIds, expectedTvals,
1472  expectedPoints);
1473 } // GmMultiPolyIntersectorUnitTests::testTouchesVertex
1474 //------------------------------------------------------------------------------
1478 //
1479 // (0, 0)
1480 // 0-------------1-------------2
1481 // 1 |\ 4 /|\ 8 /|
1482 // \ | \ / | \ / |
1483 // 2| \ / | \ / |
1484 // | 1 3 3 | 5 4 7 |
1485 // | / \ | / \ |
1486 // | / \ | / \ |
1487 // |/ 2 \|/ 6 \|
1488 // 5-------------6-------------7 2
1489 // (20, -10)
1491 //------------------------------------------------------------------------------
1492 void GmMultiPolyIntersectorUnitTests::testTouchesEdge() {
1493 #ifdef __linux__
1494  TS_SKIP("GREENBUILD: This test does not pass on Linux builds.");
1495 #endif
1496  VecPt3d pts;
1497  VecInt2d polys;
1498  trBuildGridTrianglePolys(1, 2, pts, polys);
1499  VecInt expectedIds{1, -1};
1500  VecDbl expectedTvals{1.0, 1.0};
1501  VecPt3d expectedPoints = {{0.0, -2.0, 0.0}, {0.0, -2.0, 0.0}};
1502  iRunTest(-1, -1, 0, -2, pts, polys, expectedIds, expectedTvals,
1503  expectedPoints);
1504 } // GmMultiPolyIntersectorUnitTests::testTouchesEdge
1505 //------------------------------------------------------------------------------
1509 //
1510 // (0, 0)
1511 // +-------------+-------------+-------------+
1512 // |\ 4 /|\ 8 /|\ 12 /|
1513 // | \ / | \ / | \ / |
1514 // | \ / | \ / | \ / |
1515 // | 1 x 3 | 5 x 7 | 9 x 11 |
1516 // | / 1 | / \ | / \ |
1517 // | / \ | / \ | / \ |
1518 // |/ 2 \|/ 6 \|/ 10 \|
1519 // +-------------+-------------+-------------+
1520 // |\ 16 /|\ 20 /|\ 24 /|
1521 // | \ / | \ / | \ / |
1522 // | \ / | \ / | \ / |
1523 // | 13 x 15 | 17 x 19 | 21 x 23 |
1524 // | / \ | / \ | / \ |
1525 // | / \ | / \ | / \ |
1526 // |/ 14 \|/ 18 \|/ 22 \|
1527 // +-------------+-------------+-------------+
1528 // |\ 28 /|\ 32 /|\ 36 /|
1529 // | \ / | \ / | \ / |
1530 // | \ / | \ / | 2 / |
1531 // | 25 x 27 | 29 x 31 | 33 x 35 |
1532 // | / \ | / \ | / \ |
1533 // | / \ | / \ | / \ |
1534 // |/ 26 \|/ 30 \|/ 34 \|
1535 // +-------------+-------------+-------------+
1536 // (30, -30)
1538 //------------------------------------------------------------------------------
1539 void GmMultiPolyIntersectorUnitTests::testAlongEdgesInsideToInside() {
1540  // TS_FAIL("GmMultiPolyIntersectorUnitTests::testAlongEdgesInsideToInside");
1541 
1542  VecPt3d pts;
1543  VecInt2d polys;
1544  trBuildGridTrianglePolys(3, 3, pts, polys);
1545 
1546  // MfMapLayerUGridImp::TraverseLineSegment results
1547  // VecInt expectedIds = {3,17,18,33,-1};
1548  // VecDbl expectedTvals = {0.0,0.22222,0.5,0.777778,1.0};
1549  VecInt expectedIds{2, 17, 18, 33, -1};
1550  VecDbl expectedTvals{0.0, 0.22222, 0.5, 0.777778, 1.0};
1551  VecPt3d expectedPoints = {{6.0, -6.0, 0.0},
1552  {10.0, -10.0, 0.0},
1553  {15.0, -15.0, 0.0},
1554  {20.0, -20.0, 0.0},
1555  {24.0, -24.0, 0.0}};
1556  iRunTest(6, -6, 24, -24, pts, polys, expectedIds, expectedTvals,
1557  expectedPoints);
1558 
1559 } // GmMultiPolyIntersectorUnitTests::testAlongEdgesInsideToInside
1560 //------------------------------------------------------------------------------
1564 //
1565 // (0, 0)
1566 // 0-------------1-------------2-------------3
1567 // |\ 4 /|\ 8 /|\ 12 /|
1568 // | \ / | \ / | \ / |
1569 // | \ / | \ / | \ / |
1570 // | 1 12 3 | 5 13 7 | 9 14 11 |
1571 // | / \ | / \ | / \ |
1572 // | / \ | / \ | / \ |
1573 // |/ 2 \|/ 6 \|/ 10 \|
1574 // 1 4-------------5-------------6-------------7 2
1575 // |\ 16 /|\ 20 /|\ 24 /|
1576 // | \ / | \ / | \ / |
1577 // | \ / | \ / | \ / |
1578 // | 13 15 15 | 17 16 19 | 21 17 23 |
1579 // | / \ | / \ | / \ |
1580 // | / \ | / \ | / \ |
1581 // |/ 14 \|/ 18 \|/ 22 \|
1582 // 8-------------9------------10------------11
1583 // (30, -20)
1585 //------------------------------------------------------------------------------
1586 void GmMultiPolyIntersectorUnitTests::testAlongEdgesOutsideToOutside() {
1587  VecPt3d pts;
1588  VecInt2d polys;
1589  trBuildGridTrianglePolys(2, 3, pts, polys);
1590 
1591  // VecInt expectedIds = {16,20,24,23,-1}; SurfaceIter results
1592  // MfMapLayerUGridImp::TraverseLineSegment results:
1593  VecInt expectedIds{16, 20, 24, -1};
1594  VecDbl expectedTvals{0.016129032258064516, 0.33870967741935482,
1595  0.66129032258064513, 0.98387096774193550};
1596  VecPt3d expectedPoints = {{0.0, -10.0, 0.0},
1597  {10.0, -10.0, 0.0},
1598  {20.0, -10.0, 0.0},
1599  {30.0, -10.0, 0.0}};
1600  iRunTest(-0.5, -10, 30.5, -10, pts, polys, expectedIds, expectedTvals,
1601  expectedPoints);
1602 } // GmMultiPolyIntersectorUnitTests::testAlongEdgesOutsideToOutside
1603 //------------------------------------------------------------------------------
1607 //
1608 // (0, 0)
1609 // +-------------+-------------+
1610 // |\ 4 /|\ 8 /|
1611 // | \ / | \ / |
1612 // | \ / 1 | \ / |
1613 // | 1 x 3 | 5 x 7 |
1614 // | / \ | / \ | 2
1615 // | / \ | / \ |
1616 // |/ 2 \|/ 6 \|
1617 // +-------------+-------------+
1618 // (20, -10)
1620 //------------------------------------------------------------------------------
1621 void GmMultiPolyIntersectorUnitTests::testEdgeThroughOppositeVertexAtAngle() {
1622  // TS_FAIL("GmMultiPolyIntersectorUnitTests::testEdgeThroughOppositeVertexAtAngle");
1623 
1624  VecPt3d pts;
1625  VecInt2d polys;
1626  trBuildGridTrianglePolys(1, 2, pts, polys);
1627 
1628  // MfMapLayerUGridImp::TraverseLineSegment results
1629  // VecInt expectedIds = {3,5,7,-1};
1630  // VecDbl expectedTvals = {0.0,0.14285714285714288,0.5,0.85714285714285721};
1631  VecInt expectedIds{3, 5, 7, -1};
1632  VecDbl expectedTvals{0.0, 0.14285714285714288, 0.5, 0.85714285714285721};
1633  VecPt3d expectedPoints = {{8.0, -2.5, 0.0},
1634  {10.0, -3.214285714286, 0.0},
1635  {15.0, -5.0, 0.0},
1636  {20.0, -6.785714285714, 0.0}};
1637  iRunTest(8, -2.5, 22, -7.5, pts, polys, expectedIds, expectedTvals,
1638  expectedPoints);
1639 
1640 } // GmMultiPolyIntersectorUnitTests::testEdgeThroughOppositeVertexAtAngle
1641 //------------------------------------------------------------------------------
1645 //
1646 // (0, 0) 2
1647 // +-------------+-------------+
1648 // |\ 4 /|\ 8 /|
1649 // | \ / | \ / |
1650 // | \ / | \ / |
1651 // | 1 x 3 | 5 x 7 |
1652 // | / \ | / \ |
1653 // | / \ 1 / \ |
1654 // |/ 2 \|/ 6 \|
1655 // +-------------+-------------+
1656 // (20, -10)
1658 //------------------------------------------------------------------------------
1659 void GmMultiPolyIntersectorUnitTests::testStartAtEdgeThroughAdjacent() {
1660  // TS_FAIL("GmMultiPolyIntersectorUnitTests::testStartAtEdgeThroughAdjacent");
1661 
1662  VecPt3d pts;
1663  VecInt2d polys;
1664  trBuildGridTrianglePolys(1, 2, pts, polys);
1665 
1666  // MfMapLayerUGridImp::TraverseLineSegment results
1667  // VecInt expectedIds = {5,8,-1};
1668  // VecDbl expectedTvals = {0.0,0.4,0.8};
1669  VecInt expectedIds{5, 8, -1};
1670  VecDbl expectedTvals{0.0, 0.4, 0.8};
1671  VecPt3d expectedPoints = {
1672  {10.0, -8.0, 0.0}, {14.0, -4.0, 0.0}, {18.0, 0.0, 0.0}};
1673  iRunTest(10, -8, 20, 2, pts, polys, expectedIds, expectedTvals,
1674  expectedPoints);
1675 } // GmMultiPolyIntersectorUnitTests::testStartAtEdgeThroughAdjacent
1676 //------------------------------------------------------------------------------
1682 //
1683 // (0, 0)
1684 // +-------------+-------------+
1685 // |\ 4 /|\ 8 /|
1686 // | \ / | \ / |
1687 // | \ / | \ / |
1688 // | 1 x 3 | 5 x 7 |
1689 // | / \ | / \ |
1690 // | / \ | / \ |
1691 // |/ 2 \|/ 6 \|
1692 // +-------------+-------------+
1693 // (20, -10)
1695 //------------------------------------------------------------------------------
1696 void GmMultiPolyIntersectorUnitTests::testInsideToEdgeThenThroughAdjacent() {
1697 // TS_FAIL("GmMultiPolyIntersectorUnitTests::testInsideToEdgeThenThroughAdjacent");
1698 #ifdef __linux__
1699  TS_SKIP("GREENBUILD: This test does not pass on Linux builds.");
1700 #endif
1701  VecPt3d pts;
1702  VecInt2d polys;
1703  trBuildGridTrianglePolys(1, 2, pts, polys);
1704 
1705  // MfMapLayerUGridImp::TraverseLineSegment results
1706  // VecInt expectedIds = {3,-1};
1707  // VecDbl expectedTvals = {0.0,1.0};
1708  VecInt expectedIds{3, -1};
1709  VecDbl expectedTvals{0.0, 1.0};
1710  VecPt3d expectedPoints = {{9.0, -5.0, 0.0}, {10.0, -8.0, 0.0}};
1711  iRunTest(9, -5, 10, -8, pts, polys, expectedIds, expectedTvals,
1712  expectedPoints);
1713 } // GmMultiPolyIntersectorUnitTests::testInsideToEdgeThenThroughAdjacent
1714 //------------------------------------------------------------------------------
1718 //------------------------------------------------------------------------------
1719 void GmMultiPolyIntersectorUnitTests::testMap2MfBug() {
1720  VecPt3d pts{{1937.0003414079, 11829.937474193, 0.0},
1721  {1947.0331979019, 11744.658193995, 0.0},
1722  {1806.3085553039, 11640.957366058, 0.0},
1723  {1827.8055464927, 11817.091027732, 0.0},
1724  {2046.1951363232, 11842.783920654, 0.0},
1725  {2155.4908205085, 11854.643944679, 0.0},
1726  {2160.8354359402, 11805.390806652, 0.0},
1727  {2070.1604445251, 11710.224742147, 0.0}};
1728  VecInt2d polys(2);
1729  polys[0] = {0, 3, 2, 1};
1730  polys[1] = {0, 1, 7, 6, 5, 4};
1731 
1732  const double t = 0.41350462827872492;
1733  VecInt expectedIds{2, -1, 2, 1, -1};
1734  VecDbl expectedTvals{0.0, 0.0, t, .5, 1.0};
1735  VecPt3d expectedPoints = {
1736  {2046.1951363232131, 11842.783920653745, 0.00000000000000000},
1737  {2046.1951363231999, 11842.783920653999, 0.00000000000000000},
1738  {1955.8900301603892, 11832.159790516887, 0.00000000000000000},
1739  {1937.0003414078999, 11829.937474193001, 0.00000000000000000},
1740  {1827.8055464926999, 11817.091027732000, 0.00000000000000000}};
1741  iRunTest(2046.1951363232131, 11842.783920653745, 1827.8055464926651,
1742  11817.091027732373, pts, polys, expectedIds, expectedTvals,
1743  expectedPoints);
1744  expectedIds = {1, 2, -1, 2, -1};
1745  expectedTvals = {0.0, .5, 1 - t, 1, 1};
1746  expectedPoints = {{1827.8055464927, 11817.091027732, 0.0},
1747  {1937.0003414079, 11829.937474193, 0.0},
1748  {1955.8909579942, 11832.159899674, 0.0},
1749  {2046.1951363232, 11842.783920654, 0.0},
1750  {2046.1951363232, 11842.783920654, 0.0}};
1751  iRunTest(1827.8055464926651, 11817.091027732373, 2046.1951363232131,
1752  11842.783920653745, pts, polys, expectedIds, expectedTvals,
1753  expectedPoints);
1754 } // GmMultiPolyIntersectorUnitTests::testInsideToEdgeThenThroughAdjacent
1755 //------------------------------------------------------------------------------
1759 //
1760 // (0, 0)
1761 // +-------------+-------------+
1762 // |\ 4 /|\ 8 /|
1763 // | \ / | \ / |
1764 // | \ / | \ / |
1765 // | 1 x 3 | 5 x 7 |
1766 // | / \ | / \ |
1767 // | / \ | / \ |
1768 // |/ 2 \|/ 6 \|
1769 // +-------------+-------------+
1770 // (20, -10)
1772 //------------------------------------------------------------------------------
1773 void GmMultiPolyIntersectorUnitTests::testEndAtEdgeFromAdjacent() {
1774  // TS_FAIL("GmMultiPolyIntersectorUnitTests::testEndAtEdgeFromAdjacent");
1775 
1776  VecPt3d pts;
1777  VecInt2d polys;
1778  trBuildGridTrianglePolys(1, 2, pts, polys);
1779 
1780  // MfMapLayerUGridImp::TraverseLineSegment results
1781  // VecInt expectedIds = {8,5,-1};
1782  // VecDbl expectedTvals = {0.2,0.6,1.0};
1783  VecInt expectedIds{8, 5, -1};
1784  VecDbl expectedTvals{0.2, 0.6, 1.0};
1785  VecPt3d expectedPoints = {{18.0, 0.0}, {14.0, -4.0, 0.0}, {10.0, -8.0, 0.0}};
1786  iRunTest(20, 2, 10, -8, pts, polys, expectedIds, expectedTvals,
1787  expectedPoints);
1788 } // GmMultiPolyIntersectorUnitTests::testEndAtEdgeFromAdjacent
1789 //------------------------------------------------------------------------------
1791 //------------------------------------------------------------------------------
1792 void GmMultiPolyIntersectorUnitTests::testSmsCase1() {
1793  VecPt3d pts{{-39.719999999999999, 90.079999999999998, 0.0},
1794  {-21.129999999999999, 90.469999999999999, 1.0},
1795  {-38.930000000000000, 75.840000000000003, 2.0},
1796  {-20.539999999999999, 76.629999999999995, 3.0},
1797  {-39.719999999999999, 62.000000000000000, 4.0},
1798  {-20.539999999999999, 61.609999999999999, 5.0},
1799  {-40.509999999999998, 47.770000000000003, 6.0},
1800  {-20.150000000000002, 46.579999999999998, 7.0},
1801  {-41.100000000000001, 30.370000000000001, 8.0},
1802  {-19.550000000000001, 29.379999999999999, 9.0}};
1803  VecInt2d polys(8);
1804  polys[0] = {7, 5, 6};
1805  polys[1] = {3, 2, 5};
1806  polys[2] = {2, 3, 1};
1807  polys[3] = {9, 7, 8};
1808  polys[4] = {7, 6, 8};
1809  polys[5] = {0, 2, 1};
1810  polys[6] = {5, 2, 4};
1811  polys[7] = {4, 6, 5};
1812 
1813  VecInt expectedIds{6, 3, 2, 7, 8, 1, 5, 4, -1};
1814  VecDbl expectedTvals{
1815  0.065777232109665892, 0.18968813237387866, 0.26837085508795250,
1816  0.35199491192297022, 0.47395399691316503, 0.58799734941084614,
1817  0.68358069055240822, 0.81969307266961533, 0.93250275302111885};
1818  VecPt3d expectedPoints = {{-31.97119143306, 90.242562417488, 0.0},
1819  {-31.8980840019, 81.619602868102, 0.0},
1820  {-31.8516611955, 76.144072194429, 0.0},
1821  {-31.80232300197, 70.32467407928, 0.0},
1822  {-31.73036714182, 61.837541354813, 0.0},
1823  {-31.66308156385, 53.901264454499, 0.0},
1824  {-31.60668739257, 47.249619744458, 0.0},
1825  {-31.52638108712, 37.777559072921, 0.0},
1826  {-31.45982337572, 29.92713341726, 0.0}};
1827  iRunTest(-32.009999999999998, 94.819999999999993, -31.420000000000002,
1828  25.230000000000000, pts, polys, expectedIds, expectedTvals,
1829  expectedPoints);
1830 } // GmMultiPolyIntersectorUnitTests::testSmsCase1
1831 
1836 //------------------------------------------------------------------------------
1839 //------------------------------------------------------------------------------
1840 #ifndef CXXTEST4
1841 const CxxTest::TestGroup &GmMultiPolyIntersector2IntermediateTests::group() {
1842  return *CxxTest::TestGroup::GetGroup(CxxTest::TG_INTERMEDIATE);
1843 } // GmMultiPolyIntersector2IntermediateTests::group
1844 #endif
1845 //------------------------------------------------------------------------------
1847 //------------------------------------------------------------------------------
1848 void GmMultiPolyIntersector2IntermediateTests::testLargeNumPolys() {
1849  // TS_FAIL("GmMultiPolyIntersectorUnitTests::testHuge");
1850 
1851  // Like testAlongEdgesInsideToInside but with many more polygons
1852 
1853  VecPt3d pts;
1854  VecInt2d polys;
1855  trBuildGridTrianglePolys(1000, 3, pts, polys);
1856  // Results in 120,000 polygons, 70,004 points
1857 
1858  // MfMapLayerUGridImp::TraverseLineSegment results
1859  // VecInt expectedIds = {3,17,18,33,-1};
1860  // VecDbl expectedTvals = {0.0,0.22222,0.5,0.777778,1.0};
1861  VecInt expectedIds{2, 17, 18, 33, -1};
1862  VecDbl expectedTvals{0.0, 0.22222, 0.5, 0.777778, 1.0};
1863  VecPt3d expectedPoints = {{6.0, -6.0, 0.0},
1864  {10.0, -10.0, 0.0},
1865  {15.0, -15.0, 0.0},
1866  {20.0, -20.0, 0.0},
1867  {24.0, -24.0, 0.0}};
1868  iRunTest(6, -6, 24, -24, pts, polys, expectedIds, expectedTvals,
1869  expectedPoints);
1870 
1871 } // GmMultiPolyIntersector2IntermediateTests::testLargeNumPolys
1872 //------------------------------------------------------------------------------
1874 //------------------------------------------------------------------------------
1875 void GmMultiPolyIntersector2IntermediateTests::testLargeNumPolysAndSegments() {
1876  // TS_FAIL("GmMultiPolyIntersectorUnitTests::testHuge");
1877 
1878  // Like testAlongEdgesInsideToInside but with many more polygons
1879 
1880  VecPt3d pts;
1881  VecInt2d polys;
1882  trBuildGridTrianglePolys(1000, 3, pts, polys);
1883  // Results in 120,000 polygons, 70,004 points
1884 
1885  VecInt expectedIds = {2, 17, 18, 33, -1};
1886  VecDbl expectedTvals = {0.0, 0.22222, 0.5, 0.777778, 1.0};
1887  BSHP<GmMultiPolyIntersectionSorter> sorter =
1888  BSHP<GmMultiPolyIntersectionSorter>(
1889  new GmMultiPolyIntersectionSorterTerse());
1890  BSHP<GmMultiPolyIntersector> mpi =
1891  GmMultiPolyIntersector::New(pts, polys, sorter);
1892  VecInt polyIds;
1893  VecDbl tValues;
1894  const int nIntersectingLines =
1895  /*1e5*/ 1000; // Go big for serious timing testing
1896  for (size_t i = 0; i < nIntersectingLines; ++i) {
1897  // 3 different segments repeated
1898  mpi->TraverseLineSegment(6, -6, 24, -24, polyIds, tValues);
1899  mpi->TraverseLineSegment(7, -6, 25, -24, polyIds, tValues);
1900  mpi->TraverseLineSegment(25, -6, 6, -24, polyIds, tValues);
1901  // Don't need to check that the values are correct. That is done in
1902  // testLargeNumPolys
1903  }
1904 
1905 } // GmMultiPolyIntersector2IntermediateTests::testLargeNumPolysAndSegments
1906 
1907  //} // namespace xms
1908 
1909 #endif
xms::GmMultiPolyIntersectorImpl::GetBoostPoly
GmBstPoly3d & GetBoostPoly(int a_polyIdx)
Create and return a boost polygon given a polygon index.
Definition: GmMultiPolyIntersector.cpp:238
xms::GmMultiPolyIntersectorData::m_polys
std::vector< std::vector< int > > m_polys
0-based? indices into m_points to form polygons
Definition: GmMultiPolyIntersectorData.h:52
xms::GmMultiPolyIntersectorImpl::m_query
GmMultiPolyIntersectorQueryEnum m_query
Type of query (intersect, covered by...)
Definition: GmMultiPolyIntersector.cpp:109
xms::GmMultiPolyIntersectorImpl::GetPolysForPoint
void GetPolysForPoint(Pt3d pt, SetInt &poly)
Find the set of polygons intersected (in or on) by the point.
Definition: GmMultiPolyIntersector.cpp:310
xms::GmMultiPolyIntersector
See GmMultiPolyIntersectorImpl comments.
Definition: GmMultiPolyIntersector.h:34
GmMultiPolyIntersector.h
GmMultiPolyIntersectorUnitTests::testSmsCase1
void testSmsCase1()
This case revealed the need for a tolerance when comparing t values.
Definition: GmMultiPolyIntersector.cpp:1792
xms::XM_DBL_LOWEST
static const double XM_DBL_LOWEST
GmMultiPolyIntersectorUnitTests::testMap2MfBug
void testMap2MfBug()
We only do the first part: inside to edge.
Definition: GmMultiPolyIntersector.cpp:1719
XM_NONE
#define XM_NONE
triangles.h
Functions dealing with triangles.
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:394
xms::GmMultiPolyIntersectorImpl::m_rtree
RtreeBox * m_rtree
Rtree used to find polygons.
Definition: GmMultiPolyIntersector.cpp:101
xms::GmMultiPolyIntersectorImpl::m_line
GmBstLine3d m_line
Current line segment.
Definition: GmMultiPolyIntersector.cpp:102
xms::GmMultiPolyIntersectorImpl
Used to intersect a line segment with any number of polygons in 2D. Returns the intersected polygons ...
Definition: GmMultiPolyIntersector.cpp:61
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:206
xms::GmMultiPolyIntersectorImpl::SetQuery
virtual void SetQuery(GmMultiPolyIntersectorQueryEnum a_query) override
Set the query to use (covered by, intersects...).
Definition: GmMultiPolyIntersector.cpp:301
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:140
xms::GmMultiPolyIntersectorImpl::IntersectEachPolyWithLine
void IntersectEachPolyWithLine()
Go through results (potential polygons) and intersect each one.
Definition: GmMultiPolyIntersector.cpp:339
xms::GmMultiPolyIntersectorImpl::m_d
GmMultiPolyIntersectorData m_d
Point and poly data.
Definition: GmMultiPolyIntersector.cpp:98
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:1395
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:1428
xms::ix
An intersection point of a line with a polygon.
Definition: GmMultiPolyIntersectorData.h:24
xms::GmMultiPolyIntersectorData::m_polys2
std::set< int > m_polys2
polygon IDs (1-based) that 2nd point is inside on on
Definition: GmMultiPolyIntersectorData.h:54
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:1539
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:1773
xms::GmMultiPolyIntersectorImpl::SortIntersections
void SortIntersections()
Does a preliminary sort of the intersections by t value.
Definition: GmMultiPolyIntersector.cpp:405
xms::GmMultiPolyIntersectorImpl::CreateLine
void CreateLine()
Creates a boost geom line of the current line segment.
Definition: GmMultiPolyIntersector.cpp:293
xms::VecInt
std::vector< int > VecInt
xms::SetInt
std::set< int > SetInt
xms::GmMultiPolyIntersectorImpl::m_boostPolys
std::vector< GmBstPoly3d > m_boostPolys
Polygons as boost geom polygons.
Definition: GmMultiPolyIntersector.cpp:105
xms::GmMultiPolyIntersectorImpl::BuildRTree
void BuildRTree()
Create a boost rtree of polygon extents.
Definition: GmMultiPolyIntersector.cpp:262
GmMultiPolyIntersectionSorterTerse.h
boost_defines.h
xms::ix::m_t
double m_t
t values
Definition: GmMultiPolyIntersectorData.h:44
xms::GmMultiPolyIntersectorImpl::m_pt1
Pt3d m_pt1
1st line segment point
Definition: GmMultiPolyIntersector.cpp:99
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:104
xms::GmMultiPolyIntersectorImpl::m_buffer
double m_buffer
Small buffer around each bounding box.
Definition: GmMultiPolyIntersector.cpp:103
xms::VecDbl
std::vector< double > VecDbl
xms::GmMultiPolyIntersectorData::m_polys1
std::set< int > m_polys1
polygon IDs (1-based) that 1st point is inside or on
Definition: GmMultiPolyIntersectorData.h:53
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:1463
xms::GmMultiPolyIntersectorImpl::GmMultiPolyIntersectorImpl
GmMultiPolyIntersectorImpl(const VecPt3d &a_points, const VecInt2d &a_polys, BSHP< GmMultiPolyIntersectionSorter > a_sorter, int a_startingId=1)
constructor
Definition: GmMultiPolyIntersector.cpp:164
xms::GmMultiPolyIntersectorImpl::PolygonFromPoint
virtual int PolygonFromPoint(const Pt3d &a_pt) override
Finds the polygon containing the point.
Definition: GmMultiPolyIntersector.cpp:519
xms::GmMultiPolyIntersectorImpl::m_sorter
BSHP< GmMultiPolyIntersectionSorter > m_sorter
Sorter used to process results.
Definition: GmMultiPolyIntersector.cpp:107
GmMultiPolyIntersector2IntermediateTests::group
virtual const CxxTest::TestGroup & group()
Returns the test group.
Definition: GmMultiPolyIntersector.cpp:1841
XM_ENSURE_TRUE_VOID_NO_ASSERT
#define XM_ENSURE_TRUE_VOID_NO_ASSERT(...)
xms::GmMultiPolyIntersectorImpl::TraverseLineSegmentAll
void TraverseLineSegmentAll(double a_x1, double a_y1, double a_x2, double a_y2, VecInt &a_polyids, VecDbl &a_tvalues, std::vector< Pt3d > &a_pts)
Intersect segment with polys and save intersected polys, t-values, and intersection points...
Definition: GmMultiPolyIntersector.cpp:546
xms::VecPt3d
std::vector< Pt3d > VecPt3d
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:369
XM_NODATA
#define XM_NODATA
xms::GmMultiPolyIntersectorData::m_ixs
std::vector< ix > m_ixs
Intersections.
Definition: GmMultiPolyIntersectorData.h:55
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:1875
XM_ASSERT
#define XM_ASSERT(x)
xms::GmMultiPolyIntersectorData
Struct used by GmMultiPolyIntersector.
Definition: GmMultiPolyIntersectorData.h:49
GmMultiPolyIntersectorData.h
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:449
GmMultiPolyIntersector2IntermediateTests::testLargeNumPolys
void testLargeNumPolys()
Test a large number of polygons for speed.
Definition: GmMultiPolyIntersector.cpp:1848
XmError.h
XmLog.h
xms::GmMultiPolyIntersectorImpl::EnsureEndPointsRepresented
void EnsureEndPointsRepresented()
Because unfortunately intersecting the line with the poly doesn't always create an intersection if a ...
Definition: GmMultiPolyIntersector.cpp:417
xms::VecInt2d
std::vector< VecInt > VecInt2d
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:1659
GmMultiPolyIntersectionSorter.h
xms::GmMultiPolyIntersectionSorterTerse
Class for sorting intersections from GmMultiPolyIntersector in a terse way (with no duplicate info)...
Definition: GmMultiPolyIntersectionSorterTerse.h:32
TS_ASSERT_EQUALS_VEC
#define TS_ASSERT_EQUALS_VEC(a, b)
GmMultiPolyIntersector.t.h
xms::GmMultiPolyIntersectorImpl::TraverseLineSegment
virtual void TraverseLineSegment(double x1, double y1, double x2, double y2, VecInt &polyids, VecDbl &tvalues) override
Intersect segment with polys and save intersected polys and t-values.
Definition: GmMultiPolyIntersector.cpp:475
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:1696
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:227
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:1492
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:1586
TS_ASSERT_DELTA_VEC
#define TS_ASSERT_DELTA_VEC(a, b, delta)
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:1621
xms::GmMultiPolyIntersectorData::m_points
std::vector< Pt3d > m_points
All points used by all polygons.
Definition: GmMultiPolyIntersectorData.h:51
xms::XM_DBL_HIGHEST
static const double XM_DBL_HIGHEST
xms::GmMultiPolyIntersectorImpl::BuildBoostPoly
void BuildBoostPoly(int a_polyIdx, GmBstPoly3d &a_boostPoly) const
Build a boost polygon given a polygon index.
Definition: GmMultiPolyIntersector.cpp:250