pttriang.h

Go to the documentation of this file.

/**
 * triangle.h -- Triangulate points with break edges and clipping regions
 *
 * \if NODOC
 * $Id: pttriang.h_v 1.8 2004/05/26 20:30:41 vdronov Exp $
 *
 * $Log: pttriang.h_v $
 * Revision 1.8  2004/05/26 20:30:41  vdronov
 * added some methods
 *
 * Revision 1.7  2004/05/19 21:33:27  vdronov
 * handle boundaries
 *
 * Revision 1.6  2004/05/14 22:33:17  vdronov
 * Bondary
 *
 * Revision 1.5  2004/05/13 19:49:43  vdronov
 * many modisfications
 *
 * Revision 1.4  2004/04/21 22:57:40  vdronov
 * added pragma to eliminate warning
 *
 * Revision 1.3  2004/04/20 20:33:40  vdronov
 * added extra methods
 *
 * Revision 1.2  2004/02/27 20:35:08  vdronov
 * added GEOMDLL
 *
 * Revision 1.1  2004/02/27 01:35:11  vdronov
 * Initial revision
 *
 * \endif
*/

#ifndef  INC_MI32_PTTRIANG_H
#define  INC_MI32_PTTRIANG_H

#ifndef  INC_MI32_REGION2D_H
#include <mi32/region2d.h>
#endif

#ifndef  INC_MI32_SIMPLEAR_H
#include <mi32/simplear.h>
#endif

#ifndef  INC_MI32_DOUBLEAR_H
#include <mi32/doublear.h>
#endif

#ifndef  INC_MI32_BITSET_H
#include <mi32/bitset.h>
#endif

#ifndef  INC_MI32_POINT_H
#include <mi32/point.h>
#endif


#ifndef  INC_MI32_RVCTIN_H
#include <mi32/rvctin.h>
#endif


#ifndef  INC_MI32_QTREE_H
#include <mi32/qtree.h> 
#endif

#include <set>
#include <map>
#include <vector>

#ifdef GEOMDLL
   #define GEOMLIBEXPORT MI_DLLEXPORT
   #define GEOMLIBCLASSEXPORT MI_DLLCLASSEXPORT
#else
   #define GEOMLIBEXPORT MI_DLLIMPORT
   #define GEOMLIBCLASSEXPORT MI_DLLCLASSIMPORT
#endif

// PTTRIANGULATOR class provides algorithm of triangulation of points with respect of hard edges and clip regions.
class GEOMLIBCLASSEXPORT PTTRIANGULATOR {

public:

   //! Rule is used to swap diagonal in quadritlateral
   enum RULE {
      RULE_Delaunay = 0,
      RULE_ShorterEdge = 1
      };

   //! Type of point in triangulation
   enum POINTTYPE {
      POINTTYPE_Regular = 0,
      POINTTYPE_Break = 1,
      POINTTYPE_Clip = 2,
      POINTTYPE_Intersection = 3
      };

   //! Type of edge in triangulation
   enum EDGETYPE {
      EDGETYPE_Regular = 0,
      EDGETYPE_Break = 1,
      EDGETYPE_Clip = 2
      };

   typedef SIMPLE_ARRAY<INT32> BOUNDARY;
   typedef MILIST<BOUNDARY> BOUNDARYLIST;

   #ifndef GENERATING_DOXYGEN_OUTPUT
   enum FLAGS {
      FLAG_ElementBit = 0x01,
      FLAG_EdgeBit = 0x02,
      FLAG_DiagonalBit = 0x04,
      FLAG_Point = 0x00,
      FLAG_Edge = 0x01,
      FLAG_Clip = 0x00,
      FLAG_Hard = 0x02,
      FLAG_TLtoBR = 0x00,
      FLAG_BLtoTR = 0x04
      };
   #endif // GENERATING_DOXYGEN_OUTPUT

   //! Add point for triangulation
   //! Return index of point added for triangulation
   INT32 AddPoint (
      const DPOINT2D& point
      );

   //! Add points for triangulation
   //! Return index of first point added for triangulation
   INT32 AddPoints (
      const DOUBLE_ARRAY<DPOINT2D>& points
      );

   //! Add points for triangulation
   //! Return index of first point added for triangulation
   INT32 AddPoints (
      const DOUBLE_ARRAY<DPOINT3D>& points
      );

