1 /********************************************************************** 2 * 3 * GEOS - Geometry Engine Open Source 4 * http://geos.osgeo.org 5 * 6 * Copyright (C) 2020 Paul Ramsey <pramsey@cleverelephant.ca> 7 * 8 * This is free software; you can redistribute and/or modify it under 9 * the terms of the GNU Lesser General Public Licence as published 10 * by the Free Software Foundation. 11 * See the COPYING file for more information. 12 * 13 **********************************************************************/ 14 15 16 #pragma once 17 18 #include <geos/edgegraph/HalfEdge.h> 19 20 #include <geos/export.h> 21 #include <string> 22 #include <cassert> 23 #include <map> 24 #include <array> 25 #include <memory> 26 #include <vector> 27 28 // Forward declarations 29 namespace geos { 30 namespace geom { 31 class Coordinate; 32 } 33 } 34 35 #undef EDGEGRAPH_HEAPHACK 36 37 namespace geos { 38 namespace edgegraph { // geos.edgegraph 39 40 41 /** 42 * A graph comprised of {@link HalfEdge}s. 43 * It supports tracking the vertices in the graph 44 * via edges incident on them, 45 * to allow efficient lookup of edges and vertices. 46 * 47 * This class may be subclassed to use a 48 * different subclass of HalfEdge, 49 * by overriding {@link createEdge}. 50 * If additional logic is required to initialize 51 * edges then {@link addEdge} 52 * can be overridden as well. 53 * 54 * @author Martin Davis 55 * 56 */ 57 58 class GEOS_DLL EdgeGraph { 59 60 private: 61 62 std::deque<HalfEdge> edges; 63 std::map<geom::Coordinate, HalfEdge*> vertexMap; 64 65 HalfEdge* create(const geom::Coordinate& p0, const geom::Coordinate& p1); 66 67 68 protected: 69 70 /** 71 * Creates a single HalfEdge. 72 * Override to use a different HalfEdge subclass. 73 * 74 * @param orig the origin location 75 * @return a new HalfEdge with the given origin 76 */ 77 HalfEdge* createEdge(const geom::Coordinate& orig); 78 79 /** 80 * Inserts an edge not already present into the graph. 81 * 82 * @param orig the edge origin location 83 * @param dest the edge destination location 84 * @param eAdj an existing edge with same orig (if any) 85 * @return the created edge 86 */ 87 HalfEdge* insert(const geom::Coordinate& orig, const geom::Coordinate& dest, HalfEdge* eAdj); 88 89 90 public: 91 92 /** 93 * Initialized 94 */ EdgeGraph()95 EdgeGraph() {}; 96 97 /** 98 * Adds an edge between the coordinates orig and dest 99 * to this graph. 100 * Only valid edges can be added (in particular, zero-length segments cannot be added) 101 * 102 * @param orig the edge origin location 103 * @param dest the edge destination location. 104 * @return the created edge 105 * @return null if the edge was invalid and not added 106 * 107 * @see isValidEdge(Coordinate, Coordinate) 108 */ 109 HalfEdge* addEdge(const geom::Coordinate& orig, const geom::Coordinate& dest); 110 111 /** 112 * Tests if the given coordinates form a valid edge (with non-zero length). 113 * 114 * @param orig the start coordinate 115 * @param dest the end coordinate 116 * @return true if the edge formed is valid 117 */ 118 static bool isValidEdge(const geom::Coordinate& orig, const geom::Coordinate& dest); 119 120 void getVertexEdges(std::vector<const HalfEdge*>& edgesOut); 121 122 /** 123 * Finds an edge in this graph with the given origin 124 * and destination, if one exists. 125 * 126 * @param orig the origin location 127 * @param dest the destination location. 128 * @return an edge with the given orig and dest, or null if none exists 129 */ 130 HalfEdge* findEdge(const geom::Coordinate& orig, const geom::Coordinate& dest); 131 132 133 134 135 136 137 }; 138 139 140 } // namespace geos.edgegraph 141 } // namespace geos 142 143 144 145