include/geos/triangulate/quadedge/QuadEdgeSubdivision.h

   1 /**********************************************************************
   2  *
   3  * GEOS - Geometry Engine Open Source
   4  * http://geos.osgeo.org
   5  *
   6  * Copyright (C) 2012 Excensus LLC.
   7  *
   8  * This is free software; you can redistribute and/or modify it under
   9  * the terms of the GNU Lesser General Licence as published
  10  * by the Free Software Foundation.
  11  * See the COPYING file for more information.
  12  *
  13  **********************************************************************
  14  *
  15  * Last port: triangulate/quadedge/QuadEdgeSubdivision.java r524
  16  *
  17  **********************************************************************/
  18
  19 #ifndef GEOS_TRIANGULATE_QUADEDGE_QUADEDGESUBDIVISION_H
  20 #define GEOS_TRIANGULATE_QUADEDGE_QUADEDGESUBDIVISION_H
  21
  22 #include <memory>
  23 #include <list>
  24 #include <stack>
  25 #include <set>
  26 #include <vector>
  27
  28 #include <geos/geom/MultiLineString.h>
  29 #include <geos/triangulate/quadedge/QuadEdgeLocator.h>
  30 #include <geos/triangulate/quadedge/Vertex.h>
  31
  32 namespace geos {
  33
  34 namespace geom {
  35
  36         class CoordinateSequence;
  37         class GeometryCollection;
  38         class GeometryFactory;
  39         class Coordinate;
  40         class Geometry;
  41         class Envelope;
  42 }
  43
  44 namespace triangulate { //geos.triangulate
  45 namespace quadedge { //geos.triangulate.quadedge
  46
  47 class QuadEdge;
  48 class TriangleVisitor;
  49
  50 const double EDGE_COINCIDENCE_TOL_FACTOR = 1000;
  51
  52 /**
  53  * A class that contains the {@link QuadEdge}s representing a planar
  54  * subdivision that models a triangulation.
  55  * The subdivision is constructed using the
  56  * quadedge algebra defined in the classs {@link QuadEdge}.
  57  * All metric calculations
  58  * are done in the {@link Vertex} class.
  59  * In addition to a triangulation, subdivisions
  60  * support extraction of Voronoi diagrams.
  61  * This is easily accomplished, since the Voronoi diagram is the dual
  62  * of the Delaunay triangulation.
  63  * <p>
  64  * Subdivisions can be provided with a tolerance value. Inserted vertices which
  65  * are closer than this value to vertices already in the subdivision will be
  66  * ignored. Using a suitable tolerance value can prevent robustness failures
  67  * from happening during Delaunay triangulation.
  68  * <p>
  69  * Subdivisions maintain a <b>frame</b> triangle around the client-created
  70  * edges. The frame is used to provide a bounded "container" for all edges
  71  * within a TIN. Normally the frame edges, frame connecting edges, and frame
  72  * triangles are not included in client processing.
  73  *
  74  * @author JTS: David Skea
  75  * @author JTS: Martin Davis
  76  * @author Benjamin Campbell
  77  */
  78 class GEOS_DLL QuadEdgeSubdivision {
  79 public:
  80         typedef std::list<QuadEdge*> QuadEdgeList;
  81
  82         /**
  83          * Gets the edges for the triangle to the left of the given {@link QuadEdge}.
  84          *
  85          * @param startQE
  86          * @param triEdge
  87          *
  88          * @throws IllegalArgumentException
  89          *           if the edges do not form a triangle
  90          */
  91         static void getTriangleEdges(const QuadEdge &startQE,
  92                         const QuadEdge* triEdge[3]);
  93
  94 private:
  95         QuadEdgeList quadEdges;
  96         QuadEdgeList createdEdges;
  97         QuadEdge* startingEdges[3];
  98         double tolerance;
  99         double edgeCoincidenceTolerance;
 100         Vertex frameVertex[3];
 101         geom::Envelope frameEnv;
 102         std::auto_ptr<QuadEdgeLocator> locator;
 103
 104 public:
 105         /**
 106          * Creates a new instance of a quad-edge subdivision based on a frame triangle
 107          * that encloses a supplied bounding box. A new super-bounding box that
 108          * contains the triangle is computed and stored.
 109          *
 110          * @param env
 111          *          the bouding box to surround
 112          * @param tolerance
 113          *          the tolerance value for determining if two sites are equal
 114          */
 115         QuadEdgeSubdivision(const geom::Envelope &env, double tolerance);
 116
 117         virtual ~QuadEdgeSubdivision();
 118
 119 private:
 120         virtual void createFrame(const geom::Envelope &env);
 121
 122         virtual void initSubdiv(QuadEdge* initEdges[3]);
 123
 124 public:
 125         /**
 126          * Gets the vertex-equality tolerance value
 127          * used in this subdivision
 128          *
 129          * @return the tolerance value
 130          */
 131         inline double getTolerance() const {
 132                 return tolerance;
 133         }
 134
 135         /**
 136          * Gets the envelope of the Subdivision (including the frame).
 137          *
 138          * @return the envelope
 139          */
 140         inline const geom::Envelope& getEnvelope() const {
 141                 return frameEnv;
 142         }
 143
 144         /**
 145          * Gets the collection of base {@link QuadEdge}s (one for every pair of
 146          * vertices which is connected).
 147          *
 148          * @return a QuadEdgeList
 149          */
 150         inline const QuadEdgeList& getEdges() const {
 151                 return quadEdges;
 152         }
 153
 154         /**
 155          * Sets the {@link QuadEdgeLocator} to use for locating containing triangles
 156          * in this subdivision.
 157          *
 158          * @param locator
 159          *          a QuadEdgeLocator
 160          */
 161         inline void setLocator(std::auto_ptr<QuadEdgeLocator> locator) {
 162                 this->locator = locator;
 163         }
 164
 165         /**
 166          * Creates a new quadedge, recording it in the edges list.
 167          *
 168          * @param o
 169          * @param d
 170          * @return
 171          */
 172         virtual QuadEdge& makeEdge(const Vertex &o, const Vertex &d);
 173
 174         /**
 175          * Creates a new QuadEdge connecting the destination of a to the origin of b,
 176          * in such a way that all three have the same left face after the connection
 177          * is complete. The quadedge is recorded in the edges list.
 178          *
 179          * @param a
 180          * @param b
 181          * @return
 182          */
 183         virtual QuadEdge& connect(QuadEdge &a, QuadEdge &b);
 184
 185         /**
 186          * Deletes a quadedge from the subdivision. Linked quadedges are updated to
 187          * reflect the deletion.
 188          *
 189          * @param e
 190          *          the quadedge to delete
 191          */
 192         void remove(QuadEdge &e);
 193
 194         /**
 195          * Locates an edge of a triangle which contains a location
 196          * specified by a Vertex v.
 197          * The edge returned has the
 198          * property that either v is on e, or e is an edge of a triangle containing v.
 199          * The search starts from startEdge amd proceeds on the general direction of v.
 200          * <p>
 201          * This locate algorithm relies on the subdivision being Delaunay. For
 202          * non-Delaunay subdivisions, this may loop for ever.
 203          *
 204          * @param v the location to search for
 205          * @param startEdge an edge of the subdivision to start searching at
 206          * @returns a QuadEdge which contains v, or is on the edge of a triangle containing v
 207          * @throws LocateFailureException
 208          *           if the location algorithm fails to converge in a reasonable
 209          *           number of iterations. The returned pointer should not be
 210          * freed be the caller.
 211          */
 212         QuadEdge* locateFromEdge(const Vertex &v,
 213                         const QuadEdge &startEdge) const;
 214
 215         /**
 216          * Finds a quadedge of a triangle containing a location
 217          * specified by a {@link Vertex}, if one exists.
 218          *
 219          * @param x the vertex to locate
 220          * @return a quadedge on the edge of a triangle which touches or contains the location
 221          * @return null if no such triangle exists. The returned pointer should not be
 222          * freed be the caller.
 223          */
 224         inline QuadEdge* locate(const Vertex &v) const {
 225                 return locator->locate(v);
 226         }
 227
 228         /**
 229          * Finds a quadedge of a triangle containing a location
 230          * specified by a {@link Coordinate}, if one exists.
 231          *
 232          * @param p the Coordinate to locate
 233          * @return a quadedge on the edge of a triangle which touches or contains the location
 234          * @return null if no such triangle exists. The returned pointer should not be
 235          * freed be the caller.
 236          */
 237         inline QuadEdge* locate(const geom::Coordinate &p) {
 238                 return locator->locate(Vertex(p));
 239         }
 240
 241         /**
 242          * Locates the edge between the given vertices, if it exists in the
 243          * subdivision.
 244          *
 245          * @param p0 a coordinate
 246          * @param p1 another coordinate
 247          * @return the edge joining the coordinates, if present
 248          * @return null if no such edge exists
 249          * @return the caller _should not_ free the returned pointer
 250          */
 251         QuadEdge* locate(const geom::Coordinate &p0, const geom::Coordinate &p1);
 252
 253         /**
 254          * Inserts a new site into the Subdivision, connecting it to the vertices of
 255          * the containing triangle (or quadrilateral, if the split point falls on an
 256          * existing edge).
 257          * <p>
 258          * This method does NOT maintain the Delaunay condition. If desired, this must
 259          * be checked and enforced by the caller.
 260          * <p>
 261          * This method does NOT check if the inserted vertex falls on an edge. This
 262          * must be checked by the caller, since this situation may cause erroneous
 263          * triangulation
 264          *
 265          * @param v
 266          *          the vertex to insert
 267          * @return a new quad edge terminating in v
 268          */
 269         QuadEdge& insertSite(const Vertex &v);
 270
 271         /**
 272          * Tests whether a QuadEdge is an edge incident on a frame triangle vertex.
 273          *
 274          * @param e
 275          *          the edge to test
 276          * @return true if the edge is connected to the frame triangle
 277          */
 278         bool isFrameEdge(const QuadEdge &e) const;
 279
 280         /**
 281          * Tests whether a QuadEdge is an edge on the border of the frame facets and
 282          * the internal facets. E.g. an edge which does not itself touch a frame
 283          * vertex, but which touches an edge which does.
 284          *
 285          * @param e
 286          *          the edge to test
 287          * @return true if the edge is on the border of the frame
 288          */
 289         bool isFrameBorderEdge(const QuadEdge &e) const;
 290
 291         /**
 292          * Tests whether a vertex is a vertex of the outer triangle.
 293          *
 294          * @param v
 295          *          the vertex to test
 296          * @return true if the vertex is an outer triangle vertex
 297          */
 298         bool isFrameVertex(const Vertex &v) const;
 299
 300
 301         /**
 302          * Tests whether a {@link Coordinate} lies on a {@link QuadEdge}, up to a
 303          * tolerance determined by the subdivision tolerance.
 304          *
 305          * @param e
 306          *          a QuadEdge
 307          * @param p
 308          *          a point
 309          * @return true if the vertex lies on the edge
 310          */
 311         bool isOnEdge(const QuadEdge &e, const geom::Coordinate &p) const;
 312
 313         /**
 314          * Tests whether a {@link Vertex} is the start or end vertex of a
 315          * {@link QuadEdge}, up to the subdivision tolerance distance.
 316          *
 317          * @param e
 318          * @param v
 319          * @return true if the vertex is a endpoint of the edge
 320          */
 321         bool isVertexOfEdge(const QuadEdge &e, const Vertex &v) const;
 322
 323         /**
 324          * Gets all primary quadedges in the subdivision.
 325          * A primary edge is a {@link QuadEdge}
 326          * which occupies the 0'th position in its array of associated quadedges.
 327          * These provide the unique geometric edges of the triangulation.
 328          *
 329          * @param includeFrame true if the frame edges are to be included
 330          * @return a List of QuadEdges. The caller takes ownership of the returned QuadEdgeList but not the
 331          * items it contains.
 332          */
 333         std::auto_ptr<QuadEdgeList> getPrimaryEdges(bool includeFrame);
 334
 335         /*****************************************************************************
 336          * Visitors
 337          ****************************************************************************/
 338
 339         void visitTriangles(TriangleVisitor *triVisitor, bool includeFrame);
 340
 341 private:
 342         typedef std::stack<QuadEdge*> QuadEdgeStack;
 343         typedef std::set<QuadEdge*> QuadEdgeSet;
 344         typedef std::list< geom::CoordinateSequence*> TriList;
 345
 346         /**
 347          * The quadedges forming a single triangle.
 348          * Only one visitor is allowed to be active at a
 349          * time, so this is safe.
 350          */
 351         QuadEdge* triEdges[3];
 352
 353         /**
 354          * Stores the edges for a visited triangle. Also pushes sym (neighbour) edges
 355          * on stack to visit later.
 356          *
 357          * @param edge
 358          * @param edgeStack
 359          * @param includeFrame
 360          * @return the visited triangle edges
 361          * @return null if the triangle should not be visited (for instance, if it is
 362          *         outer)
 363          */
 364         QuadEdge** fetchTriangleToVisit(QuadEdge *edge, QuadEdgeStack &edgeStack, bool includeFrame,
 365                         QuadEdgeSet &visitedEdges);
 366
 367         /**
 368          * Gets the coordinates for each triangle in the subdivision as an array.
 369          *
 370          * @param includeFrame
 371          *          true if the frame triangles should be included
 372          * @param triList a list of Coordinate[4] representing each triangle
 373          */
 374         void getTriangleCoordinates(TriList* triList, bool includeFrame);
 375
 376 private:
 377         class TriangleCoordinatesVisitor;
 378         class TriangleCircumcentreVisitor;
 379
 380 public:
 381         /**
 382          * Gets the geometry for the edges in the subdivision as a {@link MultiLineString}
 383          * containing 2-point lines.
 384          *
 385          * @param geomFact the GeometryFactory to use
 386          * @return a MultiLineString. The caller takes ownership of the returned object.
 387          */
 388         std::auto_ptr<geom::MultiLineString> getEdges(const geom::GeometryFactory& geomFact);
 389
 390         /**
 391          * Gets the geometry for the triangles in a triangulated subdivision as a {@link GeometryCollection}
 392          * of triangular {@link Polygon}s.
 393          *
 394          * @param geomFact the GeometryFactory to use
 395          * @return a GeometryCollection of triangular Polygons. The caller takes ownership of the returned object.
 396          */
 397         std::auto_ptr<geom::GeometryCollection> getTriangles(const geom::GeometryFactory &geomFact);
 398
 399         /**
 400          * Gets the cells in the Voronoi diagram for this triangulation.
 401          * The cells are returned as a {@link GeometryCollection} of {@link Polygon}s
 402          * The userData of each polygon is set to be the {@link Coordinate}
 403          * of the cell site.  This allows easily associating external
 404          * data associated with the sites to the cells.
 405          *
 406          * @param geomFact a geometry factory
 407          * @return a GeometryCollection of Polygons
 408          */
 409         std::auto_ptr<geom::GeometryCollection> getVoronoiDiagram(const geom::GeometryFactory& geomFact);
 410
 411         /**
 412          * Gets a List of {@link Polygon}s for the Voronoi cells
 413          * of this triangulation.
 414          * The userData of each polygon is set to be the {@link Coordinate}
 415          * of the cell site.  This allows easily associating external
 416          * data associated with the sites to the cells.
 417          *
 418          * @param geomFact a geometry factory
 419          * @return a List of Polygons
 420          */
 421         std::auto_ptr< std::vector<geom::Geometry*> > getVoronoiCellPolygons(const geom::GeometryFactory& geomFact);
 422
 423         /**
 424          * Gets a collection of {@link QuadEdge}s whose origin
 425          * vertices are a unique set which includes
 426          * all vertices in the subdivision.
 427          * The frame vertices can be included if required.
 428          * This is useful for algorithms which require traversing the
 429          * subdivision starting at all vertices.
 430          * Returning a quadedge for each vertex
 431          * is more efficient than
 432          * the alternative of finding the actual vertices
 433          * using {@link #getVertices} and then locating
 434          * quadedges attached to them.
 435          *
 436          * @param includeFrame true if the frame vertices should be included
 437          * @return a collection of QuadEdge with the vertices of the subdivision as their origins
 438          */
 439         std::auto_ptr<QuadEdgeSubdivision::QuadEdgeList> getVertexUniqueEdges(bool includeFrame);
 440
 441         /**
 442          * Gets the Voronoi cell around a site specified
 443          * by the origin of a QuadEdge.
 444          * The userData of the polygon is set to be the {@link Coordinate}
 445          * of the site.  This allows attaching external
 446          * data associated with the site to this cell polygon.
 447          *
 448          * @param qe a quadedge originating at the cell site
 449          * @param geomFact a factory for building the polygon
 450          * @return a polygon indicating the cell extent
 451          */
 452         std::auto_ptr<geom::Geometry> getVoronoiCellPolygon(QuadEdge* qe ,const geom::GeometryFactory& geomFact);
 453 };
 454
 455 } //namespace geos.triangulate.quadedge
 456 } //namespace geos.triangulate
 457 } //namespace goes
 458
 459 #endif //GEOS_TRIANGULATE_QUADEDGE_QUADEDGESUBDIVISION_H