   //! Add hard edge for triangulation as two DPOINT2Ds
   void AddHardEdge (
      const DPOINT2D& start, const DPOINT2D& end
      );

   //! Add hard edge for triangulation as two indices for added before points
   ERRVALUE AddHardEdge (
      const INT32& start, 
      const INT32& end
      );

   //! Add hard line for triangulation as array of points
   void AddHardLine (
      const DOUBLE_ARRAY<DPOINT2D>& points
      );

   //! Add hard line for triangulation as array of points
   void AddHardLine (
      const DOUBLE_ARRAY<DPOINT3D>& points
      );

   //! Add hard line for triangulation as polyline
   void AddHardLine (
      const POLYLINE& polyline
      );

   //! Clear all input data
   void ClearAll (
      );

   //! Clear all points
   void ClearPoints (
      );

   //! Clear all hard edges and lines
   void ClearHardEdges (
      );

   //! Clear clip region
   void ClearClipRegion (
      ) { m_ClipRegion.Clear(); return; };
                              
   //! Get number of nodes in triangulation
   //! Return number of nodes
   INT32 GetNumNodes (
      ) const;

   //! Get number of edges in triangulation
   //! Return number of edges
   INT32 GetNumEdges (
      ) const;

   //! Get number of triangles triangulation
   //! Return number of triangles
   INT32 GetNumTriangles (
      ) const;

   //! Get nodes information for given triangle
   //! Return true if given triangle exists
   bool GetTriangleNodes (
      const INT32 triangle, 
      TRIANGLENODES& nodes
      ) const;

   //! Get edges information for given triangle
   //! Return true if given triangle exists
   bool GetTriangleEdges (
      const INT32 triangle, 
      TRIANGLEEDGES& edges
      ) const;

   //! Get neighbor triangles information for given triangle
   //! Return true if given triangle exists
   bool GetTriangleTriangles (
      const INT32 triangle, 
      TRIANGLETRIANGLES& triangles
      ) const;

   //! Get point for given node
   //! Return true if given node exists
   bool GetPoint (
      const INT32 node, 
      DPOINT2D& point
      ) const;

   //! Get index of node assigned when this node was added for triangulation
   //! Return index of node or -1 if node is part of break edge of clip region
   INT32 GetIndex (
      const INT32 node
      ) const;

   INT32 GetNode (
      const INT32 index
      ) const;

   POINTTYPE GetPointType (
      const INT32 node
      ) const;

   //! Get edge information for given edge
   //! Return true if given edge exists
   bool GetEdgeInfo (
      const INT32 edge, 
      EDGEINFO& edgeinfo
      ) const;

   //! Get triangle information for given edge
   //! Return true if given triangle exists
    bool GetTriangleInfo (
      const INT32 triangle, 
      TRIANGLEINFO& triangleinfo
      ) const;

   void GetBoundaries (
      BOUNDARYLIST& boundaries 
      ) const;

   void SetBoundaries (
      const BOUNDARYLIST& boundaries 
      );

   void GetHardEdges (
      SIMPLE_ARRAY<INT32>& hardedges 
      ) const;

   void ClearAllSelection(
      ) { ClearEdgesSelection(); ClearHardEdgesSelection(); ClearTrianglesSelection(); return; };

   void ClearEdgesSelection(
      ) { m_SelectedEdges.ClearAll(); return; };

    void ClearHardEdgesSelection(
      ) { m_SelectedHardEdges.ClearAll(); return; };

   void ClearTrianglesSelection(
      ) { m_SelectedTriangles.ClearAll(); return; };

    INT32 GetNumSelectedEdges(
      );

    INT32 GetNumSelectedHardEdges(
      );

   INT32 GetNumSelectedTriangles(
      );

   INT32 ExtrapolatePointsInExtents (
      const DRECT2D& extents,
      SIMPLE_ARRAY<DPOINT2D>& points 
      );

   INT32 FindNode(
      const DPOINT2D& point 
      );

   INT32 FindDifferentNode(
      const DPOINT2D& point,
      const INT32 node
      );

    INT32 FindEdge(
      const DPOINT2D& point 
      );

   INT32 FindHardEdge(
      const DPOINT2D& point 
      );

   INT32 FindTriangle(
      const DPOINT2D& point 
      );

   INT32 FindClosestTriangle(
      const DPOINT2D& point 
      );

    bool IsEdgeSelected (
      const INT32 edge 
      );

    bool IsTriangleSelected (
      const INT32 triangle
      );

