xmsgeom  1.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
TrTin.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/triangulate/TrTin.h>
15 
16 // 3. Standard library headers
17 #include <cfloat>
18 #include <numeric>
19 #include <ostream>
20 #include <sstream>
21 
22 // 4. External library headers
23 #include <boost/bind.hpp>
24 #include <boost/archive/text_iarchive.hpp>
25 #include <boost/archive/text_oarchive.hpp>
26 #include <boost/serialization/export.hpp>
27 #include <boost/serialization/vector.hpp>
28 #include <boost/unordered_set.hpp>
29 
30 // 5. Shared code headers
31 #include <xmscore/misc/StringUtil.h>
32 #include <xmscore/stl/set.h>
33 #include <xmscore/stl/vector.h>
34 #include <xmsgeom/geometry/geoms.h>
35 #include <xmscore/misc/boost_defines.h>
36 #include <xmsgeom/triangulate/triangles.h>
37 #include <xmscore/misc/XmError.h>
38 #include <xmscore/misc/xmstype.h>
39 #include <xmscore/misc/XmConst.h>
40 
41 // 6. Non-shared code headers
42 
43 //----- Namespace declaration --------------------------------------------------
44 
45 namespace xms
46 {
47 //----- Forward declarations ---------------------------------------------------
48 
49 //----- External globals -------------------------------------------------------
50 
51 //----- Constants / Enumerations -----------------------------------------------
52 
53 //----- Classes / Structs ------------------------------------------------------
54 
56 class TrTinImpl : public TrTin
57 {
59  friend class boost::serialization::access;
61 public:
62  TrTinImpl();
63  virtual ~TrTinImpl();
64 
65  // Setters
66  virtual void SetPoints(BSHP<VecPt3d> a_pts) override;
67  virtual void SetTriangles(BSHP<VecInt> a_tris) override;
68  virtual void SetTrianglesAdjacentToPoints(BSHP<VecInt2d> a_trisAdjToPts) override;
69  virtual void SetGeometry(BSHP<VecPt3d> a_pts,
70  BSHP<VecInt> a_tris,
71  BSHP<VecInt2d> a_trisAdjToPts) override;
72 
73  // Getters
74  virtual VecPt3d& Points() override;
75  virtual VecInt& Triangles() override;
76  virtual VecInt2d& TrisAdjToPts() override;
77 
78  virtual const VecPt3d& Points() const override;
79  virtual const VecInt& Triangles() const override;
80  virtual const VecInt2d& TrisAdjToPts() const override;
81 
82  virtual BSHP<VecPt3d> PointsPtr() override;
83  virtual BSHP<VecInt> TrianglesPtr() override;
84 
85  virtual int NumPoints() const override;
86  virtual int NumTriangles() const override;
87 
88  // "tr" equivalent functions (trTriangleFromEdge, trIndex etc)
89 
90  // Non modifiers
91  virtual bool TriangleFromEdge(int a_pt1,
92  int a_pt2,
93  int& a_tri,
94  int& a_idx1,
95  int& a_idx2) const override;
96  virtual int TriangleAdjacentToEdge(int a_pt1, int a_pt2) const override;
97  virtual int LocalIndex(int a_tri, int a_pt) const override;
98  virtual int GlobalIndex(int a_triIdx, int a_localVtxIdx) const override;
99  virtual bool VerticesAreAdjacent(int a_pt1, int a_pt2) const override;
100  virtual int CommonEdgeIndex(int a_tri, int a_adjTri) const override;
101  virtual int AdjacentTriangle(int a_triIdx, int a_edgeIdx) const override;
102  virtual Pt3d TriangleCentroid(int a_tri) const override;
103  virtual double TriangleArea(int a_tri) const override;
104  // virtual int FirstBoundaryPoint () const;
105  virtual int NextBoundaryPoint(int a_point) const override;
106  virtual int PreviousBoundaryPoint(int a_point) const override;
107  virtual void GetBoundaryPoints(VecInt& a_boundaryPoints) const override;
108  virtual void GetBoundaryPolys(VecInt2d& a_polys) const override;
109  virtual bool GetExtents(Pt3d& a_mn, Pt3d& a_mx) const override;
110  virtual void ExportTinFile(std::ostream& a_os) const override;
111 
112  // Modifiers
113  virtual bool SwapEdge(int a_triA, int a_triB, bool a_checkAngle = true) override;
114  virtual void DeleteTriangles(const SetInt& a_trisToDelete) override;
115  virtual void DeletePoints(const SetInt& a_points) override;
116  virtual bool OptimizeTriangulation() override;
117  virtual void Clear() override;
118  virtual void BuildTrisAdjToPts() override;
119 
120  virtual std::string ToString() const override;
121  virtual void FromString(const std::string&) override;
122  template <typename Archive>
123  void serialize(Archive& archive, const unsigned int version);
124 
125 private:
126  void InsertAdjacentTriangle(int a_pt, int a_tri);
127  void DeleteAdjacentTriangle(int a_pt, int a_tri);
128  bool TriIndexFound(const int& a_triPt) const;
129  bool PointIndexFound(const Pt3d& a_point) const;
130  bool AdjacentIndexFound(const VecInt& a_point) const;
131  bool CheckAndSwap(int a_triA, int a_triB, bool a_propagate, const VecInt& a_flags);
132  bool PointIsInCircumcircle(int a_tri1, int a_tri2, int id);
133  void BuildTrisAdjToPtsConst() const;
134 
135  BSHP<VecPt3d> m_pts;
136  BSHP<VecInt> m_tris;
137  BSHP<VecInt2d> m_trisAdjToPts;
138  boost::unordered_set<int> m_toDelete;
139 
140 }; // class TrTinImpl
141 } // namespace xms
142 
143 BOOST_CLASS_EXPORT(xms::TrTinImpl);
144 // BOOST_CLASS_VERSION(xms::TrTinImpl, 1) // only if using version
145 
146 namespace xms
147 {
148 //----- Internal functions -----------------------------------------------------
149 
150 //----- Class / Function definitions -------------------------------------------
151 
157 //------------------------------------------------------------------------------
159 //------------------------------------------------------------------------------
160 TrTinImpl::TrTinImpl()
161 : m_pts(new VecPt3d())
162 , m_tris(new VecInt())
163 , m_trisAdjToPts(new VecInt2d())
164 , m_toDelete()
165 {
166 }
167 //------------------------------------------------------------------------------
169 //------------------------------------------------------------------------------
170 TrTinImpl::~TrTinImpl()
171 {
172 }
173 //------------------------------------------------------------------------------
176 //------------------------------------------------------------------------------
177 void TrTinImpl::SetPoints(BSHP<VecPt3d> a_pts)
178 {
179  m_pts = a_pts;
180 }
181 //------------------------------------------------------------------------------
184 //------------------------------------------------------------------------------
185 void TrTinImpl::SetTriangles(BSHP<VecInt> a_tris)
186 {
187  m_tris = a_tris;
188 }
189 //------------------------------------------------------------------------------
192 //------------------------------------------------------------------------------
193 void TrTinImpl::SetTrianglesAdjacentToPoints(BSHP<VecInt2d> a_trisAdjToPts)
194 {
195  m_trisAdjToPts = a_trisAdjToPts;
196 }
197 //------------------------------------------------------------------------------
202 //------------------------------------------------------------------------------
203 void TrTinImpl::SetGeometry(BSHP<VecPt3d> a_pts, BSHP<VecInt> a_tris, BSHP<VecInt2d> a_trisAdjToPts)
204 {
205  m_pts = a_pts;
206  m_tris = a_tris;
207  m_trisAdjToPts = a_trisAdjToPts;
208 } // TrTinImpl::SetGeometry
209 //------------------------------------------------------------------------------
212 //------------------------------------------------------------------------------
213 VecPt3d& TrTinImpl::Points()
214 {
215  return *m_pts.get();
216 }
217 //------------------------------------------------------------------------------
220 //------------------------------------------------------------------------------
221 VecInt& TrTinImpl::Triangles()
222 {
223  return *m_tris.get();
224 }
225 //------------------------------------------------------------------------------
228 //------------------------------------------------------------------------------
229 VecInt2d& TrTinImpl::TrisAdjToPts()
230 {
231  return *m_trisAdjToPts.get();
232 }
233 //------------------------------------------------------------------------------
236 //------------------------------------------------------------------------------
237 const VecPt3d& TrTinImpl::Points() const
238 {
239  return *m_pts.get();
240 }
241 //------------------------------------------------------------------------------
244 //------------------------------------------------------------------------------
245 const VecInt& TrTinImpl::Triangles() const
246 {
247  return *m_tris.get();
248 }
249 //------------------------------------------------------------------------------
252 //------------------------------------------------------------------------------
253 const VecInt2d& TrTinImpl::TrisAdjToPts() const
254 {
255  return *m_trisAdjToPts.get();
256 }
257 //------------------------------------------------------------------------------
260 //------------------------------------------------------------------------------
261 BSHP<VecPt3d> TrTinImpl::PointsPtr()
262 {
263  return m_pts;
264 }
265 //------------------------------------------------------------------------------
268 //------------------------------------------------------------------------------
269 BSHP<VecInt> TrTinImpl::TrianglesPtr()
270 {
271  return m_tris;
272 }
273 //------------------------------------------------------------------------------
276 //------------------------------------------------------------------------------
277 int TrTinImpl::NumPoints() const
278 {
279  return (int)(*m_pts).size();
280 }
281 //------------------------------------------------------------------------------
284 //------------------------------------------------------------------------------
285 int TrTinImpl::NumTriangles() const
286 {
287  return (int)(*m_tris).size() / 3;
288 }
289 //------------------------------------------------------------------------------
298 //------------------------------------------------------------------------------
299 bool TrTinImpl::TriangleFromEdge(int a_pt1,
300  int a_pt2,
301  int& a_tri,
302  int& a_localPt1,
303  int& a_localPt2) const
304 {
305  a_localPt1 = a_localPt2 = 0;
306 
307  // For each triangle adjacent to a_pt1
308  VecInt::const_iterator adj = (*m_trisAdjToPts)[a_pt1].begin();
309  for (; adj != (*m_trisAdjToPts)[a_pt1].end(); ++adj)
310  {
311  a_localPt1 = LocalIndex(*adj, a_pt1);
312  a_localPt2 = trIncrementIndex(a_localPt1);
313  if ((*m_tris)[(*adj * 3) + a_localPt2] == a_pt2)
314  {
315  a_tri = *adj;
316  return true;
317  }
318  }
319  a_tri = XM_NONE;
320  return false;
321 } // TrTinImpl::TriangleFromEdge
322 //------------------------------------------------------------------------------
330 //------------------------------------------------------------------------------
331 int TrTinImpl::TriangleAdjacentToEdge(int a_pt1, int a_pt2) const
332 {
333  int localIdx1, localIdx2;
334 
335  // For each triangle adjacent to a_pt1
336  VecInt::const_iterator adj = (*m_trisAdjToPts)[a_pt1].begin();
337  bool found = false;
338  for (; adj != (*m_trisAdjToPts)[a_pt1].end(); ++adj)
339  {
340  localIdx1 = LocalIndex(*adj, a_pt1);
341  localIdx2 = trDecrementIndex(localIdx1);
342  if ((*m_tris)[(*adj * 3) + localIdx2] == a_pt2)
343  {
344  found = true;
345  break;
346  }
347  }
348  return (found ? *adj : XM_NONE);
349 } // TrTinImpl::TriangleAdjacentToEdge
350 //------------------------------------------------------------------------------
357 //------------------------------------------------------------------------------
358 int TrTinImpl::LocalIndex(int a_tri, int a_pt) const
359 {
360  int t = a_tri * 3;
361  for (int i = 0; i < 3; ++i)
362  {
363  if ((*m_tris)[t + i] == a_pt)
364  return i;
365  }
366  return XM_NONE;
367 } // TrTinImpl::LocalIndex
368 //------------------------------------------------------------------------------
374 //------------------------------------------------------------------------------
375 bool TrTinImpl::VerticesAreAdjacent(int a_pt1, int a_pt2) const
376 {
377  // Look through the triangles adjacent to a_pt1
378  for (size_t i = 0; i < (*m_trisAdjToPts)[a_pt1].size(); ++i)
379  {
380  int trisIdx = (*m_trisAdjToPts)[a_pt1][i] * 3; // Index in m_tris
381  // See if a_pt2 is part of this triangle by checking all three points.
382  // vrVerticesAreAdjacent would call trIndex then trIncrementIndex and
383  // trDecrementIndex but I think this is simpler and maybe faster.
384  for (int j = 0; j < 3; ++j)
385  {
386  if ((*m_tris)[trisIdx + j] == a_pt2)
387  {
388  return true;
389  }
390  }
391  }
392  return false;
393 } // TrTinImpl::VerticesAreAdjacent
394 //------------------------------------------------------------------------------
415 //------------------------------------------------------------------------------
416 bool TrTinImpl::SwapEdge(int a_triA, int a_triB, bool a_checkAngle /*true*/)
417 {
418  XM_ENSURE_TRUE_NO_ASSERT(a_triA >= 0 && a_triB >= 0, false);
419 
420  int a1, a2, a3, b1, b2, b3;
421  int top, btm, lft, rgt;
422  Pt3d toppt, btmpt, lftpt, rgtpt;
423 
424  b3 = CommonEdgeIndex(a_triB, a_triA);
425  b2 = trDecrementIndex(b3);
426  b1 = trIncrementIndex(b3);
427  a3 = LocalIndex(a_triA, GlobalIndex(a_triB, b1));
428  a1 = trIncrementIndex(a3);
429  a2 = trIncrementIndex(a1);
430  top = GlobalIndex(a_triB, b2);
431  lft = GlobalIndex(a_triB, b3);
432  rgt = GlobalIndex(a_triB, b1);
433  btm = GlobalIndex(a_triA, a2);
434  toppt = (*m_pts)[top];
435  lftpt = (*m_pts)[lft];
436  rgtpt = (*m_pts)[rgt];
437  btmpt = (*m_pts)[btm];
438 
439  // make sure triangles are good
440  double area1 = trArea(toppt, lftpt, btmpt);
441  double area2 = trArea(btmpt, rgtpt, toppt);
442 
443  if (area1 > 0.0 && area2 > 0.0)
444  {
445  bool swap = true;
446  if (a_checkAngle)
447  {
448  double ang1 = gmAngleBetweenEdges(rgtpt, btmpt, toppt);
449  double ang2 = gmAngleBetweenEdges(btmpt, toppt, rgtpt);
450  double ang3 = gmAngleBetweenEdges(toppt, btmpt, lftpt);
451  double ang4 = gmAngleBetweenEdges(lftpt, toppt, btmpt);
452  const static double min_ang = 0.01 * (XM_PI / 180.0);
453  const static double max_ang = 179.99 * (XM_PI / 180.0);
454  if (ang1 < min_ang || ang1 > max_ang || ang2 < min_ang || ang2 > max_ang || ang3 < min_ang ||
455  ang3 > max_ang || ang4 < min_ang || ang4 > max_ang)
456  {
457  swap = false;
458  }
459  }
460  if (swap)
461  {
462  // update the adjacent tin ptrs
463  DeleteAdjacentTriangle(lft, a_triB);
464  DeleteAdjacentTriangle(rgt, a_triA);
465  InsertAdjacentTriangle(top, a_triA /*, a3*/);
466  InsertAdjacentTriangle(btm, a_triB /*, b3*/);
467 
468  // update the verts
469  (*m_tris)[(a_triA * 3) + a3] = top;
470  (*m_tris)[(a_triB * 3) + b3] = btm;
471 
472  // See if we created a bad triangle
473  if (!gmCounterClockwiseTri((*m_pts)[(*m_tris)[a_triA * 3]],
474  (*m_pts)[(*m_tris)[(a_triA * 3) + 1]],
475  (*m_pts)[(*m_tris)[(a_triA * 3) + 2]]) ||
476  !gmCounterClockwiseTri((*m_pts)[(*m_tris)[a_triB * 3]],
477  (*m_pts)[(*m_tris)[(a_triB * 3) + 1]],
478  (*m_pts)[(*m_tris)[(a_triB * 3) + 2]]))
479  {
480  std::stringstream msg;
481  msg << "Swapping triangles: " << a_triA << " and " << a_triB
482  << " created invalid triangles (ordered cw instead of ccw).";
483  XM_LOG(xmlog::error, msg.str());
484  }
485  return true;
486  }
487  }
488  return false;
489 } // TrTinImpl::SwapEdge
490 //------------------------------------------------------------------------------
513 //------------------------------------------------------------------------------
514 bool TrTinImpl::CheckAndSwap(int a_triA, int a_triB, bool a_propagate, const VecInt& a_flags)
515 {
516  XM_ENSURE_TRUE_NO_ASSERT(a_triA >= 0 && a_triB >= 0, false);
517 
518  bool change = false;
519  int tri1id2 = 0;
520  int tri2id0 = 0, tri2id1 = 0, tri2id2 = 0;
521 
522  if (a_triB != XM_NONE)
523  {
524  tri2id2 = CommonEdgeIndex(a_triB, a_triA);
525  tri2id1 = trDecrementIndex(tri2id2);
526  change = PointIsInCircumcircle(a_triA, a_triB, tri2id1);
527  }
528 
529  if (change)
530  {
531  tri2id0 = trIncrementIndex(tri2id2);
532  tri1id2 = LocalIndex(a_triA, GlobalIndex(a_triB, tri2id0));
533 
534  SwapEdge(a_triA, a_triB, false);
535  int adjTri = AdjacentTriangle(a_triA, tri1id2);
536  if (a_propagate || (!a_propagate && adjTri != XM_NONE && a_flags[adjTri]))
537  {
538  CheckAndSwap(a_triA, adjTri, a_propagate, a_flags);
539  }
540  adjTri = AdjacentTriangle(a_triA, tri2id0);
541  if (a_propagate || (!a_propagate && adjTri != XM_NONE && a_flags[adjTri]))
542  {
543  CheckAndSwap(a_triB, adjTri, a_propagate, a_flags);
544  }
545  }
546 
547  return false;
548 } // TrTinImpl::CheckAndSwap
549 //------------------------------------------------------------------------------
578 //------------------------------------------------------------------------------
579 bool TrTinImpl::PointIsInCircumcircle(int a_tri1, int a_tri2, int a_localPt)
580 {
581  int t = a_tri1 * 3;
582  return (gmPtInCircumcircle((*m_pts)[GlobalIndex(a_tri2, a_localPt)], &(*m_pts)[t]) == PT_IN);
583 } // TrTinImpl::PointIsInCircumcircle
584 //------------------------------------------------------------------------------
594 //------------------------------------------------------------------------------
595 int TrTinImpl::CommonEdgeIndex(int a_tri, int a_adjTri) const
596 {
597  bool found = false;
598  int edge = 0;
599  while (!found)
600  {
601  int adjtri = AdjacentTriangle(a_tri, edge);
602  if (adjtri == a_adjTri)
603  found = true;
604  else
605  edge = trIncrementIndex(edge);
606  if (edge == 0)
607  break;
608  }
609  if (!found)
610  edge = XM_NONE;
611  return edge;
612 } // TrTinImpl::CommonEdgeIndex
613 //------------------------------------------------------------------------------
629 //------------------------------------------------------------------------------
630 int TrTinImpl::AdjacentTriangle(int a_triIdx, int a_edgeIdx) const
631 {
632  int t = a_triIdx * 3;
633  int edgePt1 = (*m_tris)[t + a_edgeIdx];
634  int edgePt2 = (*m_tris)[t + trIncrementIndex(a_edgeIdx)];
635 
636  int adjTri;
637  int idx1, idx2;
638  if (TriangleFromEdge(edgePt2, edgePt1, adjTri, idx1, idx2))
639  {
640  return adjTri;
641  }
642  return XM_NONE;
643 } // TrTinImpl::AdjacentTriangle
644 //------------------------------------------------------------------------------
648 //------------------------------------------------------------------------------
649 xms::Pt3d TrTinImpl::TriangleCentroid(int a_tri) const
650 {
651  int t = a_tri * 3;
652  Pt3d centroid((*m_pts)[(*m_tris)[t]]);
653  centroid += (*m_pts)[(*m_tris)[t + 1]];
654  centroid += (*m_pts)[(*m_tris)[t + 2]];
655  return (centroid / (double)3);
656 } // TrTinImpl::TriangleCentroid
657 //------------------------------------------------------------------------------
661 //------------------------------------------------------------------------------
662 double TrTinImpl::TriangleArea(int a_tri) const
663 {
664  int t = a_tri * 3;
665  return trArea((*m_pts)[(*m_tris)[t]], (*m_pts)[(*m_tris)[t + 1]], (*m_pts)[(*m_tris)[t + 2]]);
666 
667 } // TrTinImpl::TriangleArea
668 #if 0 // FirstBoundaryPoint has been commented out because it wasn't used
669  // Also, what if you have holes? Consider using GetBoundaryPoints and
670  // GetBoundaryPolys. The code has been left here in case we reconsider.
671 //------------------------------------------------------------------------------
676 //------------------------------------------------------------------------------
677 int TrTinImpl::FirstBoundaryPoint () const
678 {
679  XM_ENSURE_TRUE_NO_ASSERT(!(*m_trisAdjToPts).empty(), XM_NONE);
680 
681  int nPoints = NumPoints();
682  int firstTri, tri, localIndex, prevtri(XM_NONE);
683  for (int p = 0; p < nPoints; ++p)
684  {
685  firstTri = tri = (*m_trisAdjToPts)[p][0];
686  do {
687  localIndex = LocalIndex(tri, p);
688  prevtri = tri;
689  tri = AdjacentTriangle(tri, localIndex);
690  } while (tri != firstTri && tri != XM_NONE);
691  if (tri == XM_NONE) {
692  return p;
693  }
694  }
695  return XM_NONE;
696 } // TrTinImpl::FirstBoundaryPoint
697 #endif
698 //------------------------------------------------------------------------------
706 //------------------------------------------------------------------------------
707 int TrTinImpl::NextBoundaryPoint(int a_point) const
708 {
709  XM_ENSURE_TRUE_NO_ASSERT(a_point >= 0 && a_point <= (int)(*m_pts).size(), XM_NONE);
710  XM_ENSURE_TRUE_NO_ASSERT(!(*m_trisAdjToPts)[a_point].empty(), XM_NONE);
711 
712  // Get a starting tri
713  int firstTri, tri, prevtri(XM_NONE), bpoint(XM_NONE);
714  int localIndex;
715  firstTri = tri = (*m_trisAdjToPts)[a_point][0];
716 
717  // use a "do" loop not a "while" loop here
718  do
719  {
720  localIndex = trDecrementIndex(LocalIndex(tri, a_point));
721  prevtri = tri;
722  tri = AdjacentTriangle(tri, localIndex);
723  } while (tri != firstTri && tri != XM_NONE);
724 
725  // if tri is null, there is a boundary vertex
726  if (tri == XM_NONE)
727  {
728  bpoint = GlobalIndex(prevtri, localIndex);
729  }
730  return bpoint;
731 
732 } // TrTinImpl::NextBoundaryPoint
733 //------------------------------------------------------------------------------
741 //------------------------------------------------------------------------------
742 int TrTinImpl::PreviousBoundaryPoint(int a_point) const
743 {
744  XM_ENSURE_TRUE_NO_ASSERT(a_point >= 0 && a_point <= (int)(*m_pts).size(), XM_NONE);
745  XM_ENSURE_TRUE_NO_ASSERT(!(*m_trisAdjToPts)[a_point].empty(), XM_NONE);
746 
747  // Get a starting tri
748  int firstTri, tri, prevtri(XM_NONE), bpoint(XM_NONE);
749  int localIndex;
750  firstTri = tri = (*m_trisAdjToPts)[a_point][0];
751 
752  // use a "do" loop not a "while" loop here
753  do
754  {
755  localIndex = LocalIndex(tri, a_point);
756  prevtri = tri;
757  tri = AdjacentTriangle(tri, localIndex);
758  } while (tri != firstTri && tri != XM_NONE);
759 
760  // if tri is null, there is a boundary vertex
761  if (tri == XM_NONE)
762  {
763  bpoint = GlobalIndex(prevtri, trIncrementIndex(localIndex));
764  }
765  return bpoint;
766 } // TrTinImpl::PreviousBoundaryPoint
767 //------------------------------------------------------------------------------
772 //------------------------------------------------------------------------------
773 void TrTinImpl::GetBoundaryPoints(VecInt& a_boundaryPoints) const
774 {
775  // Make sure adjacencies exist first
776  if (TrisAdjToPts().empty())
777  {
778  BuildTrisAdjToPtsConst();
779  }
780 
781  VecInt& tris = *m_tris;
782  SetInt setPoints;
783  size_t numTri = m_tris->size() / 3;
784  int t = 0;
785  for (size_t tri = 0; tri < numTri; ++tri, t += 3)
786  {
787  for (int i = 0; i < 3; ++i)
788  {
789  if (AdjacentTriangle((int)tri, i) == XM_NONE)
790  {
791  setPoints.insert(tris[t + i]);
792  setPoints.insert(tris[t + trIncrementIndex(i)]);
793  }
794  }
795  }
796 
797  a_boundaryPoints.clear();
798  std::copy(setPoints.begin(), setPoints.end(), std::back_inserter(a_boundaryPoints));
799 
800 } // TrTinImpl::GetBoundaryPoints
801 //------------------------------------------------------------------------------
806 //------------------------------------------------------------------------------
807 void TrTinImpl::GetBoundaryPolys(VecInt2d& a_polys) const
808 {
809  // Get all the points on any boundary
810  VecInt points;
811  GetBoundaryPoints(points);
812 
813  // Convert to a set
814  boost::unordered_set<int> pointSet(points.begin(), points.end());
815 
816  // Put points into polygons
817  a_polys.clear();
818  while (!pointSet.empty())
819  {
820  // Get the new first point
821  // using minimum element so result is consistent for different architectures
822  auto it = std::min_element(pointSet.begin(), pointSet.end());
823 
824  // Find adjacent points on the border until we return to the first point,
825  // removing the points from the set of boundary points
826  int first = *it;
827  a_polys.push_back(VecInt());
828  a_polys.back().push_back(first);
829  pointSet.erase(it);
830  int next = NextBoundaryPoint(first);
831  while (next != first)
832  {
833  a_polys.back().push_back(next);
834  it = pointSet.find(next);
835  if (it == pointSet.end())
836  {
837  XM_LOG(xmlog::warning,
838  "Unable to get boundary polygon from meshed points. Check the input polygon.");
839  a_polys.clear();
840  return;
841  }
842  pointSet.erase(it);
843  next = NextBoundaryPoint(next);
844  }
845  a_polys.back().push_back(a_polys.back().front()); // Repeat first point as the last point
846  }
847 } // TrTinImpl::GetBoundaryPolys
848 //------------------------------------------------------------------------------
853 //------------------------------------------------------------------------------
854 bool TrTinImpl::GetExtents(Pt3d& a_mn, Pt3d& a_mx) const
855 {
856  if (!(*m_pts).empty())
857  {
858  const VecPt3d& pts = (*m_pts);
859  a_mn = XM_DBL_HIGHEST;
860  a_mx = XM_DBL_LOWEST;
861  for (size_t i = 0; i < pts.size(); ++i)
862  {
863  gmAddToExtents(pts[i], a_mn, a_mx);
864  }
865  return true;
866  }
867  return false;
868 } // TrTinImpl::GetExtents
869 //------------------------------------------------------------------------------
872 //------------------------------------------------------------------------------
873 void TrTinImpl::ExportTinFile(std::ostream& a_os) const
874 {
875  a_os << "TIN\n";
876  a_os << "BEGT\n";
877 
878  // Points
879  VecPt3d& pts = (*m_pts);
880  a_os << "VERT " << pts.size() << "\n";
881  for (size_t i = 0; i < pts.size(); ++i)
882  {
883  a_os << STRstd(pts[i].x) << "\t" << STRstd(pts[i].y) << "\t" << STRstd(pts[i].z) << "\n";
884  }
885 
886  // Triangles
887  VecInt& tris = (*m_tris);
888  a_os << "TRI " << NumTriangles() << "\n";
889  for (size_t i = 0; i < tris.size(); i += 3)
890  {
891  a_os << (tris[i] + 1) << "\t" << (tris[i + 1] + 1) << "\t" << (tris[i + 2] + 1) << "\n";
892  }
893 
894  a_os << "ENDT\n";
895 } // TrTinImpl::ExportTinFile
896 //------------------------------------------------------------------------------
901 //------------------------------------------------------------------------------
902 void TrTinImpl::InsertAdjacentTriangle(int a_pt, int a_tri)
903 {
904  XM_ENSURE_TRUE_VOID(a_pt >= 0 && a_tri >= 0);
905 
906  (*m_trisAdjToPts)[a_pt].push_back(a_tri);
907 } // TrTinImpl::InsertAdjacentTriangle
908 //------------------------------------------------------------------------------
913 //------------------------------------------------------------------------------
914 void TrTinImpl::DeleteAdjacentTriangle(int a_pt, int a_tri)
915 {
916  VecInt::iterator adjTri = (*m_trisAdjToPts)[a_pt].begin();
917  for (; adjTri != (*m_trisAdjToPts)[a_pt].end(); ++adjTri)
918  {
919  if (*adjTri == a_tri)
920  {
921  (*m_trisAdjToPts)[a_pt].erase(adjTri);
922  break;
923  }
924  }
925 } // TrTinImpl::DeleteAdjacentTriangle
926 //------------------------------------------------------------------------------
931 //------------------------------------------------------------------------------
932 int TrTinImpl::GlobalIndex(int a_triIdx, int a_localPt) const
933 {
934  XM_ENSURE_TRUE((a_triIdx * 3) + a_localPt < static_cast<int>((*m_tris).size()), XM_NONE);
935  return (*m_tris)[(a_triIdx * 3) + a_localPt];
936 } // TrTinImpl::GlobalIndex
937 //------------------------------------------------------------------------------
946 //------------------------------------------------------------------------------
947 bool TrTinImpl::TriIndexFound(const int& a_triPt) const
948 {
949  int index = (int)(&a_triPt - &*(*m_tris).begin());
950  return m_toDelete.find(index) != m_toDelete.end();
951 } // TrTinImpl::TriIndexFound
952 //------------------------------------------------------------------------------
961 //------------------------------------------------------------------------------
962 bool TrTinImpl::PointIndexFound(const Pt3d& a_point) const
963 {
964  int index = (int)(&a_point - &*(*m_pts).begin());
965  return m_toDelete.find(index) != m_toDelete.end();
966 } // TrTinImpl::PointIndexFound
967 //------------------------------------------------------------------------------
976 //------------------------------------------------------------------------------
977 bool TrTinImpl::AdjacentIndexFound(const VecInt& a_adj) const
978 {
979  int index = (int)(&a_adj - &*(*m_trisAdjToPts).begin());
980  return m_toDelete.find(index) != m_toDelete.end();
981 } // TrTinImpl::AdjacentIndexFound
982 //------------------------------------------------------------------------------
986 //------------------------------------------------------------------------------
987 void TrTinImpl::DeleteTriangles(const SetInt& a_trisToDelete)
988 {
989  int oldNumTris = NumTriangles();
990 
991  // Add indices of triangles in m_tris to a hash table
992  for (SetInt::iterator it = a_trisToDelete.begin(); it != a_trisToDelete.end(); ++it)
993  {
994  XM_ENSURE_TRUE_VOID_NO_ASSERT((*it * 3) + 2 < static_cast<int>((*m_tris).size()));
995  m_toDelete.insert((*it * 3));
996  m_toDelete.insert((*it * 3) + 1);
997  m_toDelete.insert((*it * 3) + 2);
998  }
999 
1000  // Erase triangles from the m_tris vector using m_toDelete set.
1001  // This would be better as a lamda but I couldn't get it to work.
1002  (*m_tris).erase(std::remove_if((*m_tris).begin(), (*m_tris).end(),
1003  boost::bind(&TrTinImpl::TriIndexFound, this, _1)),
1004  (*m_tris).end());
1005  m_toDelete.clear();
1006 
1007  // Remove adjacent triangles from m_trisAdjToPts
1008  for (VecInt2d::iterator itPoint = (*m_trisAdjToPts).begin(); itPoint != (*m_trisAdjToPts).end();
1009  ++itPoint)
1010  {
1011  for (VecInt::iterator itTri = itPoint->begin(); itTri != itPoint->end();)
1012  {
1013  if (a_trisToDelete.find(*itTri) != a_trisToDelete.end())
1014  {
1015  itTri = itPoint->erase(itTri);
1016  }
1017  else
1018  {
1019  ++itTri;
1020  }
1021  }
1022  }
1023 
1024  // Renumber triangles in m_trisAdjToPts
1025  // Create a oldToNewIdxs
1026  VecInt oldToNewIdxs(oldNumTris); // Size of old, will have new idxs
1027  std::iota(oldToNewIdxs.begin(), oldToNewIdxs.end(), 0); // Init 0 to old size
1028  SetInt::iterator it = a_trisToDelete.begin();
1029  int offset = 0;
1030  for (int i = 0; i < oldNumTris; ++i)
1031  {
1032  if (it != a_trisToDelete.end() && i >= *it)
1033  {
1034  offset++;
1035  ++it;
1036  }
1037  else
1038  {
1039  oldToNewIdxs[i] -= offset;
1040  }
1041  }
1042  for (VecInt2d::iterator itPoint = (*m_trisAdjToPts).begin(); itPoint != (*m_trisAdjToPts).end();
1043  ++itPoint)
1044  {
1045  for (VecInt::iterator itAdj = itPoint->begin(); itAdj != itPoint->end(); ++itAdj)
1046  {
1047  *itAdj = oldToNewIdxs[*itAdj];
1048  }
1049  }
1050 
1051 } // TrTinImpl::DeleteTriangles
1052 //------------------------------------------------------------------------------
1056 //------------------------------------------------------------------------------
1057 void TrTinImpl::DeletePoints(const SetInt& a_points)
1058 {
1059  // Add a_points to a hash table which is used by the predicate
1060  m_toDelete.clear();
1061  m_toDelete.insert(a_points.begin(), a_points.end());
1062 
1063  // Erase points from the m_pts vector using m_toDelete set.
1064  // This would be better as a lamda but I couldn't get it to work.
1065  (*m_pts).erase(std::remove_if((*m_pts).begin(), (*m_pts).end(),
1066  boost::bind(&TrTinImpl::PointIndexFound, this, _1)),
1067  (*m_pts).end());
1068 
1069  // Create a set of all triangles adjacent to all points to be deleted
1070  SetInt trianglesToDelete;
1071  if (!(*m_trisAdjToPts).empty() && !(*m_tris).empty())
1072  {
1073  SetInt::const_iterator it = a_points.begin();
1074  for (; it != a_points.end(); ++it)
1075  {
1076  trianglesToDelete.insert((*m_trisAdjToPts)[*it].begin(), (*m_trisAdjToPts)[*it].end());
1077  }
1078  }
1079 
1080  if (!(*m_trisAdjToPts).empty())
1081  {
1082  // Erase points from the m_trisAdjToPts vector using m_toDelete set.
1083  // This would be better as a lamda but I couldn't get it to work.
1084  (*m_trisAdjToPts)
1085  .erase(std::remove_if((*m_trisAdjToPts).begin(), (*m_trisAdjToPts).end(),
1086  boost::bind(&TrTinImpl::AdjacentIndexFound, this, _1)),
1087  (*m_trisAdjToPts).end());
1088  }
1089  m_toDelete.clear();
1090 
1091  // Remove all triangles attached to the deleted points
1092  if (!(*m_trisAdjToPts).empty() && !(*m_tris).empty())
1093  {
1094  DeleteTriangles(trianglesToDelete);
1095  trRenumberOnDelete(a_points, (*m_tris));
1096  }
1097 
1098 } // TrTinImpl::DeletePoints
1099 //------------------------------------------------------------------------------
1102 //------------------------------------------------------------------------------
1103 bool TrTinImpl::OptimizeTriangulation()
1104 {
1105  bool modified = false;
1106  int nTri = NumTriangles();
1107  VecInt flags(nTri, false);
1108 
1109  bool meshaltered;
1110  int id;
1111  int adjtri;
1112 
1113  do
1114  {
1115  meshaltered = false;
1116  for (int tri = 0; tri < nTri; ++tri)
1117  {
1118  if (flags[tri])
1119  {
1120  id = 0;
1121  for (int i = 0; i <= 2; i++)
1122  {
1123  // get neighboring element
1124  adjtri = AdjacentTriangle(tri, id);
1125  if (adjtri != XM_NONE && flags[adjtri])
1126  {
1127  // swap if needed and propagate
1128  if (CheckAndSwap(tri, adjtri, false, flags))
1129  {
1130  meshaltered = true;
1131  }
1132  }
1133  id = trIncrementIndex(id);
1134  }
1135  }
1136  }
1137  if (meshaltered)
1138  modified = true;
1139  } while (meshaltered);
1140 
1141  return true;
1142 } // TrTinImpl::OptimizeTriangulation
1143 //------------------------------------------------------------------------------
1145 //------------------------------------------------------------------------------
1146 void TrTinImpl::Clear()
1147 {
1148  if (m_pts)
1149  m_pts->clear();
1150  if (m_tris)
1151  m_tris->clear();
1152  if (m_trisAdjToPts)
1153  m_trisAdjToPts->clear();
1154 } // TrTinImpl::Clear
1155 //------------------------------------------------------------------------------
1157 //------------------------------------------------------------------------------
1158 void TrTinImpl::BuildTrisAdjToPts()
1159 {
1160  BuildTrisAdjToPtsConst(); // code moved to const version
1161 } // TrTinImpl::BuildTrisAdjToPts
1162 //------------------------------------------------------------------------------
1165 //------------------------------------------------------------------------------
1166 std::string TrTinImpl::ToString() const
1167 {
1168  std::stringstream ss;
1169  {
1170  boost::archive::text_oarchive oa(ss);
1171  oa << *this;
1172  }
1173  return ss.str();
1174 } // TrTinImpl::ToString
1175 //------------------------------------------------------------------------------
1178 //------------------------------------------------------------------------------
1179 void TrTinImpl::FromString(const std::string& a_text)
1180 {
1181  std::stringstream ss(a_text);
1182  {
1183  boost::archive::text_iarchive ia(ss);
1184  ia >> *this;
1185  }
1186 } // TrTinImpl::FromString
1187 //------------------------------------------------------------------------------
1191 //------------------------------------------------------------------------------
1192 template <typename Archive>
1193 void TrTinImpl::serialize(Archive& archive, const unsigned int version)
1194 {
1195  (void)version; // Because Doxygen complained when commented out above.
1196  archive& boost::serialization::base_object<TrTin>(*this); // does nothing
1197 
1198  VecPt3d& p(*m_pts);
1199  VecInt& t(*m_tris);
1200  VecInt2d& t2(*m_trisAdjToPts);
1201 
1202  archive& p;
1203  archive& t;
1204  archive& t2;
1205 } // TrTinImpl::serialize
1206 //------------------------------------------------------------------------------
1209 //------------------------------------------------------------------------------
1210 void TrTinImpl::BuildTrisAdjToPtsConst() const
1211 {
1212  // You would think m_trisAdjToPts would need to be mutable, but it doesn't
1213  VecInt2d& trisAdjToPts = *m_trisAdjToPts;
1214  const VecInt& tris = *m_tris;
1215  trisAdjToPts.assign(m_pts->size(), VecInt());
1216  size_t numTri = tris.size() / 3;
1217  int t = 0;
1218  for (size_t tri = 0; tri < numTri; ++tri)
1219  {
1220  trisAdjToPts[tris[t++]].push_back((int)tri);
1221  trisAdjToPts[tris[t++]].push_back((int)tri);
1222  trisAdjToPts[tris[t++]].push_back((int)tri);
1223  }
1224  stShrinkCapacity(trisAdjToPts);
1225 } // TrTinImpl::BuildTrisAdjToPtsConst
1226 
1231 //------------------------------------------------------------------------------
1233 //------------------------------------------------------------------------------
1234 TrTin::TrTin()
1235 {
1236 }
1237 //------------------------------------------------------------------------------
1239 //------------------------------------------------------------------------------
1240 TrTin::~TrTin()
1241 {
1242 }
1243 //------------------------------------------------------------------------------
1246 //------------------------------------------------------------------------------
1247 BSHP<TrTin> TrTin::New()
1248 {
1249  return BDPC<TrTin>(BSHP<TrTinImpl>(new TrTinImpl()));
1250 } // TrTin::TrTin
1251 //------------------------------------------------------------------------------
1253 //------------------------------------------------------------------------------
1254 // template<typename Archive>
1255 // void TrTin::serialize(Archive& archive, const unsigned int version)
1256 //{
1257 // TrTinImpl *t = dynamic_cast<TrTinImp*>(this);
1258 // if (t)
1259 // {
1260 // t->serialize(archive, version);
1261 // }
1262 //} // TrTinImpl::serialize
1263 
1264 //----- Global functions -------------------------------------------------------
1265 
1266 //------------------------------------------------------------------------------
1275 //------------------------------------------------------------------------------
1276 void trRenumberOnDelete(const SetInt& a_deleting, VecInt& a_vec)
1277 {
1278  for (SetInt::reverse_iterator itDeleting = a_deleting.rbegin(); itDeleting != a_deleting.rend();
1279  ++itDeleting)
1280  {
1281  int pt = *itDeleting;
1282  for (VecInt::iterator itTriPt = a_vec.begin(); itTriPt != a_vec.end(); ++itTriPt)
1283  {
1284  if (*itTriPt >= pt)
1285  {
1286  --(*itTriPt);
1287  }
1288  }
1289  }
1290 } // trRenumberOnDelete
1291 
1292 } // namespace xms
1293 
1294 #if CXX_TEST
1295 // UNIT TESTS
1298 
1299 #include <xmsgeom/triangulate/TrTin.t.h>
1300 
1301 #include <xmscore/testing/TestTools.h>
1302 #include <xmscore/misc/carray.h>
1303 #include <xmsgeom/triangulate/TrTriangulatorPoints.h>
1304 
1305 //----- Namespace declaration --------------------------------------------------
1306 
1307 // namespace xms {
1308 using namespace xms;
1309 
1310 namespace
1311 {
1312 //------------------------------------------------------------------------------
1314 //------------------------------------------------------------------------------
1315 static VecPt3d iArrayToVecPt3d(double* a_array, int a_size)
1316 {
1317  VecPt3d v(a_size / 2);
1318  for (int i = 0; i < a_size; i += 2)
1319  {
1320  v[i / 2].x = a_array[i];
1321  v[i / 2].y = a_array[i + 1];
1322  }
1323  return v;
1324 } // iArrayToVecPt3d
1325 
1326 } // namespace unnamed
1327 
1328 //------------------------------------------------------------------------------
1350 //------------------------------------------------------------------------------
1351 BSHP<TrTin> trBuildTestTin()
1352 {
1353  BSHP<TrTin> tin = TrTin::New();
1354 
1355  tin->Points() = {{5, 0, 0}, {10, 0, 0}, {0, 5, 0}, {5, 5, 0}, {10, 5, 0},
1356  {15, 5, 0}, {0, 10, 0}, {5, 10, 0}, {10, 10, 0}, {5, 15, 0}};
1357  tin->Triangles() = {0, 3, 2, 0, 1, 3, 1, 4, 3, 1, 5, 4, 2, 3, 6,
1358  3, 7, 6, 4, 8, 7, 4, 5, 8, 6, 7, 9, 7, 8, 9};
1359  tin->BuildTrisAdjToPts();
1360  return tin;
1361 } // trBuildTestTin
1362 //------------------------------------------------------------------------------
1386 //------------------------------------------------------------------------------
1387 BSHP<TrTin> trBuildTestTin2()
1388 {
1389  BSHP<TrTin> tin = TrTin::New();
1390 
1391  tin->Points() = {{0, 0, 0}, {5, 0, 0}, {10, 0, 0}, {2.5, 2.5, 0},
1392  {0, 5, 0}, {5, 5, 0}, {0, 10, 0}};
1393  int tris[] = {0, 1, 3, 1, 2, 5, 0, 3, 4, 1, 5, 3, 4, 3, 5, 4, 5, 6};
1394  tin->Triangles().assign(&tris[0], &tris[XM_COUNTOF(tris)]);
1395  tin->BuildTrisAdjToPts();
1396  return tin;
1397 } // trBuildTestTin2
1398 //------------------------------------------------------------------------------
1420 //------------------------------------------------------------------------------
1421 BSHP<TrTin> trBuildTestTin6()
1422 {
1423  BSHP<TrTin> tin = TrTin::New();
1424  const double kYMax = 40;
1425  const double kXMax = 80;
1426  for (int y = 0; y <= kYMax; y += 10)
1427  {
1428  for (int x = 0; x <= kXMax; x += 10)
1429  {
1430  tin->Points().push_back(Pt3d(x, y, 0.0));
1431  }
1432  }
1433 
1434  TrTriangulatorPoints triangulator(tin->Points(), tin->Triangles(), &tin->TrisAdjToPts());
1435  triangulator.Triangulate();
1436  return tin;
1437 } // trBuildTestTin6
1438 //------------------------------------------------------------------------------
1442 // 10- 17-----18------19------20------21
1443 // | |\ 8 /|\ 11 /|\ 22 / \ 26 /|
1444 // | | \ / | \ / | \ / \ //|
1445 // | | \ / | \ /30|23\ / 27 \ / /|
1446 // 5- |6 13 12|9 14 | 15------16 /|
1447 // | | / \ | /|\ | / \ 25 /|28/|
1448 // | | / \ | / | \ | / \ / | / |
1449 // | |/ 7 \|/ | \|/ 24 \ /29| / |
1450 // 0- 9------10 10|3 11------12 | / |
1451 // | |\ 13 / \ | / \ 15 / \ |/ |
1452 // | | \ / \ | / \ / \ |/ |
1453 // | | \ / 5 \|/ 16 \ / 21 \|/ |
1454 // -5- | 0 5-------6-------7-------8 18|
1455 // | | / \ 4 / \ 14 / \ 19 / \ |
1456 // | | / \ / \ / \ / \ |
1457 // | |/ 1 \ / 2 \ / 20 \ / 17 \|
1458 // -10- 0-------1-------2-------3-------4
1459 //
1460 // |-------|-------|-------|-------|
1461 // 0 10 20 30 40
1464 //------------------------------------------------------------------------------
1465 BSHP<TrTin> trBuildTestTin7()
1466 {
1467  double meshPtsA[] = {0, -10, 10, -10, 20, -10, 30, -10, 40, -10, 5, -5, 15, -5, 25,
1468  -5, 35, -5, 0, 0, 10, 0, 20, 0, 30, 0, 5, 5, 15, 5,
1469  25, 5, 35, 5, 0, 10, 10, 10, 20, 10, 30, 10, 40, 10};
1470  BSHP<TrTin> tin = TrTin::New();
1471  tin->Points() = iArrayToVecPt3d(meshPtsA, XM_COUNTOF(meshPtsA));
1472  TrTriangulatorPoints triangulator(tin->Points(), tin->Triangles(), &tin->TrisAdjToPts());
1473  triangulator.Triangulate();
1474  return tin;
1475 } // trBuildTestTin7
1476 //------------------------------------------------------------------------------
1498 //------------------------------------------------------------------------------
1499 BSHP<TrTin> trBuildTestTin8()
1500 {
1501  BSHP<TrTin> tin = TrTin::New();
1502 
1503  tin->Points() = {{5, 0, 0}, {10, 0, 0}, {0, 5, 0}, {5, 5, 0}, {10, 5, 0}, {15, 5, 0},
1504  {0, 10, 0}, {5, 10, 0}, {10, 10, 0}, {5, 15, 0}, {10, 15, 0}, {15, 15, 0}};
1505  tin->Triangles() = {0, 3, 2, 0, 1, 3, 1, 4, 3, 1, 5, 4, 2, 3, 6, 3, 7, 6,
1506  4, 8, 7, 4, 5, 8, 6, 7, 9, 7, 8, 9, 8, 10, 9, 8, 11, 10};
1507  tin->BuildTrisAdjToPts();
1508  return tin;
1509 } // trBuildTestTin8
1510 
1515 //------------------------------------------------------------------------------
1518 
1519 // 10- 3-----------4
1520 // | /0\2 1/2\
1521 // | / \ 2 / \
1522 // | / \ / \
1523 // | / 0 \ / 1 \
1524 // | /1 2\0/0 1\
1525 // 0- 0-----------1-----------2
1526 //
1527 // |-----|-----|-----|-----|
1528 // 0 5 10 15 20
1529 //
1530 // m_tris = 3,0,1, 1,2,4, 1,4,3
1531 // m_trisAdjToPts = [0][0,1,2][1][0,2][1,2]
1532 
1534 //------------------------------------------------------------------------------
1535 void TrTinUnitTests::test1()
1536 {
1537  // Create memory
1538  BSHP<VecPt3d> pts(new VecPt3d());
1539  BSHP<VecInt> tris(new VecInt());
1540  BSHP<VecInt2d> trisAdjToPts(new VecInt2d());
1541 
1542  // Set up to our example tin
1543  *pts = {{0, 0, 0}, {10, 0, 0}, {20, 0, 0}, {5, 10, 0}, {15, 10, 0}};
1544  *tris = {3, 0, 1, 1, 2, 4, 1, 4, 3};
1545  *trisAdjToPts = {{0}, {0, 1, 2}, {1}, {0, 2}, {1, 2}};
1546 
1547  BSHP<TrTin> tin = TrTin::New();
1548  tin->SetGeometry(pts, tris, trisAdjToPts);
1549 
1550  // TriangleFromEdge
1551 
1552  int tri;
1553  int idx1, idx2;
1554  bool rv;
1555  rv = tin->TriangleFromEdge(1, 3, tri, idx1, idx2);
1556  TS_ASSERT_EQUALS(rv, true);
1557  TS_ASSERT_EQUALS(tri, 0);
1558  TS_ASSERT_EQUALS(idx1, 2);
1559  TS_ASSERT_EQUALS(idx2, 0);
1560  rv = tin->TriangleFromEdge(3, 1, tri, idx1, idx2);
1561  TS_ASSERT_EQUALS(rv, true);
1562  TS_ASSERT_EQUALS(tri, 2);
1563  TS_ASSERT_EQUALS(idx1, 2);
1564  TS_ASSERT_EQUALS(idx2, 0);
1565  rv = tin->TriangleFromEdge(1, 0, tri, idx1, idx2);
1566  TS_ASSERT_EQUALS(rv, false);
1567 
1568  // TriangleAdjacentToEdge
1569 
1570  tri = tin->TriangleAdjacentToEdge(1, 3);
1571  TS_ASSERT_EQUALS(tri, 2);
1572  tri = tin->TriangleAdjacentToEdge(3, 1);
1573  TS_ASSERT_EQUALS(tri, 0);
1574  tri = tin->TriangleAdjacentToEdge(1, 0);
1575  TS_ASSERT_EQUALS(tri, 0);
1576 
1577  // LocalIndex
1578 
1579  TS_ASSERT_EQUALS(tin->LocalIndex(0, 0), 1);
1580  TS_ASSERT_EQUALS(tin->LocalIndex(0, 1), 2);
1581  TS_ASSERT_EQUALS(tin->LocalIndex(0, 3), 0);
1582  TS_ASSERT_EQUALS(tin->LocalIndex(0, 4), XM_NONE);
1583 
1584  // GlobalIndex
1585 
1586  TS_ASSERT_EQUALS(tin->GlobalIndex(0, 0), 3);
1587  TS_ASSERT_EQUALS(tin->GlobalIndex(0, 1), 0);
1588  TS_ASSERT_EQUALS(tin->GlobalIndex(0, 2), 1);
1589  TS_ASSERT_EQUALS(tin->GlobalIndex(1, 0), 1);
1590  TS_ASSERT_EQUALS(tin->GlobalIndex(1, 1), 2);
1591  TS_ASSERT_EQUALS(tin->GlobalIndex(1, 2), 4);
1592  TS_ASSERT_EQUALS(tin->GlobalIndex(2, 0), 1);
1593  TS_ASSERT_EQUALS(tin->GlobalIndex(2, 1), 4);
1594  TS_ASSERT_EQUALS(tin->GlobalIndex(2, 2), 3);
1595  bool asserting = xmAsserting();
1596  xmAsserting() = false;
1597  TS_ASSERT_EQUALS(tin->GlobalIndex(3, 2), XM_NONE);
1598  TS_ASSERT_EQUALS(tin->GlobalIndex(2, 3), XM_NONE);
1599  xmAsserting() = asserting;
1600 
1601  // VerticesAreAdjacent
1602 
1603  TS_ASSERT_EQUALS(tin->VerticesAreAdjacent(0, 1), true);
1604  TS_ASSERT_EQUALS(tin->VerticesAreAdjacent(1, 0), true);
1605  TS_ASSERT_EQUALS(tin->VerticesAreAdjacent(0, 2), false);
1606 
1607  // CommonEdgeIndex
1608 
1609  TS_ASSERT_EQUALS(tin->CommonEdgeIndex(0, 2), 2);
1610  TS_ASSERT_EQUALS(tin->CommonEdgeIndex(2, 0), 2);
1611  TS_ASSERT_EQUALS(tin->CommonEdgeIndex(1, 2), 2);
1612  TS_ASSERT_EQUALS(tin->CommonEdgeIndex(2, 1), 0);
1613  TS_ASSERT_EQUALS(tin->CommonEdgeIndex(0, 1), XM_NONE);
1614 
1615  // AdjacentTriangle
1616 
1617  TS_ASSERT_EQUALS(tin->AdjacentTriangle(0, 0), XM_NONE);
1618  TS_ASSERT_EQUALS(tin->AdjacentTriangle(0, 1), XM_NONE);
1619  TS_ASSERT_EQUALS(tin->AdjacentTriangle(0, 2), 2);
1620  TS_ASSERT_EQUALS(tin->AdjacentTriangle(1, 0), XM_NONE);
1621  TS_ASSERT_EQUALS(tin->AdjacentTriangle(1, 1), XM_NONE);
1622  TS_ASSERT_EQUALS(tin->AdjacentTriangle(1, 2), 2);
1623  TS_ASSERT_EQUALS(tin->AdjacentTriangle(2, 0), 1);
1624  TS_ASSERT_EQUALS(tin->AdjacentTriangle(2, 1), XM_NONE);
1625  TS_ASSERT_EQUALS(tin->AdjacentTriangle(2, 2), 0);
1626 
1627  // TriangleCentroid
1628 
1629  const double kDelta = 1e-5;
1630  TS_ASSERT_DELTA_PT3D(tin->TriangleCentroid(0), Pt3d(5, 3.333333333, 0), kDelta);
1631  TS_ASSERT_DELTA_PT3D(tin->TriangleCentroid(1), Pt3d(15, 3.333333333, 0), kDelta);
1632  TS_ASSERT_DELTA_PT3D(tin->TriangleCentroid(2), Pt3d(10, 6.66666667, 0), kDelta);
1633 
1634  // TriangleArea
1635 
1636  TS_ASSERT_DELTA(tin->TriangleArea(0), 50.0, kDelta);
1637  TS_ASSERT_DELTA(tin->TriangleArea(1), 50.0, kDelta);
1638  TS_ASSERT_DELTA(tin->TriangleArea(2), 50.0, kDelta);
1639 
1640  // NextBoundaryPoint
1641 
1642  TS_ASSERT_EQUALS(tin->NextBoundaryPoint(0), 3);
1643  TS_ASSERT_EQUALS(tin->NextBoundaryPoint(3), 4);
1644  TS_ASSERT_EQUALS(tin->NextBoundaryPoint(4), 2);
1645  TS_ASSERT_EQUALS(tin->NextBoundaryPoint(2), 1);
1646  TS_ASSERT_EQUALS(tin->NextBoundaryPoint(1), 0);
1647 
1648  // PreviousBoundaryPoint
1649 
1650  TS_ASSERT_EQUALS(tin->PreviousBoundaryPoint(0), 1);
1651  TS_ASSERT_EQUALS(tin->PreviousBoundaryPoint(1), 2);
1652  TS_ASSERT_EQUALS(tin->PreviousBoundaryPoint(2), 4);
1653  TS_ASSERT_EQUALS(tin->PreviousBoundaryPoint(4), 3);
1654  TS_ASSERT_EQUALS(tin->PreviousBoundaryPoint(3), 0);
1655 
1656  // GetBoundaryPoints is tested elsewhere
1657  // GetBoundaryPolys is tested elsewhere
1658 
1659  // GetExtents
1660 
1661  Pt3d mn, mx;
1662  TS_ASSERT_EQUALS(tin->GetExtents(mn, mx), true);
1663  TS_ASSERT_DELTA_PT3D(mn, Pt3d(0, 0, 0), kDelta);
1664  TS_ASSERT_DELTA_PT3D(mx, Pt3d(20, 10, 0), kDelta);
1665 
1666  // Below here we've modified the tin -----------------------------------------
1667 
1668  // SwapEdge
1669 
1670  rv = tin->SwapEdge(0, 2);
1671  TS_ASSERT_EQUALS(rv, true);
1672  TS_ASSERT_EQUALS(tin->Triangles()[0], 3);
1673  TS_ASSERT_EQUALS(tin->Triangles()[1], 0);
1674  TS_ASSERT_EQUALS(tin->Triangles()[2], 4);
1675  TS_ASSERT_EQUALS(tin->Triangles()[3], 1);
1676  TS_ASSERT_EQUALS(tin->Triangles()[4], 2);
1677  TS_ASSERT_EQUALS(tin->Triangles()[5], 4);
1678  TS_ASSERT_EQUALS(tin->Triangles()[6], 1);
1679  TS_ASSERT_EQUALS(tin->Triangles()[7], 4);
1680  TS_ASSERT_EQUALS(tin->Triangles()[8], 0);
1681  const VecInt2d& trisAdjToPtsRef = tin->TrisAdjToPts();
1682  TS_ASSERT_EQUALS((VecInt{0, 2}), trisAdjToPtsRef[0]);
1683  TS_ASSERT_EQUALS((VecInt{1, 2}), trisAdjToPtsRef[1]);
1684  TS_ASSERT_EQUALS((VecInt{1}), trisAdjToPtsRef[2]);
1685  TS_ASSERT_EQUALS((VecInt{0}), trisAdjToPtsRef[3]);
1686  TS_ASSERT_EQUALS((VecInt{1, 2, 0}), trisAdjToPtsRef[4]);
1687 
1688  // DeleteTriangles is tested elsewhere
1689  // DeletePoints is tested elsewhere
1690  // OptimizeTriangulation is tested elsewhere
1691  // Clear is tested below
1692 
1693  // BuildTrisAdjToPts
1694 
1695  tin->TrisAdjToPts().clear();
1696  tin->BuildTrisAdjToPts();
1697  TS_ASSERT_EQUALS(*trisAdjToPts, tin->TrisAdjToPts());
1698 
1699  // Clear
1700 
1701  tin->Clear();
1702  TS_ASSERT_EQUALS(tin->Points().empty(), true);
1703  TS_ASSERT_EQUALS(tin->Triangles().empty(), true);
1704  TS_ASSERT_EQUALS(tin->TrisAdjToPts().empty(), true);
1705 
1706 } // TrTinUnitTests::test1
1707 //------------------------------------------------------------------------------
1710 // Before
1711 //
1712 // 20- 6------7------8
1713 // | |\ |\ |
1714 // | |\\ 3 |\\ 7 |
1715 // | |\ \ |\ \ |
1716 // | | \ \ | \ \ |
1717 // | | \ \ | \ \ |
1718 // | | \ \| \ \|
1719 // 10- 3 1 \2 4 5 \6 5
1720 // | |\ \ |\ \ |
1721 // | | \ \ | \ \ |
1722 // | | \ \ | \ \ |
1723 // | | \ \| \ \|
1724 // | | 0 \\| 4 \\|
1725 // | | \| \|0
1726 // 0 - 0------1------2
1727 //
1728 // |------|------|
1729 // 0 10 20
1730 
1731 // After
1732 // 20- 6------7------8
1733 // | |\ |\ |
1734 // | | \ 3 | \ 7 |
1735 // | | \ | \ |
1736 // | | \ | \ |
1737 // | | 2 \ | 6 \ |
1738 // | | \| \|
1739 // 10- 3------4------5
1740 // | |\ |\ |
1741 // | | \ 1 | \ 5 |
1742 // | | \ | \ |
1743 // | | \ | \ |
1744 // | | 0 \ | 4 \ |
1745 // | | \| \|
1746 // 0 - 0------1------2
1747 //
1748 // |------|------|
1749 // 0 10 20
1751 //------------------------------------------------------------------------------
1752 void TrTinUnitTests::testOptimizeTriangulation()
1753 {
1754  // Create memory
1755  BSHP<VecPt3d> pts(new VecPt3d());
1756  BSHP<VecInt> tris(new VecInt());
1757  BSHP<VecInt2d> trisAdjToPts(new VecInt2d());
1758 
1759  // Set up to our example tin
1760  *pts = {{0, 0, 0}, {10, 0, 0}, {20, 0, 0}, {0, 10, 0}, {10, 10, 0},
1761  {20, 10, 0}, {0, 20, 0}, {10, 20, 0}, {20, 20, 0}};
1762  *tris = {0, 1, 3, 1, 6, 3, 1, 4, 6, 4, 7, 6, 1, 2, 4, 2, 7, 4, 2, 5, 7, 5, 8, 7};
1763  *trisAdjToPts = {{0}, {0, 1, 2, 4}, {4, 5, 6}, {0, 1}, {2, 4, 5, 3},
1764  {6, 7}, {1, 2, 3}, {3, 5, 6, 7}, {7}};
1765 
1766  BSHP<TrTin> tin = TrTin::New();
1767  tin->SetGeometry(pts, tris, trisAdjToPts);
1768 
1769  // Test GetBoundaryPoints
1770  VecInt boundaryPoints;
1771  tin->GetBoundaryPoints(boundaryPoints);
1772  TS_ASSERT_EQUALS((VecInt{0, 1, 2, 3, 5, 6, 7, 8}), boundaryPoints);
1773 
1774  // Optimize
1775  TS_ASSERT(tin->OptimizeTriangulation());
1776  VecInt trisAfter = {0, 1, 3, 1, 6, 3, 1, 4, 6, 4, 7, 6, 1, 2, 4, 2, 7, 4, 2, 5, 7, 5, 8, 7};
1777  TS_ASSERT_EQUALS_VEC(trisAfter, tin->Triangles());
1778 
1779  // Test GetBoundaryPoints
1780  tin->GetBoundaryPoints(boundaryPoints);
1781  TS_ASSERT_EQUALS((VecInt{0, 1, 2, 3, 5, 6, 7, 8}), boundaryPoints);
1782 
1783 } // TrTinUnitTests::testOptimizeTriangulation
1784 //------------------------------------------------------------------------------
1787 // 20- 5-----------6-----------7 20- 5-----------6-----------7
1788 // | |\ / \ /| | |\ /|\ /|
1789 // | | \ 1 / \ 6 / | | | \ 1 / | \ 6 / |
1790 // | | \ / \ / | | | \ / | \ / |
1791 // | | \ / 7 \ / | | | \ / | \ / |
1792 // | | \ / \ / | | | \ / | \ / |
1793 // 10- | 2 3-----------4 4 | 10- | 2 3 3 | 7 4 4 |
1794 // | | / \ / \ | | | / \ | / \ |
1795 // | | / \ 3 / \ | | | / \ | / \ |
1796 // | | / \ / \ | | | / \ | / \ |
1797 // | | / 0 \ / 5 \ | | | / 0 \ | / 5 \ |
1798 // | |/ \ / \| | |/ \|/ \|
1799 // 0- 0-----------1-----------2 0- 0-----------1-----------2
1800 //
1801 // |-----|-----|-----|-----| |-----|-----|-----|-----|
1802 // 0 5 10 15 20 0 5 10 15 20
1804 //------------------------------------------------------------------------------
1805 void TrTinUnitTests::testSwap()
1806 {
1807  // Create tin and get some convenience variables
1808  BSHP<TrTin> tin = TrTin::New();
1809  VecInt& tris = tin->Triangles();
1810  VecInt2d& trisAdjToPts = tin->TrisAdjToPts();
1811 
1812  // Set up to our example tin points
1813  tin->Points() = {{0, 0, 0}, {10, 0, 0}, {20, 0, 0}, {5, 10, 0},
1814  {15, 10, 0}, {0, 20, 0}, {10, 20, 0}, {20, 20, 0}};
1815 
1816  // Triangulate the points
1817  TrTriangulatorPoints client(tin->Points(), tin->Triangles(), &trisAdjToPts);
1818  client.Triangulate();
1819 
1820  // See that things are as expected before the swap
1821  int trisB[] = {0, 1, 3, 5, 3, 6, 3, 5, 0, 1, 4, 3, 4, 2, 7, 2, 4, 1, 7, 6, 4, 4, 6, 3};
1822  VecInt trisBefore(&trisB[0], &trisB[24]);
1823  TS_ASSERT_EQUALS(trisBefore, tris);
1824 
1825  VecInt2d trisAdjToPtsBefore = {{0, 2}, {0, 3, 5}, {4, 5}, {0, 1, 2, 3, 7},
1826  {3, 4, 5, 6, 7}, {1, 2}, {1, 6, 7}, {4, 6}};
1827 
1828  TS_ASSERT_EQUALS(trisAdjToPtsBefore, trisAdjToPts);
1829 
1830  // Swap
1831  bool rv = tin->SwapEdge(3, 7);
1832  TS_ASSERT_EQUALS(rv, true);
1833 
1834  // See that things are as expected after the swap
1835  int trisA[] = {0, 1, 3, 5, 3, 6, 3, 5, 0, 1, 6, 3, 4, 2, 7, 2, 4, 1, 7, 6, 4, 4, 6, 1};
1836  VecInt trisAfter(&trisA[0], &trisA[24]);
1837  TS_ASSERT_EQUALS(trisAfter, tris);
1838 
1839  VecInt2d trisAdjToPtsAfter = {{0, 2}, {0, 3, 5, 7}, {4, 5}, {0, 1, 2, 3},
1840  {4, 5, 6, 7}, {1, 2}, {1, 6, 7, 3}, {4, 6}};
1841  TS_ASSERT_EQUALS(trisAdjToPtsAfter, trisAdjToPts);
1842 
1843  // Test GetBoundaryPoints
1844  VecInt boundaryPoints;
1845  tin->GetBoundaryPoints(boundaryPoints);
1846  TS_ASSERT_EQUALS((VecInt{0, 1, 2, 5, 6, 7}), boundaryPoints);
1847 
1848 } // TrTinUnitTests::testSwap
1849 #if 0 // FirstBoundaryPoint has been commented out because it wasn't used
1850 //------------------------------------------------------------------------------
1852 //------------------------------------------------------------------------------
1853 void TrTinTests::testFirstBoundaryPoint ()
1854 {
1855 
1856 
1857  // Example 1
1858  {
1859  BSHP<TrTin> tin = trBuildTestTin();
1860  TS_ASSERT_EQUALS(tin->FirstBoundaryPoint(), 0);
1861  }
1862 
1863  // Example 2
1864 // 20- 5-----------6-----------7
1865 // | |\ / \ /|
1866 // | | \ 1 / \ 6 / |
1867 // | | \ / \ / |
1868 // | | \ / 7 \ / |
1869 // | | \ / \ / |
1870 // 10- | 2 0-----------1 4 |
1871 // | | / \ / \ |
1872 // | | / \ 3 / \ |
1873 // | | / \ / \ |
1874 // | | / 0 \ / 5 \ |
1875 // | |/ \ / \|
1876 // 0- 2-----------3-----------4
1877 //
1878 // |-----|-----|-----|-----|
1879 // 0 5 10 15 20
1880 
1881  {
1882  BSHP<TrTin> tin = TrTin::New();
1883  tin->Points() = {{5,10,0},{15,10,0},{0,0,0},{10,0,0},
1884  {20,0,0},{0,20,0},{10,20,0},{20,20,0}};
1885  TrTriangulatorPoints client(tin->Points(), tin->Triangles(),
1886  &tin->TrisAdjToPts());
1887  client.Triangulate();
1888  TS_ASSERT_EQUALS(tin->FirstBoundaryPoint(), 2);
1889  }
1890 
1891 } // TrTinTests::testFirstBoundaryPoint
1892 #endif
1893 //------------------------------------------------------------------------------
1896 
1897 // 40 34-35--36--37--38--39--40--41--42
1898 // |\15|\23|\19|\44|41/|42/|\51|\49|
1899 // |16\|17\|20\|21\|/37|/40|43\|50\|
1900 // 30 25-26--27--28--29--30--31--32--33
1901 // |\13| \18|\52|38/|39/ \48|\47|
1902 // |14\| \|22\|/29|/ \|45\|
1903 // 20 18-19 20--21--22 23--24
1904 // |\ 3| /|\24|\26|\ |46/|
1905 // |1 \| / 9|12\|27\|28\ |/36|
1906 // 10 9--10--11--12--13--14--15--16--17
1907 // |2 /|\11|7 /|8 /|\31|\30|\32|35/|
1908 // |/ 0|4 \|/ 5|/ 6|10\|25\|33\|/34|
1909 // 0 0---1---2---3---4---5---6---7---8
1910 // 0 10 20 30 40 50 60 70 80
1911 
1913 //------------------------------------------------------------------------------
1914 void TrTinUnitTests::testBoundaries()
1915 {
1916  BSHP<TrTin> tin = trBuildTestTin6();
1917  SetInt toDelete = {20, 24};
1918  tin->DeletePoints(toDelete);
1919  VecInt2d boundaries;
1920 
1921  // GetBoundaryPoints
1922 
1923  VecInt pts;
1924  tin->GetBoundaryPoints(pts);
1925  int ptsA[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 15, 16, 17, 18, 19, 20,
1926  22, 23, 24, 25, 26, 27, 31, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42};
1927  VecInt expectedPts(&ptsA[0], &ptsA[XM_COUNTOF(ptsA)]);
1928  TS_ASSERT_EQUALS(expectedPts, pts);
1929 
1930  // GetBoundaryPolys
1931 
1932  tin->GetBoundaryPolys(boundaries);
1933 
1934  VecInt2d expected = {
1935  {0, 9, 18, 25, 34, 35, 36, 37, 38, 39, 40, 41, 42, 33, 24, 17, 8, 7, 6, 5, 4, 3, 2, 1, 0},
1936  {10, 11, 20, 27, 26, 19, 10},
1937  {15, 16, 23, 31, 22, 15}};
1938  TS_ASSERT_EQUALS_VEC2D(expected, boundaries);
1939 } // TrTinUnitTests::testBoundaries
1940 //------------------------------------------------------------------------------
1942 //------------------------------------------------------------------------------
1943 void TrTinUnitTests::testDeleteTriangles()
1944 {
1945  BSHP<TrTin> tin = trBuildTestTin6();
1946  TS_ASSERT_EQUALS(tin->NumTriangles(), 64);
1947  TS_ASSERT_EQUALS(tin->NumPoints(), 45);
1948 
1949  const VecInt2d& trisAdjToPts = tin->TrisAdjToPts();
1950 
1951  // Verify adjacency
1952  TS_ASSERT_EQUALS((VecInt{7, 19, 20, 21, 23, 29}), trisAdjToPts[20]);
1953  TS_ASSERT_EQUALS((VecInt{0, 1, 2, 3, 4, 7, 12, 29}), trisAdjToPts[10]);
1954  TS_ASSERT_EQUALS((VecInt{7, 8, 10, 12, 21}), trisAdjToPts[11]);
1955  TS_ASSERT_EQUALS((VecInt{10, 13, 20, 21, 22, 27, 30}), trisAdjToPts[21]);
1956  TS_ASSERT_EQUALS((VecInt{18, 20, 22, 23, 25, 28}), trisAdjToPts[29]);
1957  TS_ASSERT_EQUALS((VecInt{14, 16, 17, 18, 19, 23}), trisAdjToPts[28]);
1958  TS_ASSERT_EQUALS((VecInt{3, 14, 15, 19, 29}), trisAdjToPts[19]);
1959 
1960  // Delete the triangles around point 20
1961  SetInt toDelete = {7, 19, 20, 21, 23, 29};
1962  tin->DeleteTriangles(toDelete);
1963 
1964  TS_ASSERT_EQUALS(tin->NumTriangles(), 58); // 64 - 6
1965  TS_ASSERT_EQUALS(tin->NumPoints(), 45);
1966 
1967  // Make sure we renumbered the adjacency array properly
1968  int mx = -1;
1969  for (size_t i = 0; i < trisAdjToPts.size(); ++i)
1970  {
1971  for (size_t j = 0; j < trisAdjToPts[i].size(); ++j)
1972  {
1973  if (trisAdjToPts[i][j] > mx)
1974  mx = trisAdjToPts[i][j];
1975  }
1976  }
1977  TS_ASSERT_EQUALS(mx, 57); // 58 - 1
1978 
1993  // Verify adjacency
1994  TS_ASSERT(tin->TrisAdjToPts()[20].empty());
1995  TS_ASSERT_EQUALS((VecInt{0, 1, 2, 3, 4, 11}), trisAdjToPts[10]);
1996  TS_ASSERT_EQUALS((VecInt{7, 9, 11}), trisAdjToPts[11]);
1997  TS_ASSERT_EQUALS((VecInt{9, 12, 18, 22, 24}), trisAdjToPts[21]);
1998  TS_ASSERT_EQUALS((VecInt{17, 18, 20, 23}), trisAdjToPts[29]);
1999  TS_ASSERT_EQUALS((VecInt{13, 15, 16, 17}), trisAdjToPts[28]);
2000  TS_ASSERT_EQUALS((VecInt{3, 13, 14}), trisAdjToPts[19]);
2001 } // TrTinUnitTests::testDeleteTriangles
2002 //------------------------------------------------------------------------------
2004 //------------------------------------------------------------------------------
2005 void TrTinUnitTests::testDeletePoints()
2006 {
2007  BSHP<TrTin> tin = trBuildTestTin6();
2008  TS_ASSERT_EQUALS(tin->NumTriangles(), 64);
2009  TS_ASSERT_EQUALS(tin->NumPoints(), 45);
2010 
2011  SetInt toDelete = {20, 24};
2012  tin->DeletePoints(toDelete);
2013 
2014  TS_ASSERT_EQUALS(tin->NumTriangles(), 53);
2015  TS_ASSERT_EQUALS(tin->NumPoints(), 43);
2016 
2031 
2032  // Verify adjacency
2033  const VecInt2d& trisAdjToPts = tin->TrisAdjToPts();
2034 
2035  TS_ASSERT_EQUALS((VecInt{0, 1, 2, 3, 4, 11}), trisAdjToPts[10]);
2036  TS_ASSERT_EQUALS((VecInt{7, 9, 11}), trisAdjToPts[11]);
2037  TS_ASSERT_EQUALS((VecInt{9, 12, 18, 22, 24}), trisAdjToPts[20]);
2038  TS_ASSERT_EQUALS((VecInt{17, 18, 20, 23}), trisAdjToPts[27]);
2039  TS_ASSERT_EQUALS((VecInt{13, 15, 16, 17}), trisAdjToPts[26]);
2040  TS_ASSERT_EQUALS((VecInt{3, 13, 14}), trisAdjToPts[19]);
2041 
2042  TS_ASSERT_EQUALS((VecInt{28, 30, 32, 33}), trisAdjToPts[15]);
2043  TS_ASSERT_EQUALS((VecInt{32, 35, 36, 46}), trisAdjToPts[16]);
2044  TS_ASSERT_EQUALS((VecInt{45, 46, 48}), trisAdjToPts[23]);
2045  TS_ASSERT_EQUALS((VecInt{39, 40, 43, 48}), trisAdjToPts[31]);
2046  TS_ASSERT_EQUALS((VecInt{26, 28, 29, 39}), trisAdjToPts[22]);
2047 } // TrTinUnitTests::testDeletePoints
2048 
2049  //} // namespace xms
2050 
2051 #endif // CXX_TEST
xms::TrTinImpl::CheckAndSwap
bool CheckAndSwap(int a_triA, int a_triB, bool a_propagate, const VecInt &a_flags)
Swap edges if triangles combine to form convex quad. Compare to trCheckAndSwap.
Definition: TrTin.cpp:514
TS_ASSERT_DELTA_PT3D
#define TS_ASSERT_DELTA_PT3D(a, b, delta)
XM_LOG
#define XM_LOG(A, B)
xms::TrTinImpl::AdjacentTriangle
virtual int AdjacentTriangle(int a_triIdx, int a_edgeIdx) const override
Returns the triangle adjacent to a_triIdx across a_edgeIdx (0-2). Compare to trAdjacentTriangle. Example: a_edgeIdx 2 returns triangle adjacent to edge c.
Definition: TrTin.cpp:630
TrTinUnitTests::testBoundaries
void testBoundaries()
Tests TrTin::GetBoundaryPoints and TrTin::GetBoundaryPolys.
Definition: TrTin.cpp:1914
xms::TrTinImpl::TriangleFromEdge
virtual bool TriangleFromEdge(int a_pt1, int a_pt2, int &a_tri, int &a_idx1, int &a_idx2) const override
Finds the triangle with the edge defined by a_pt1 and a_pt2 and the local index of those points...
Definition: TrTin.cpp:299
xms::TrTinImpl::~TrTinImpl
virtual ~TrTinImpl()
destructor
Definition: TrTin.cpp:170
xms::TrTinImpl::PointIndexFound
bool PointIndexFound(const Pt3d &a_point) const
Predicate used in remove_if to get the index of the current item in the vector.
Definition: TrTin.cpp:962
trBuildTestTin8
BSHP< TrTin > trBuildTestTin8()
Builds a simple TIN with a hole in the middle and a concavity.
Definition: TrTin.cpp:1499
xms::TrTin::~TrTin
virtual ~TrTin()
destructor
Definition: TrTin.cpp:1240
xms::Pt3d
Pt3< double > Pt3d
xms::XM_DBL_LOWEST
static const double XM_DBL_LOWEST
xms::TrTinImpl::NextBoundaryPoint
virtual int NextBoundaryPoint(int a_point) const override
Returns the next point CW from point on the boundary. CCW if in an inside hole. Compare to trNextBoun...
Definition: TrTin.cpp:707
XM_NONE
#define XM_NONE
BOOST_CLASS_EXPORT
BOOST_CLASS_EXPORT(xms::TrTinImpl)
Cause boost.
XM_ENSURE_TRUE_VOID
#define XM_ENSURE_TRUE_VOID(...)
xms::TrTinImpl::m_pts
BSHP< VecPt3d > m_pts
tin points
Definition: TrTin.cpp:135
triangles.h
Functions dealing with triangles.
xms::TrTinImpl::LocalIndex
virtual int LocalIndex(int a_tri, int a_pt) const override
Returns index (0-2) of point within triangle given global index. Compare to trIndex.
Definition: TrTin.cpp:358
xms::TrTinImpl::InsertAdjacentTriangle
void InsertAdjacentTriangle(int a_pt, int a_tri)
Adds a_tri as an adjacent triangle to a_pt and updates m_trisAdjToPts.
Definition: TrTin.cpp:902
xms::TrTinImpl::TriIndexFound
bool TriIndexFound(const int &a_triPt) const
Predicate used in remove_if to get the index of the current item in the vector.
Definition: TrTin.cpp:947
xms::TrTinImpl::ToString
virtual std::string ToString() const override
Use boost archive to get the TrTin as text.
Definition: TrTin.cpp:1166
xms::TrTinImpl::SetTriangles
virtual void SetTriangles(BSHP< VecInt > a_tris) override
Sets the tin triangles.
Definition: TrTin.cpp:185
xms::TrTinImpl::GetExtents
virtual bool GetExtents(Pt3d &a_mn, Pt3d &a_mx) const override
Computes the extents (min, max) of the tin.
Definition: TrTin.cpp:854
trBuildTestTin
BSHP< TrTin > trBuildTestTin()
Builds a simple TIN with a hole in the middle.
Definition: TrTin.cpp:1351
xms::stShrinkCapacity
void stShrinkCapacity(std::vector< T > &v)
XM_ENSURE_TRUE_NO_ASSERT
#define XM_ENSURE_TRUE_NO_ASSERT(...)
xms::TrTinImpl::GlobalIndex
virtual int GlobalIndex(int a_triIdx, int a_localVtxIdx) const override
Returns index into m_pts of a_localPt which is 0-2.
Definition: TrTin.cpp:932
TrTin.h
TrTin.t.h
xms::VecInt
std::vector< int > VecInt
xms::TrTinImpl::SetTrianglesAdjacentToPoints
virtual void SetTrianglesAdjacentToPoints(BSHP< VecInt2d > a_trisAdjToPts) override
Sets the adjacency info of triangles adjacent to points.
Definition: TrTin.cpp:193
xms::TrTinImpl::m_tris
BSHP< VecInt > m_tris
triangles, 0-based indices to m_pts, grouped by 3s
Definition: TrTin.cpp:136
xms::TrTinImpl::Clear
virtual void Clear() override
Delete the memory.
Definition: TrTin.cpp:1146
xms::SetInt
std::set< int > SetInt
xms::TrTinImpl::BuildTrisAdjToPts
virtual void BuildTrisAdjToPts() override
Build array of triangles adjacent to points.
Definition: TrTin.cpp:1158
trBuildTestTin6
BSHP< TrTin > trBuildTestTin6()
Builds a simple TIN for testing.
Definition: TrTin.cpp:1421
TrTinUnitTests::testSwap
void testSwap()
Definition: TrTin.cpp:1805
xms::TrTinImpl::GetBoundaryPolys
virtual void GetBoundaryPolys(VecInt2d &a_polys) const override
Gets exterior boundary and all interior voids as polygons of 0-based point indices. First point is not repeated as the last point.
Definition: TrTin.cpp:807
boost_defines.h
geoms.h
Functions dealing with geometry.
XmConst.h
xms::TrTin::New
static BSHP< TrTin > New()
Create a TrTinImpl object.
Definition: TrTin.cpp:1247
xms::TrTinImpl::PointsPtr
virtual BSHP< VecPt3d > PointsPtr() override
Return the pointer to tin points.
Definition: TrTin.cpp:261
xms::TrTriangulator::Triangulate
bool Triangulate()
Triangulate the points into a tin.
Definition: TrTriangulator.cpp:55
xms::TrTinImpl
Class to encapsulate a tin made simply of arrays of points, triangles and adjacency information...
Definition: TrTin.cpp:56
xms::TrTinImpl::AdjacentIndexFound
bool AdjacentIndexFound(const VecInt &a_point) const
Predicate used in remove_if to get the index of the current item in the vector.
Definition: TrTin.cpp:977
xms::TrTinImpl::DeleteAdjacentTriangle
void DeleteAdjacentTriangle(int a_pt, int a_tri)
Removes a_tri from a_pt's adjacent triangles. Compare to vrDeleteAdjacentTrianglePtr.
Definition: TrTin.cpp:914
xms::TrTinImpl::TrisAdjToPts
virtual VecInt2d & TrisAdjToPts() override
Returns triangles adjacent to points (0-based).
Definition: TrTin.cpp:229
XM_ENSURE_TRUE
#define XM_ENSURE_TRUE(...)
xms::TrTinImpl::NumPoints
virtual int NumPoints() const override
Return the number of points.
Definition: TrTin.cpp:277
xms::TrTinImpl::DeleteTriangles
virtual void DeleteTriangles(const SetInt &a_trisToDelete) override
Deletes the triangles specified in a_trisToDelete and updates and renumbers triangle adjacency info...
Definition: TrTin.cpp:987
xms::TrTinImpl::TriangleArea
virtual double TriangleArea(int a_tri) const override
Calculate and return the area of a triangle.
Definition: TrTin.cpp:662
XM_ENSURE_TRUE_VOID_NO_ASSERT
#define XM_ENSURE_TRUE_VOID_NO_ASSERT(...)
xms::VecPt3d
std::vector< Pt3d > VecPt3d
xms::TrTinImpl::FromString
virtual void FromString(const std::string &) override
Use boost archive to turn the text into a TrTin.
Definition: TrTin.cpp:1179
xms::TrTinImpl::GetBoundaryPoints
virtual void GetBoundaryPoints(VecInt &a_boundaryPoints) const override
Gives the 0-based indices of all points on any boundary, in no particular order.
Definition: TrTin.cpp:773
xms::STRstd
std::string STRstd(double a_value, int a_n, int width, int flags)
xms::TrTinImpl::DeletePoints
virtual void DeletePoints(const SetInt &a_points) override
Deletes the points and any attached triangles, updates adjacency and renumbers things.
Definition: TrTin.cpp:1057
xms::TrTinImpl::SwapEdge
virtual bool SwapEdge(int a_triA, int a_triB, bool a_checkAngle=true) override
Swap edges if triangles combine to form convex quad. Compare to trSwapEdge.
Definition: TrTin.cpp:416
xms::TrTinImpl::PreviousBoundaryPoint
virtual int PreviousBoundaryPoint(int a_point) const override
Returns the next point CCW from point on the boundary. CW if in an inside hole. Compare to trPrevious...
Definition: TrTin.cpp:742
xms::TrTinImpl::m_toDelete
boost::unordered_set< int > m_toDelete
Used only when deleting stuff.
Definition: TrTin.cpp:138
xms::TrTinImpl::BuildTrisAdjToPtsConst
void BuildTrisAdjToPtsConst() const
A const function used only internally and needed to modify m_trisAdjToPts which is mutable...
Definition: TrTin.cpp:1210
xms::TrTinImpl::Triangles
virtual VecInt & Triangles() override
Return 0-based indices of triangle points (grouped by 3s).
Definition: TrTin.cpp:221
xms::TrTinImpl::Points
virtual VecPt3d & Points() override
Return the tin points.
Definition: TrTin.cpp:213
XM_PI
#define XM_PI
TrTriangulatorPoints.h
XM_COUNTOF
#define XM_COUNTOF(array)
xms::TrTinImpl::TriangleCentroid
virtual Pt3d TriangleCentroid(int a_tri) const override
Calculate and return the centroid of a triangle.
Definition: TrTin.cpp:649
trBuildTestTin7
BSHP< TrTin > trBuildTestTin7()
Builds a simple TIN for testing.
Definition: TrTin.cpp:1465
TrTinUnitTests::testDeletePoints
void testDeletePoints()
Tests TrTin::DeletePoints.
Definition: TrTin.cpp:2005
xms::TrTinImpl::TrTinImpl
TrTinImpl()
constructor
Definition: TrTin.cpp:160
xms::TrTinImpl::SetPoints
virtual void SetPoints(BSHP< VecPt3d > a_pts) override
Sets the tin points.
Definition: TrTin.cpp:177
xms::TrTinImpl::serialize
void serialize(Archive &archive, const unsigned int version)
Boost serialize function.
Definition: TrTin.cpp:1193
xms::TrTin::TrTin
TrTin()
constructor
Definition: TrTin.cpp:1234
XmError.h
StringUtil.h
xms::TrTinImpl::CommonEdgeIndex
virtual int CommonEdgeIndex(int a_tri, int a_adjTri) const override
Return index of common edge between triangle and neighbor. Edge index is 0-2 based on a_tri...
Definition: TrTin.cpp:595
xms::TrTinImpl::PointIsInCircumcircle
bool PointIsInCircumcircle(int a_tri1, int a_tri2, int id)
Returns true if a_localPt of a_tri2 is inside a_tri1's circumcircle.
Definition: TrTin.cpp:579
xms::xmAsserting
bool & xmAsserting()
xms::TrTinImpl::VerticesAreAdjacent
virtual bool VerticesAreAdjacent(int a_pt1, int a_pt2) const override
Return true if vertices form the edge of a triangle. Compare to vrVerticesAreAdjacent.
Definition: TrTin.cpp:375
xms::TrTinImpl::m_trisAdjToPts
BSHP< VecInt2d > m_trisAdjToPts
triangles adjacent to points. 1st dim = size of m_pts
Definition: TrTin.cpp:137
xms::VecInt2d
std::vector< VecInt > VecInt2d
xms::TrTinImpl::OptimizeTriangulation
virtual bool OptimizeTriangulation() override
Swaps triangle edges until they are a Delauney triangulation.
Definition: TrTin.cpp:1103
xms::TrTinImpl::TrianglesPtr
virtual BSHP< VecInt > TrianglesPtr() override
Return the pointer to tin triangles.
Definition: TrTin.cpp:269
trBuildTestTin2
BSHP< TrTin > trBuildTestTin2()
Builds a simple TIN for testing.
Definition: TrTin.cpp:1387
TrTinUnitTests::test1
void test1()
Tests a bunch of the TrTin methods.
Definition: TrTin.cpp:1535
TS_ASSERT_EQUALS_VEC
#define TS_ASSERT_EQUALS_VEC(a, b)
xms::TrTinImpl::SetGeometry
virtual void SetGeometry(BSHP< VecPt3d > a_pts, BSHP< VecInt > a_tris, BSHP< VecInt2d > a_trisAdjToPts) override
Set all the tin geometry at once (points, triangles, adjacency).
Definition: TrTin.cpp:203
xms::TrTinImpl::ExportTinFile
virtual void ExportTinFile(std::ostream &a_os) const override
Export in the .tin file format. Useful for debugging.
Definition: TrTin.cpp:873
xms::TrTinImpl::TriangleAdjacentToEdge
virtual int TriangleAdjacentToEdge(int a_pt1, int a_pt2) const override
Returns the triangle adjacent to the edge defined by a_pt1 and a_pt2. Compare to trTriangleAdjacentTo...
Definition: TrTin.cpp:331
TrTinUnitTests::testOptimizeTriangulation
void testOptimizeTriangulation()
Definition: TrTin.cpp:1752
xms::TrTinImpl::NumTriangles
virtual int NumTriangles() const override
Return the number of triangles.
Definition: TrTin.cpp:285
TestTools.h
TrTinUnitTests::testDeleteTriangles
void testDeleteTriangles()
Tests TrTin::DeleteTriangles.
Definition: TrTin.cpp:1943
xms::TrTriangulatorPoints
Class to triangulate simple points.
Definition: TrTriangulatorPoints.h:26
TS_ASSERT_EQUALS_VEC2D
#define TS_ASSERT_EQUALS_VEC2D(expected, actual)
xms::XM_DBL_HIGHEST
static const double XM_DBL_HIGHEST