1 2 /* 3 * Copyright (c) 2016 Vivid Solutions. 4 * 5 * All rights reserved. This program and the accompanying materials 6 * are made available under the terms of the Eclipse Public License 2.0 7 * and Eclipse Distribution License v. 1.0 which accompanies this distribution. 8 * The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html 9 * and the Eclipse Distribution License is available at 10 * 11 * http://www.eclipse.org/org/documents/edl-v10.php. 12 */ 13 package org.locationtech.jts.operation.buffer; 14 15 import java.util.ArrayList; 16 import java.util.Collection; 17 import java.util.Collections; 18 import java.util.Comparator; 19 import java.util.Iterator; 20 import java.util.List; 21 22 import org.locationtech.jts.algorithm.Orientation; 23 import org.locationtech.jts.geom.Coordinate; 24 import org.locationtech.jts.geom.Envelope; 25 import org.locationtech.jts.geom.LineSegment; 26 import org.locationtech.jts.geom.Position; 27 import org.locationtech.jts.geomgraph.DirectedEdge; 28 29 /** 30 * Locates a subgraph inside a set of subgraphs, 31 * in order to determine the outside depth of the subgraph. 32 * The input subgraphs are assumed to have had depths 33 * already calculated for their edges. 34 * 35 * @version 1.7 36 */ 37 class SubgraphDepthLocater 38 { 39 private Collection subgraphs; 40 private LineSegment seg = new LineSegment(); 41 SubgraphDepthLocater(List subgraphs)42 public SubgraphDepthLocater(List subgraphs) 43 { 44 this.subgraphs = subgraphs; 45 } 46 getDepth(Coordinate p)47 public int getDepth(Coordinate p) 48 { 49 List stabbedSegments = findStabbedSegments(p); 50 // if no segments on stabbing line subgraph must be outside all others. 51 if (stabbedSegments.size() == 0) 52 return 0; 53 DepthSegment ds = (DepthSegment) Collections.min(stabbedSegments); 54 return ds.leftDepth; 55 } 56 57 /** 58 * Finds all non-horizontal segments intersecting the stabbing line. 59 * The stabbing line is the ray to the right of stabbingRayLeftPt. 60 * 61 * @param stabbingRayLeftPt the left-hand origin of the stabbing line 62 * @return a List of {@link DepthSegments} intersecting the stabbing line 63 */ findStabbedSegments(Coordinate stabbingRayLeftPt)64 private List findStabbedSegments(Coordinate stabbingRayLeftPt) 65 { 66 List stabbedSegments = new ArrayList(); 67 for (Iterator i = subgraphs.iterator(); i.hasNext(); ) { 68 BufferSubgraph bsg = (BufferSubgraph) i.next(); 69 70 // optimization - don't bother checking subgraphs which the ray does not intersect 71 Envelope env = bsg.getEnvelope(); 72 if (stabbingRayLeftPt.y < env.getMinY() 73 || stabbingRayLeftPt.y > env.getMaxY()) 74 continue; 75 76 findStabbedSegments(stabbingRayLeftPt, bsg.getDirectedEdges(), stabbedSegments); 77 } 78 return stabbedSegments; 79 } 80 81 /** 82 * Finds all non-horizontal segments intersecting the stabbing line 83 * in the list of dirEdges. 84 * The stabbing line is the ray to the right of stabbingRayLeftPt. 85 * 86 * @param stabbingRayLeftPt the left-hand origin of the stabbing line 87 * @param stabbedSegments the current list of {@link DepthSegments} intersecting the stabbing line 88 */ findStabbedSegments(Coordinate stabbingRayLeftPt, List dirEdges, List stabbedSegments)89 private void findStabbedSegments(Coordinate stabbingRayLeftPt, 90 List dirEdges, 91 List stabbedSegments) 92 { 93 /** 94 * Check all forward DirectedEdges only. This is still general, 95 * because each Edge has a forward DirectedEdge. 96 */ 97 for (Iterator i = dirEdges.iterator(); i.hasNext();) { 98 DirectedEdge de = (DirectedEdge) i.next(); 99 if (! de.isForward()) 100 continue; 101 findStabbedSegments(stabbingRayLeftPt, de, stabbedSegments); 102 } 103 } 104 105 /** 106 * Finds all non-horizontal segments intersecting the stabbing line 107 * in the input dirEdge. 108 * The stabbing line is the ray to the right of stabbingRayLeftPt. 109 * 110 * @param stabbingRayLeftPt the left-hand origin of the stabbing line 111 * @param stabbedSegments the current list of {@link DepthSegments} intersecting the stabbing line 112 */ findStabbedSegments(Coordinate stabbingRayLeftPt, DirectedEdge dirEdge, List stabbedSegments)113 private void findStabbedSegments(Coordinate stabbingRayLeftPt, 114 DirectedEdge dirEdge, 115 List stabbedSegments) 116 { 117 Coordinate[] pts = dirEdge.getEdge().getCoordinates(); 118 for (int i = 0; i < pts.length - 1; i++) { 119 seg.p0 = pts[i]; 120 seg.p1 = pts[i + 1]; 121 // ensure segment always points upwards 122 if (seg.p0.y > seg.p1.y) 123 seg.reverse(); 124 125 // skip segment if it is left of the stabbing line 126 double maxx = Math.max(seg.p0.x, seg.p1.x); 127 if (maxx < stabbingRayLeftPt.x) 128 continue; 129 130 // skip horizontal segments (there will be a non-horizontal one carrying the same depth info 131 if (seg.isHorizontal()) 132 continue; 133 134 // skip if segment is above or below stabbing line 135 if (stabbingRayLeftPt.y < seg.p0.y || stabbingRayLeftPt.y > seg.p1.y) 136 continue; 137 138 // skip if stabbing ray is right of the segment 139 if (Orientation.index(seg.p0, seg.p1, stabbingRayLeftPt) 140 == Orientation.RIGHT) 141 continue; 142 143 // stabbing line cuts this segment, so record it 144 int depth = dirEdge.getDepth(Position.LEFT); 145 // if segment direction was flipped, use RHS depth instead 146 if (! seg.p0.equals(pts[i])) 147 depth = dirEdge.getDepth(Position.RIGHT); 148 DepthSegment ds = new DepthSegment(seg, depth); 149 stabbedSegments.add(ds); 150 } 151 } 152 153 154 /** 155 * A segment from a directed edge which has been assigned a depth value 156 * for its sides. 157 */ 158 static class DepthSegment 159 implements Comparable 160 { 161 private LineSegment upwardSeg; 162 private int leftDepth; 163 DepthSegment(LineSegment seg, int depth)164 public DepthSegment(LineSegment seg, int depth) 165 { 166 // input seg is assumed to be normalized 167 upwardSeg = new LineSegment(seg); 168 //upwardSeg.normalize(); 169 this.leftDepth = depth; 170 } 171 /** 172 * Defines a comparison operation on DepthSegments 173 * which orders them left to right. 174 * Assumes the segments are normalized. 175 * <p> 176 * The definition of the ordering is: 177 * <ul> 178 * <li>-1 : if DS1.seg is left of or below DS2.seg (DS1 < DS2) 179 * <li>1 : if DS1.seg is right of or above DS2.seg (DS1 > DS2) 180 * <li>0 : if the segments are identical 181 * </ul> 182 * 183 * KNOWN BUGS: 184 * <ul> 185 * <li>The logic does not obey the {@link Comparator.compareTo} contract. 186 * This is acceptable for the intended usage, but may cause problems if used with some 187 * utilities in the Java standard library (e.g. {@link Collections.sort()}. 188 * </ul> 189 * 190 * @param obj a DepthSegment 191 * @return the comparison value 192 */ compareTo(Object obj)193 public int compareTo(Object obj) 194 { 195 DepthSegment other = (DepthSegment) obj; 196 197 // fast check if segments are trivially ordered along X 198 if (upwardSeg.minX() >= other.upwardSeg.maxX()) return 1; 199 if (upwardSeg.maxX() <= other.upwardSeg.minX()) return -1; 200 201 /** 202 * try and compute a determinate orientation for the segments. 203 * Test returns 1 if other is left of this (i.e. this > other) 204 */ 205 int orientIndex = upwardSeg.orientationIndex(other.upwardSeg); 206 if (orientIndex != 0) return orientIndex; 207 208 /** 209 * If comparison between this and other is indeterminate, 210 * try the opposite call order. 211 * The sign of the result needs to be flipped. 212 */ 213 orientIndex = -1 * other.upwardSeg.orientationIndex(upwardSeg); 214 if (orientIndex != 0) return orientIndex; 215 216 // otherwise, use standard lexocographic segment ordering 217 return upwardSeg.compareTo(other.upwardSeg); 218 } 219 220 /** 221 * Compare two collinear segments for left-most ordering. 222 * If segs are vertical, use vertical ordering for comparison. 223 * If segs are equal, return 0. 224 * Segments are assumed to be directed so that the second coordinate is >= to the first 225 * (e.g. up and to the right). 226 * 227 * @param seg0 a segment to compare 228 * @param seg1 a segment to compare 229 * @return 230 */ compareX(LineSegment seg0, LineSegment seg1)231 private int compareX(LineSegment seg0, LineSegment seg1) 232 { 233 int compare0 = seg0.p0.compareTo(seg1.p0); 234 if (compare0 != 0) 235 return compare0; 236 return seg0.p1.compareTo(seg1.p1); 237 238 } 239 toString()240 public String toString() 241 { 242 return upwardSeg.toString(); 243 } 244 } 245 } 246