    bool IsHardEdgeSelected (
      const INT32 edge 
      );

    bool IsHardEdge (
      const INT32 start,
      const INT32 end
      );

    bool IsSegmentIntersectedByHardEdges (
      const INT32 start,
      const INT32 end
      );

    INT32 RemoveSelectedEdges (
      );

    INT32 RemoveSelectedTriangles (
      );

    INT32 RemoveSelectedHardEdges (
      );

    void SelectEdge (
      const INT32 edge 
      );

    void SelectTriangle (
      const INT32 triangle
      );

    void SelectHardEdge (
      const INT32 edge 
      );

    void UnSelectEdge (
      const INT32 edge 
      );

    void UnSelectTriangle (
      const INT32 triangle
      );

    void UnSelectHardEdge (
      const INT32 edge 
      );

   //! Set clip region
   void SetClipRegion (
      const REGION2D& region
      ) { m_IsTriangulated = false; m_ClipRegion = region; return; };

   //! Get rule used for triangulation
   //! Return rule
   RULE GetRule (
      ) {return m_Rule; };

   //! Get tolerance used for triangulation
   //! Return tolerance
   double GetTolerance (
      ) {return m_Tolerance; };

   //! Get modify stamp
   //! Return modify stamp
      INT32 GetModifyStamp (
      ) { return m_ModifyStamp; };

   //! Is triangulated
   //! Return true if it is
      bool IsTriangulated (
      ) { return m_IsTriangulated; };

   //! Triangulate given set of input data for given rule and tolerance
   //! Return error code
   ERRVALUE Triangulate (
      const double tolerance = 0.0, 
      const RULE rule = RULE_Delaunay
      );

   //! Constructor
   PTTRIANGULATOR (
      );

   //! Destructor
   ~PTTRIANGULATOR (
      );

   //! Assignment operator 
   PTTRIANGULATOR& operator= (            
      const PTTRIANGULATOR& rhs
      );


private:

   #ifndef GENERATING_DOXYGEN_OUTPUT

   struct BOUNDSTRUCT {
      POLYLINE m_Polyline;
      DPOINT2D m_Point;
      INT32 m_Parent;
      INT32 m_Level;

      BOUNDSTRUCT () : m_Parent(-1), m_Level(-1) {};
      };

   struct QUADRUPLE {
      QUADRUPLE (
         const INT32 n1,
         const INT32 n2,
         const INT32 n3,
         const INT32 n4
         ) :
         node1(n1),
         node2(n2),
         node3(n3),
         node4(n4)
         {
         };

      bool operator < (
         const QUADRUPLE& q
         ) const {
         if (node1 < q.node1) return true;
         if (node1 > q.node1) return false;
         if (node2 < q.node2) return true;
         if (node2 > q.node2) return false;
         if (node3 < q.node3) return true;
         if (node3 > q.node3) return false;
         if (node4 < q.node4) return true;
         return false; 
         };
      const INT32 node1;
      const INT32 node2;
      const INT32 node3;
      const INT32 node4;
      };

   RULE m_Rule;
   bool m_IsTriangulated;
   double m_Tolerance;
   INT32 m_ModifyStamp;

#pragma warning (disable:4251)
   SIMPLE_ARRAY<DPOINT2D> m_Points;
   POLYLINELIST m_HardLines;
#pragma warning (default:4251)

   REGION2D m_ClipRegion;
   bool m_AreHardEdgesExist;

   QUADTREE m_ElementQT;
#pragma warning (disable:4251)
   SIMPLE_ARRAY<FLAGS> m_ElementStatus;
#pragma warning (default:4251)
   INT32 m_NumQTElements;

   QUADTREE m_EdgeQT;
   INT32 m_NumQTEdges;

#pragma warning (disable:4251)
   std::set<INT32> m_Index;
   
   BITSET m_SelectedEdges;
   BITSET m_SelectedTriangles;
   BITSET m_SelectedHardEdges;
   
   typedef std::map<double, DPOINT2D> INTERSECTION;
   typedef std::pair<double, DPOINT2D> INTERSECTIONPAIR;

   INTERSECTION m_Intersection;
   INTERSECTION m_LeftPoints;
   INTERSECTION m_RightPoints;

   SIMPLE_ARRAY<DPOINT3D> m_WorkPoints;   // z coordinate is index of point
   SIMPLE_ARRAY<EDGEINFO> m_WorkEdges;
   SIMPLE_ARRAY<TRIANGLEEDGES> m_WorkTriangles;

