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