-- File:        BRepMesh_Delaun.cdl
-- Created:     Tue May 11 17:19:19 1993
-- Author:      Didier PIFFAULT
--              <dpf@nonox>
---Copyright:	 Matra Datavision 1993, 1994 
 

class Delaun from BRepMesh

  ---Purpose: Compute the  Delaunay's triangulation    with  the
  --          algorithm of Watson.


  uses    Integer from Standard,
          SequenceOfInteger from TColStd,
          Array1OfInteger from TColStd,
          Box2d from Bnd,
          CircleTool from BRepMesh,
          MapOfInteger from BRepMesh,
          DataStructureOfDelaun from BRepMesh,
          MapOfIntegerInteger from BRepMesh,
          Vertex from BRepMesh,
          Edge from BRepMesh,
          Triangle from BRepMesh,
          ComparatorOfVertexOfDelaun from BRepMesh,
          ComparatorOfIndexedVertexOfDelaun from BRepMesh,
          Array1OfVertexOfDelaun from BRepMesh,
          HArray1OfVertexOfDelaun from BRepMesh,
          HeapSortVertexOfDelaun from BRepMesh,
          HeapSortIndexedVertexOfDelaun from BRepMesh


  is
  -- Interface :

          Create         (Vertices  : in out Array1OfVertexOfDelaun from BRepMesh;
                          ZPositive : in Boolean from Standard=Standard_True)
              ---Purpose: Creates the  triangulation with an  empty Mesh
              --          data structure.
              returns Delaun from BRepMesh;


          Create         (OldMesh   : mutable DataStructureOfDelaun from BRepMesh;
                          Vertices  : in out Array1OfVertexOfDelaun from BRepMesh;
                          ZPositive : in Boolean from Standard=Standard_True)
              ---Purpose: Creates  the triangulation with   and existant
              --          Mesh data structure.
              returns Delaun from BRepMesh;


          Create         (OldMesh       : mutable DataStructureOfDelaun from BRepMesh;
                          VertexIndices : in out Array1OfInteger from TColStd;
                          ZPositive     : in Boolean from Standard=Standard_True)
                  ---Purpose: Creates  the triangulation with   and existant
                  --          Mesh data structure.
                  returns Delaun from BRepMesh;


          RemoveVertex   (me            : in out;
                          theVertex     : in Vertex from BRepMesh);
                ---Purpose: Removes a vertex in the triangulation.


           AddVertices    (me            : in out;
                           Vertices      : in out Array1OfVertexOfDelaun from BRepMesh);
                ---Purpose: Adds some vertices in the triangulation.


           UseEdge        (me            : in out;
                           theEdge       : in Integer from Standard)
                  ---Purpose: Modify mesh to use the edge. Return True if done.
                  returns Boolean from Standard;


           Result         (me)
                  ---C++: return const &
                  ---Purpose: Gives the Mesh data structure.
                  returns DataStructureOfDelaun from BRepMesh;


           Frontier       (me     : in out)
                  ---Purpose: Gives the list of frontier edges
                  ---C++: return const &
                  returns MapOfInteger from BRepMesh;


           InternalEdges  (me     : in out)
                  ---Purpose: Gives the list of internal edges
                  ---C++: return const &
                  returns MapOfInteger from BRepMesh;


           FreeEdges      (me     : in out)
                  ---Purpose: Gives the list of free edges used only one time
                  ---C++: return const &
                  returns MapOfInteger from BRepMesh;


           GetVertex      (me;
                           vIndex : in Integer from Standard)
                 ---C++: return const &
                 ---C++: inline
                 returns Vertex from BRepMesh;


           GetEdge        (me;
                           eIndex : in Integer from Standard)
           ---C++: return const &
           ---C++: inline
           returns Edge from BRepMesh;


           GetTriangle    (me;
                           tIndex : in Integer from Standard)
           ---C++: return const &
           ---C++: inline
           returns Triangle from BRepMesh;


           -- Implementation :

           Init           (me            : in out;
                           Vertices      : in out Array1OfVertexOfDelaun from BRepMesh);
           ---Purpose: Initializes the triangulation with an Array of
           --          Vertex.

           Compute        (me            : in out;
                            VertexIndices : in out Array1OfInteger from TColStd);
           ---Purpose: Computes the triangulation and add the vertices
           --          edges and triangles to the Mesh data structure.


           SuperMesh      (me            : in out;
                           theBox        : Box2d from Bnd);
           ---Purpose: Build the super mesh .


           FrontierAdjust (me            : in out)
           ---Purpose: Adjust the mesh on the frontier.
           is private;


           MeshLeftPolygonOf  (me        : in out;
                               EdgeIndex : Integer from Standard;
                               EdgeSens  : Boolean from Standard)
              ---Purpose: Find left polygon of the edge and call MeshPolygon.
              is private;


            MeshPolygon    (me            : in out;
                            Polygon       : in out SequenceOfInteger from TColStd)
                  ---Purpose: Mesh closed polygon.
              is private;


            CreateTriangles(me            : in out; 
                            vertexIndex   : Integer from Standard; 
                --vertex        : in Vertex from BRepMesh; 
                                freeEdges: out MapOfIntegerInteger from BRepMesh)
                ---Purpose: Creates the triangles beetween the node 
                --          <Vertex> and the polyline <freeEdges>.
              is private;


           DeleteTriangle (me         : in out; 
                            TrianIndex : Integer from Standard; 
                            freeEdges  : out MapOfIntegerInteger from BRepMesh)
               ---Purpose: Deletes the triangle of index <TrianIndex> and
               --          add the free edges to the map.
               --          When an edge is suppressed more than one time 
               --          it is destroyed.
               is private;
               
               
           Perform (me: in out;
                    theBndBox       : out Box2d from Bnd;
                    theVertexIndices: out Array1OfInteger from TColStd)
              is private;


           Contains       (me;
                           TrianIndex    : Integer from Standard;
                           theVertex     : in Vertex from BRepMesh;
                           edgeOn        : out Integer from Standard)
            ---Purpose: Test  if   triangle   of  index   <TrianIndex>
            --          contains geometricaly <theVertex>. If <EdgeOn>
            --          is != 0  then theVertex is  on Edge  of  index
            --          <edgeOn>.
            returns Boolean from Standard;


            CreateTrianglesOnNewVertices(me            : in out;
                                       theVertexIndices: out Array1OfInteger from TColStd)
                --vertex        : in Vertex from BRepMesh; 
                ---Purpose: Creates the triangles on new nodes
              is private;


            fields  MeshData               : DataStructureOfDelaun from BRepMesh;
                    PositiveOrientation    : Boolean from Standard;
                    tCircles               : CircleTool from BRepMesh;
                    supVert1               : Integer from Standard;
                    supVert2               : Integer from Standard;
                    supVert3               : Integer from Standard;
                    supTrian               : Triangle from BRepMesh;
                    mapEdges               : MapOfInteger from BRepMesh;


end Delaun;