   MILIST<INT32> m_WorkHull;      
   std::set<INT32> m_DirtyEdges;
   std::set<QUADRUPLE> m_Set;       
#pragma warning (default:4251)

   static int ComparePoints(const void *vp1, const void *vp2);

   double ConvexTest (const INT32 n1, const INT32 n2, const INT32 n3);

   ERRVALUE ClearStructures ();
   ERRVALUE PrepareQuadTrees ();
   ERRVALUE PreparePoints ();
   ERRVALUE PrepareClipRegion();
   ERRVALUE PrepareHardLines ();
   ERRVALUE AddSegment (const DPOINT2D& start, const DPOINT2D& end, const FLAGS flags);
   INT32 IntersectSegmentBy (const DPOINT2D& start, const DPOINT2D& end, const INT32 index, double t[2], DPOINT2D point[2]);
   ERRVALUE AddQTElement (const DPOINT2D& start, const DPOINT2D& end, const FLAGS flags);
   ERRVALUE FindQTElementForEdge (const INT32 edge);

   ERRVALUE UpdateQTElement (const INT32 index, const DPOINT2D& start, const DPOINT2D& end, const FLAGS flags);
   ERRVALUE RemoveQTElement (const INT32 index);
   ERRVALUE CompressQTElement ();
   ERRVALUE UpdateQTEdge ();
   ERRVALUE InsertHardEdges ();
   ERRVALUE InsertHardEdge(const INT32 start, const INT32 end);
   ERRVALUE SplitSegementByNodes (const INT32 start, const INT32 end, SIMPLE_ARRAY<INT32>& array);
   bool IsIntersectedByEdge (
      const DPOINT2D& start, 
      const DPOINT2D& end, 
      const INT32 edge, 
      double& t, 
      DPOINT2D& left,
      DPOINT2D& right
      );
   ERRVALUE TriangulatePolygon (INTERSECTION& Points);
   ERRVALUE MakeTriangle (const DPOINT2D& p1, const DPOINT2D& p2, const DPOINT2D& p3);
   ERRVALUE FindPrivateNode (const DPOINT2D& p);
   ERRVALUE FindPrivateEdge (const DPOINT2D& start, const DPOINT2D& end);

   ERRVALUE SortWorkNodes ();
   ERRVALUE FindFirstTriangle ();
   ERRVALUE ConstructAllTriangles ();
   ERRVALUE RemoveOutsideEdges ();
   ERRVALUE CheckDirtyEdges (const bool update = false);

   bool IsSwapNeeded (const INT32 edge);
   ERRVALUE SwapEdge (const INT32 edge, const bool update);
   INT32 GetLeftNode (const INT32 edge) const;
   INT32 GetLeftBottomEdge (const INT32 edge) const;
   INT32 GetLeftTopEdge (const INT32 edge) const;
   INT32 GetRightBottomEdge (const INT32 edge) const;
   INT32 GetRightTopEdge (const INT32 edge) const;
   INT32 GetRightNode (const INT32 edge) const;
   bool CircleTest (const INT32 bottomnode, const INT32 leftnode, const INT32 topnode, const INT32 rightnode); 
   void RemovePrivateEdge (const INT32 edge);
   void RemovePrivateTriangle (const INT32 triangle);
   bool FillGapEdge (const INT32 edge);
   void FillGapTriangle (const INT32 triangle);
   void SetSelection();

   double DistanceSquaredFromPointToSegement (const DPOINT2D& point, const DPOINT2D& start, const DPOINT2D& end);
   INT32 FindAnyEdge(const DPOINT2D& point);

   ERRVALUE CheckTopologyIsValid();
   ERRVALUE CheckEdgeIsValid(const INT32 edge);
   ERRVALUE CheckTriangleIsValid(const INT32 triangle);

   bool AContainsB (std::vector<PTTRIANGULATOR::BOUNDSTRUCT>& bounds, INT32 A, INT32 B);
   bool IsPointInside(const std::vector<PTTRIANGULATOR::BOUNDSTRUCT>& bounds, const INT32 maxlevels, const DPOINT2D& point);

   #endif // GENERATING_DOXYGEN_OUTPUT
   };

DEFINE_ENUM_OPERATORS(PTTRIANGULATOR::FLAGS);

#endif   //!< INC_MI32_PTTRIANG_H

---