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 }