00001
00055 #ifndef INC_MI32_PTTRIANG_H
00056 #define INC_MI32_PTTRIANG_H
00057
00058 #ifndef INC_MI32_REGION2D_H
00059 #include <mi32/region2d.h>
00060 #endif
00061
00062 #ifndef INC_MI32_BITSET_H
00063 #include <mi32/bitset.h>
00064 #endif
00065
00066 #ifndef INC_MI32_RVCTIN_H
00067 #include <mi32/rvctin.h>
00068 #endif
00069
00070 #ifndef INC_MI32_QTREE_H
00071 #include <mi32/qtree.h>
00072 #endif
00073
00074 #include <set>
00075 #include <map>
00076 #include <vector>
00077
00078 #ifdef GEOMDLL
00079 #define GEOMLIBEXPORT MI_DLLEXPORT
00080 #define GEOMLIBCLASSEXPORT MI_DLLCLASSEXPORT
00081 #else
00082 #define GEOMLIBEXPORT MI_DLLIMPORT
00083 #define GEOMLIBCLASSEXPORT MI_DLLCLASSIMPORT
00084 #endif
00085
00086
00088 class GEOMLIBCLASSEXPORT PTTRIANGULATOR {
00089
00090 public:
00091
00093 enum RULE {
00094 RULE_Delaunay = 0,
00095 RULE_ShortestEdge = 1,
00096 RULE_NoRestrictions = 2
00097 };
00098
00099 typedef SIMPLE_ARRAY<INT32> BOUNDARY;
00100 typedef MILIST<BOUNDARY> BOUNDARYLIST;
00101
00102 #ifndef GENERATING_DOXYGEN_OUTPUT
00103 enum FLAGS {
00104 FLAG_ElementBit = 0x01,
00105 FLAG_EdgeBit = 0x02,
00106 FLAG_DiagonalBit = 0x04,
00107 FLAG_Point = 0x00,
00108 FLAG_Edge = 0x01,
00109 FLAG_Clip = 0x00,
00110 FLAG_Hard = 0x02,
00111 FLAG_TLtoBR = 0x00,
00112 FLAG_BLtoTR = 0x04
00113 };
00114 #endif // GENERATING_DOXYGEN_OUTPUT
00115
00117 PTTRIANGULATOR ();
00118
00120 ~PTTRIANGULATOR ();
00121
00123 PTTRIANGULATOR& operator= (
00124 const PTTRIANGULATOR& rhs
00125 );
00126
00128 void AddHardEdge (
00129 const DPOINT2D& start,
00130 const DPOINT2D& end
00131 );
00132
00134 ERRVALUE AddHardEdge (
00135 const INT32& start,
00136 const INT32& end
00137 );
00138
00140 void AddHardLine (
00141 const POLYLINE& polyline
00142 );
00143
00146 INT32 AddPoint (
00147 const DPOINT2D& point
00148 );
00149
00152 INT32 AddPoints (
00153 const DOUBLE_ARRAY<DPOINT2D>& points
00154 );
00155
00158 INT32 AddPoints (
00159 const DOUBLE_ARRAY<DPOINT3D>& points
00160 );
00161
00164 INT32 AddPoints (
00165 const POLYLINE& polyline
00166 );
00167
00169 void ClearAll ();
00170
00171 void ClearAllSelection (
00172 ) { ClearEdgesSelection(); ClearHardEdgesSelection(); ClearTrianglesSelection(); };
00173
00175 void ClearClipRegion (
00176 ) { m_ClipRegion.Clear(); };
00177
00178 void ClearEdgesSelection (
00179 ) { m_SelectedEdges.ClearAll(); };
00180
00182 void ClearHardEdges ();
00183
00184 void ClearHardEdgesSelection (
00185 ) { m_SelectedHardEdges.ClearAll(); };
00186
00188 void ClearPoints ();
00189
00190 void ClearTrianglesSelection (
00191 ) { m_SelectedTriangles.ClearAll(); };
00192
00195 INT32 FindClosestTriangle (
00196 const DPOINT2D& point
00197 ) const;
00198
00200 INT32 FindDifferentNode (
00201 const DPOINT2D& point,
00202 const INT32 node
00203 ) const;
00204
00206 INT32 FindEdge (
00207 const DPOINT2D& point
00208 ) const;
00209
00211 INT32 FindHardEdge (
00212 const DPOINT2D& point
00213 ) const;
00214
00216 INT32 FindNode (
00217 const DPOINT2D& point
00218 ) const;
00219
00220 INT32 FindTriangle (
00221 const DPOINT2D& point
00222 ) const;
00223
00224 void GetBoundaries (
00225 BOUNDARYLIST& boundaries
00226 ) const;
00227
00230 bool GetEdgeInfo (
00231 const INT32 edge,
00232 EDGEINFO& edgeinfo
00233 ) const;
00234
00235 void GetHardEdges (
00236 SIMPLE_ARRAY<INT32>& hardedges
00237 ) const;
00238
00241 INT32 GetIndexOfNode (
00242 const INT32 node
00243 ) const;
00244
00245 ERRVALUE GetNodeEdges (
00246 const INT32 node,
00247 SIMPLE_ARRAY<INT32>& edges
00248 ) const;
00249
00250 ERRVALUE GetNodeNodes (
00251 const INT32 node,
00252 SIMPLE_ARRAY<INT32>& nodes
00253 ) const;
00254
00255 INT32 GetNodeOfIndex (
00256 const INT32 index
00257 ) const;
00258
00261 INT32 GetNumEdges (
00262 ) const { return (m_IsTriangulated ? m_WorkEdges.GetNumItems() : 0); }
00263
00266 INT32 GetNumNodes (
00267 ) const { return (m_IsTriangulated ? m_WorkPoints.GetNumItems() : 0); }
00268
00269 INT32 GetNumSelectedEdges (
00270 ) const { return (m_SelectedEdges.CountValues()); }
00271
00272 INT32 GetNumSelectedHardEdges (
00273 ) const { return (m_SelectedHardEdges.CountValues()); }
00274
00275 INT32 GetNumSelectedTriangles (
00276 ) const { return (m_SelectedTriangles.CountValues()); }
00277
00280 INT32 GetNumTriangles (
00281 ) const { return (m_IsTriangulated ? m_WorkTriangles.GetNumItems() : 0); }
00282
00285 bool GetPoint2D (
00286 const INT32 node,
00287 DPOINT2D& point
00288 ) const;
00289
00292 bool GetPoint3D (
00293 const INT32 node,
00294 DPOINT3D& point
00295 ) const;
00296
00299 RULE GetRule (
00300 ) const { return m_Rule; };
00301
00304 double GetTolerance (
00305 ) const { return m_Tolerance; };
00306
00309 bool GetTriangleEdges (
00310 const INT32 triangle,
00311 TRIANGLEEDGES& edges
00312 ) const;
00313
00316 bool GetTriangleInfo (
00317 const INT32 triangle,
00318 TRIANGLEINFO& triangleinfo
00319 ) const;
00320
00323 bool GetTriangleNodes (
00324 const INT32 triangle,
00325 TRIANGLENODES& nodes
00326 ) const;
00327
00330 bool GetTriangleTriangles (
00331 const INT32 triangle,
00332 TRIANGLETRIANGLES& triangles
00333 ) const;
00334
00335 bool IsEdgeSelected (
00336 const INT32 edge
00337 ) const { return m_SelectedEdges.GetBit(edge); }
00338
00339 bool IsHardEdge (
00340 const INT32 start,
00341 const INT32 end
00342 ) const;
00343
00344 bool IsHardEdgeSelected (
00345 const INT32 edge
00346 ) const { return m_SelectedHardEdges.GetBit(edge); }
00347
00348 bool IsSegmentIntersectedByHardEdges (
00349 const INT32 start,
00350 const INT32 end
00351 ) const;
00352
00353 bool IsTriangleSelected (
00354 const INT32 triangle
00355 ) const { return m_SelectedTriangles.GetBit(triangle); }
00356
00359 bool IsTriangulated (
00360 ) { return m_IsTriangulated; };
00361
00364 INT32 RemoveSelectedEdges ();
00365
00368 INT32 RemoveSelectedHardEdges ();
00369
00372 INT32 RemoveSelectedTriangles ();
00373
00374 void SelectEdge (
00375 const INT32 edge
00376 );
00377
00378 void SelectHardEdge (
00379 const INT32 edge
00380 );
00381
00382 void SelectTriangle (
00383 const INT32 triangle
00384 );
00385
00386 void SetBoundaries (
00387 const BOUNDARYLIST& boundaries
00388 );
00389
00391 void SetClipRegion (
00392 const REGION2D& region
00393 ) { m_IsTriangulated = false; m_ClipRegion = region; };
00394
00397 ERRVALUE Triangulate (
00398 const double tolerance = 0.0,
00399 const RULE rule = RULE_Delaunay
00400 );
00401
00402 void UnSelectEdge (
00403 const INT32 edge
00404 );
00405
00406 void UnSelectHardEdge (
00407 const INT32 edge
00408 );
00409
00410 void UnSelectTriangle (
00411 const INT32 triangle
00412 );
00413
00414 private:
00415 #ifndef GENERATING_DOXYGEN_OUTPUT
00416
00417 struct BOUNDSTRUCT {
00418 POLYLINE m_Polyline;
00419 DPOINT2D m_Point;
00420 INT32 m_Parent;
00421 INT32 m_Level;
00422
00423 BOUNDSTRUCT () : m_Parent(-1), m_Level(-1) {};
00424 };
00425
00426 struct QUADRUPLE {
00427 QUADRUPLE (
00428 const INT32 n1,
00429 const INT32 n2,
00430 const INT32 n3,
00431 const INT32 n4
00432 ) :
00433 node1(n1),
00434 node2(n2),
00435 node3(n3),
00436 node4(n4)
00437 {
00438 };
00439
00440 bool operator < (
00441 const QUADRUPLE& q
00442 ) const {
00443 if (node1 < q.node1) return true;
00444 if (node1 > q.node1) return false;
00445 if (node2 < q.node2) return true;
00446 if (node2 > q.node2) return false;
00447 if (node3 < q.node3) return true;
00448 if (node3 > q.node3) return false;
00449 if (node4 < q.node4) return true;
00450 return false;
00451 };
00452 const INT32 node1;
00453 const INT32 node2;
00454 const INT32 node3;
00455 const INT32 node4;
00456 };
00457
00458 typedef std::map<double, DPOINT2D> INTERSECTION;
00459 typedef std::pair<double, DPOINT2D> INTERSECTIONPAIR;
00460
00461 RULE m_Rule;
00462 bool m_IsTriangulated;
00463 double m_Tolerance;
00464 DOUBLE_ARRAY<DPOINT3D> m_Points;
00465 POLYLINELIST m_HardLines;
00466 DRECT2D m_Extents;
00467 REGION2D m_ClipRegion;
00468 bool m_AreHardEdgesExist;
00469 QUADTREE m_ElementQT;
00470 SIMPLE_ARRAY<FLAGS> m_ElementStatus;
00471 INT32 m_NumQTElements;
00472 QUADTREE m_EdgeQT;
00473 std::set<INT32> m_Index;
00474 BITSET m_SelectedEdges;
00475 BITSET m_SelectedTriangles;
00476 BITSET m_SelectedHardEdges;
00477 INTERSECTION m_Intersection;
00478 INTERSECTION m_LeftPoints;
00479 INTERSECTION m_RightPoints;
00480 DOUBLE_ARRAY<DPOINT2D> m_WorkPoints;
00481 DOUBLE_ARRAY<double> m_WorkZ;
00482 SIMPLE_ARRAY<INT32> m_WorkNodeOfIndex;
00483 SIMPLE_ARRAY<INT32> m_IndexOfWorkNode;
00484 SIMPLE_ARRAY<EDGEINFO> m_WorkEdges;
00485 SIMPLE_ARRAY<TRIANGLEEDGES> m_WorkTriangles;
00486 MILIST<INT32> m_WorkHull;
00487 std::set<INT32> m_DirtyEdges;
00488 mutable std::set<QUADRUPLE> m_Set;
00489 mutable DOUBLE_ARRAY<DPOINT3D> m_TempPoints;
00490 mutable SIMPLE_ARRAY<INT32> m_TempElements;
00491 mutable SIMPLE_ARRAY<INT32> m_TempEdges;
00492 mutable SIMPLE_ARRAY<INT32> m_TempArray;
00493
00494 static int ComparePoints(void*, void*, void*);
00495 static int CompareVectors(const void*, const void*);
00496 static double DistanceSquaredFromPointToSegement (const DPOINT2D& point, const DPOINT2D& start, const DPOINT2D& end);
00497 static int GetQuarter(const DPOINT3D* v);
00498
00499 bool AContainsB (std::vector<PTTRIANGULATOR::BOUNDSTRUCT>& bounds, INT32 A, INT32 B);
00500 ERRVALUE AddQTElement (const DPOINT2D& start, const DPOINT2D& end, const FLAGS flags);
00501 ERRVALUE AddSegment (const DPOINT2D& start, const DPOINT2D& end, const FLAGS flags);
00502 void CheckDirtyEdges (const bool update = false);
00503 ERRVALUE CheckEdgeIsValid(const INT32 edge);
00504 ERRVALUE CheckTopologyIsValid();
00505 ERRVALUE CheckTriangleIsValid(const INT32 triangle);
00506 bool CircleTest (const INT32 bottomnode, const INT32 leftnode, const INT32 topnode, const INT32 rightnode) const;
00507 ERRVALUE ClearStructures ();
00508 ERRVALUE CompressQTElement ();
00509 void ComputeExtents ();
00510 void ComputeWorkNodeOfIndex ();
00511 ERRVALUE ConstructAllTriangles ();
00512 double ConvexTest (const INT32 n1, const INT32 n2, const INT32 n3) const;
00513 bool FillGapEdge (const INT32 edge);
00514 void FillGapTriangle (const INT32 triangle);
00515 INT32 FindClosestEdge (const DPOINT2D& point) const;
00516 ERRVALUE FindFirstTriangle ();
00517 ERRVALUE FindPrivateEdge (const DPOINT2D& start, const DPOINT2D& end) const;
00518 ERRVALUE FindPrivateNode (const DPOINT2D& p) const;
00519 ERRVALUE FindQTElementForEdge (const INT32 edge);
00520 INT32 GetLeftBottomEdge (const INT32 edge) const;
00521 INT32 GetLeftNode (const INT32 edge) const;
00522 INT32 GetLeftTopEdge (const INT32 edge) const;
00523 INT32 GetRightBottomEdge (const INT32 edge) const;
00524 INT32 GetRightNode (const INT32 edge) const;
00525 INT32 GetRightTopEdge (const INT32 edge) const;
00526 ERRVALUE InsertHardEdge(const INT32 start, const INT32 end);
00527 ERRVALUE InsertHardEdges ();
00528 INT32 IntersectSegmentBy (const DPOINT2D& start, const DPOINT2D& end, const INT32 index, double t[2], DPOINT2D point[2]);
00529
00530 bool IsIntersectedByEdge (
00531 const DPOINT2D& start,
00532 const DPOINT2D& end,
00533 const INT32 edge,
00534 double& t,
00535 DPOINT2D& left,
00536 DPOINT2D& right
00537 );
00538
00539 bool IsPointInside(const std::vector<PTTRIANGULATOR::BOUNDSTRUCT>& bounds, const INT32 maxlevels, const DPOINT2D& point);
00540 bool IsSwapNeeded (const INT32 edge) const;
00541 ERRVALUE MakeTriangle (const DPOINT2D& p1, const DPOINT2D& p2, const DPOINT2D& p3);
00542 ERRVALUE PrepareClipRegion ();
00543 ERRVALUE PrepareHardLines ();
00544 ERRVALUE PreparePoints ();
00545 ERRVALUE RemoveOutsideEdges ();
00546 void RemovePrivateEdge (const INT32 edge);
00547 void RemovePrivateTriangle (const INT32 triangle);
00548 ERRVALUE RemoveQTElement (const INT32 index);
00549 void SetSelection();
00550 ERRVALUE SortWorkNodes ();
00551 ERRVALUE SplitSegementByNodes (const INT32 start, const INT32 end, SIMPLE_ARRAY<INT32>& array);
00552 void SwapEdge (const INT32 edge, const bool update);
00553 ERRVALUE TriangulatePolygon (INTERSECTION& Points);
00554 ERRVALUE UpdateQTEdge ();
00555 ERRVALUE UpdateQTElement (const INT32 index, const DPOINT2D& start, const DPOINT2D& end, const FLAGS flags);
00556
00557 #endif // GENERATING_DOXYGEN_OUTPUT
00558 };
00559
00560 #ifndef GENERATING_DOXYGEN_OUTPUT
00561 DEFINE_ENUM_OP_BITWISE(PTTRIANGULATOR::FLAGS)
00562 #endif
00563
00564 #endif // INC_MI32_PTTRIANG_H
