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.List; 16 17 import org.locationtech.jts.geom.Coordinate; 18 import org.locationtech.jts.geom.CoordinateList; 19 import org.locationtech.jts.geom.Envelope; 20 21 /** 22 * Limits the segments in a list of segments 23 * to those which intersect an envelope. 24 * This creates zero or more sections of the input segment sequences, 25 * containing only line segments which intersect the limit envelope. 26 * Segments are not clipped, since that can move 27 * line segments enough to alter topology, 28 * and it happens in the overlay in any case. 29 * This can substantially reduce the number of vertices which need to be 30 * processed during overlay. 31 * <p> 32 * This optimization is only applicable to Line geometries, 33 * since it does not maintain the closed topology of rings. 34 * Polygonal geometries are optimized using the {@link RingClipper}. 35 * 36 * @author Martin Davis 37 * 38 * @see RingClipper 39 */ 40 public class LineLimiter { 41 private Envelope limitEnv; 42 private CoordinateList ptList; 43 private Coordinate lastOutside = null; 44 private List<Coordinate[]> sections = null; 45 46 /** 47 * Creates a new limiter for a given envelope. 48 * 49 * @param env the envelope to limit to 50 */ LineLimiter(Envelope env)51 public LineLimiter(Envelope env) { 52 this.limitEnv = env; 53 } 54 55 /** 56 * Limits a list of segments. 57 * 58 * @param pts the segment sequence to limit 59 * @return the sections which intersect the limit envelope 60 */ limit(Coordinate[] pts)61 public List<Coordinate[]> limit(Coordinate[] pts) { 62 lastOutside = null; 63 ptList = null; 64 sections = new ArrayList<Coordinate[]>(); 65 66 for (int i = 0; i < pts.length; i++) { 67 Coordinate p = pts[i]; 68 if ( limitEnv.intersects(p) ) 69 addPoint(p); 70 else { 71 addOutside(p); 72 } 73 } 74 // finish last section, if any 75 finishSection(); 76 return sections; 77 } 78 addPoint(Coordinate p)79 private void addPoint(Coordinate p) { 80 if (p == null) return; 81 startSection(); 82 ptList.add(p, false); 83 } 84 addOutside(Coordinate p)85 private void addOutside(Coordinate p) { 86 boolean segIntersects = isLastSegmentIntersecting(p); 87 if ( ! segIntersects ) { 88 finishSection(); 89 } 90 else { 91 addPoint(lastOutside); 92 addPoint(p); 93 } 94 lastOutside = p; 95 } 96 isLastSegmentIntersecting(Coordinate p)97 private boolean isLastSegmentIntersecting(Coordinate p) { 98 if (lastOutside == null) { 99 // last point must have been inside 100 if (isSectionOpen()) 101 return true; 102 return false; 103 } 104 return limitEnv.intersects(lastOutside, p); 105 } 106 isSectionOpen()107 private boolean isSectionOpen() { 108 return ptList != null; 109 } 110 startSection()111 private void startSection() { 112 if (ptList == null) { 113 ptList = new CoordinateList(); 114 } 115 if (lastOutside != null) { 116 ptList.add(lastOutside, false); 117 } 118 lastOutside = null; 119 } 120 finishSection()121 private void finishSection() { 122 if (ptList == null) 123 return; 124 // finish off this section 125 if (lastOutside != null) { 126 ptList.add(lastOutside, false); 127 lastOutside = null; 128 } 129 130 Coordinate[] section = ptList.toCoordinateArray(); 131 sections.add(section); 132 ptList = null; 133 } 134 135 }