1 /*
2  * Copyright (c) 2019 Martin Davis.
3  *
4  * All rights reserved. This program and the accompanying materials
5  * are made available under the terms of the Eclipse Public License 2.0
6  * and Eclipse Distribution License v. 1.0 which accompanies this distribution.
7  * The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
8  * and the Eclipse Distribution License is available at
9  *
10  * http://www.eclipse.org/org/documents/edl-v10.php.
11  */
12 package org.locationtech.jts.operation.overlayng;
13 
14 import java.util.ArrayList;
15 import java.util.Collection;
16 import java.util.HashMap;
17 import java.util.List;
18 import java.util.Map;
19 
20 import org.locationtech.jts.geom.Coordinate;
21 
22 /**
23  * A planar graph of edges, representing
24  * the topology resulting from an overlay operation.
25  * Each source edge is represented
26  * by a pair of {@link OverlayEdge}s, with opposite (symmetric) orientation.
27  * The pair of OverlayEdges share the edge coordinates
28  * and a single {@link OverlayLabel}.
29  *
30  * @author Martin Davis
31  *
32  */
33 class OverlayGraph {
34 
35   private List<OverlayEdge> edges = new ArrayList<OverlayEdge>();
36   private Map<Coordinate, OverlayEdge> nodeMap = new HashMap<Coordinate, OverlayEdge>();
37 
38   /**
39    * Creates an empty graph.
40    */
OverlayGraph()41   public OverlayGraph() {
42   }
43 
44   /**
45    * Gets the set of edges in this graph.
46    * Only one of each symmetric pair of OverlayEdges is included.
47    * The opposing edge can be found by using {@link OverlayEdge#sym()}.
48    *
49    * @return the collection of representative edges in this graph
50    */
getEdges()51   public Collection<OverlayEdge> getEdges()
52   {
53     return edges;
54   }
55 
56   /**
57    * Gets the collection of edges representing the nodes in this graph.
58    * For each star of edges originating at a node
59    * a single representative edge is included.
60    * The other edges around the node can be found by following the next and prev links.
61    *
62    * @return the collection of representative node edges
63    */
getNodeEdges()64   public Collection<OverlayEdge> getNodeEdges()
65   {
66     return nodeMap.values();
67   }
68 
69   /**
70    * Gets an edge originating at the given node point.
71    *
72    * @param nodePt the node coordinate to query
73    * @return an edge originating at the point, or null if none exists
74    */
getNodeEdge(Coordinate nodePt)75   public OverlayEdge getNodeEdge(Coordinate nodePt) {
76     return nodeMap.get(nodePt);
77   }
78 
79   /**
80    * Gets the representative edges marked as being in the result area.
81    *
82    * @return the result area edges
83    */
getResultAreaEdges()84   public List<OverlayEdge> getResultAreaEdges() {
85     List<OverlayEdge> resultEdges = new ArrayList<OverlayEdge>();
86     for (OverlayEdge edge : getEdges()) {
87       if (edge.isInResultArea()) {
88         resultEdges.add(edge);
89       }
90     }
91     return resultEdges;
92   }
93 
94   /**
95    * Adds a new edge to this graph, for the given linework and topology information.
96    * A pair of {@link OverlayEdge}s with opposite (symmetric) orientation is added,
97    * sharing the same {@link OverlayLabel}.
98    *
99    * @param pts the edge vertices
100    * @param label the edge topology information
101    * @return the created graph edge with same orientation as the linework
102    */
addEdge(Coordinate[] pts, OverlayLabel label)103   public OverlayEdge addEdge(Coordinate[] pts, OverlayLabel label) {
104     //if (! isValidEdge(orig, dest)) return null;
105     OverlayEdge e = OverlayEdge.createEdgePair(pts, label);
106     //Debug.println("added edge: " + e);
107     insert( e );
108     insert( e.symOE() );
109     return e;
110   }
111 
112   /**
113    * Inserts a single half-edge into the graph.
114    * The sym edge must also be inserted.
115    *
116    * @param e the half-edge to insert
117    */
insert(OverlayEdge e)118   private void insert(OverlayEdge e) {
119     edges.add(e);
120 
121     /**
122      * If the edge origin node is already in the graph,
123      * insert the edge into the star of edges around the node.
124      * Otherwise, add a new node for the origin.
125      */
126     OverlayEdge nodeEdge = (OverlayEdge) nodeMap.get(e.orig());
127     if (nodeEdge != null) {
128       nodeEdge.insert(e);
129     }
130     else {
131       nodeMap.put(e.orig(), e);
132     }
133   }
134 
135 }
136