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 org.locationtech.jts.geom.Coordinate;
15 import org.locationtech.jts.geom.CoordinateList;
16 import org.locationtech.jts.geom.Envelope;
17 
18 /**
19  * Clips rings of points to a rectangle.
20  * Uses a variant of Cohen-Sutherland clipping.
21  * <p>
22  * In general the output is not topologically valid.
23  * In particular, the output may contain coincident non-noded line segments
24  * along the clip rectangle sides.
25  * However, the output is sufficiently well-structured
26  * that it can be used as input to the {@link OverlayNG} algorithm
27  * (which is able to process coincident linework due
28  * to the need to handle topology collapse under precision reduction).
29  * <p>
30  * Because of the likelihood of creating
31  * extraneous line segments along the clipping rectangle sides,
32  * this class is not suitable for clipping linestrings.
33  * <p>
34  * The clipping envelope should be generated using {@link RobustClipEnvelopeComputer},
35  * to ensure that intersecting line segments are not perturbed
36  * by clipping.
37  * This is required to ensure that the overlay of the
38  * clipped geometry is robust and correct (i.e. the same as
39  * if clipping was not used).
40  *
41  * @see LineLimiter
42  *
43  * @author Martin Davis
44  *
45  */
46 public class RingClipper {
47 
48   private static final int BOX_LEFT = 3;
49   private static final int BOX_TOP = 2;
50   private static final int BOX_RIGHT = 1;
51   private static final int BOX_BOTTOM = 0;
52 
53   private Envelope clipEnv;
54   private double clipEnvMinY;
55   private double clipEnvMaxY;
56   private double clipEnvMinX;
57   private double clipEnvMaxX;
58 
59   /**
60    * Creates a new clipper for the given envelope.
61    *
62    * @param clipEnv the clipping envelope
63    */
RingClipper(Envelope clipEnv)64   public RingClipper(Envelope clipEnv) {
65     this.clipEnv = clipEnv;
66     clipEnvMinY = clipEnv.getMinY();
67     clipEnvMaxY = clipEnv.getMaxY();
68     clipEnvMinX = clipEnv.getMinX();
69     clipEnvMaxX = clipEnv.getMaxX();
70   }
71 
72   /**
73    * Clips a list of points to the clipping rectangle box.
74    *
75    * @param ring
76    * @param env
77    * @return
78    */
clip(Coordinate[] pts)79   public Coordinate[] clip(Coordinate[] pts) {
80     for (int edgeIndex = 0; edgeIndex < 4; edgeIndex++) {
81       boolean closeRing = edgeIndex == 3;
82       pts = clipToBoxEdge(pts, edgeIndex, closeRing);
83       if (pts.length == 0) return pts;
84     }
85     return pts;
86   }
87 
88   /**
89    * Clips line to the axis-parallel line defined by a single box edge.
90    *
91    * @param pts
92    * @param edgeIndex
93    * @param closeRing
94    * @return
95    */
clipToBoxEdge(Coordinate[] pts, int edgeIndex, boolean closeRing)96   private Coordinate[] clipToBoxEdge(Coordinate[] pts, int edgeIndex, boolean closeRing) {
97     // TODO: is it possible to avoid copying array 4 times?
98     CoordinateList ptsClip = new CoordinateList();
99 
100     Coordinate p0 = pts[pts.length - 1];
101     for (int i = 0; i < pts.length; i++) {
102       Coordinate p1 = pts[i];
103       if ( isInsideEdge(p1, edgeIndex) ) {
104         if ( ! isInsideEdge(p0, edgeIndex) ) {
105           Coordinate intPt = intersection(p0, p1, edgeIndex);
106           ptsClip.add( intPt, false);
107         }
108         // TODO: avoid copying so much?
109         ptsClip.add( p1.copy(), false);
110 
111       } else if ( isInsideEdge(p0, edgeIndex) ) {
112         Coordinate intPt = intersection(p0, p1, edgeIndex);
113         ptsClip.add( intPt, false);
114       }
115       // else p0-p1 is outside box, so it is dropped
116 
117       p0 = p1;
118     }
119 
120     // add closing point if required
121     if (closeRing && ptsClip.size() > 0) {
122       Coordinate start = ptsClip.get(0);
123       if (! start.equals2D(ptsClip.get(ptsClip.size() - 1))) {
124         ptsClip.add( start.copy() );
125       }
126     }
127     return ptsClip.toCoordinateArray();
128   }
129 
130   /**
131    * Computes the intersection point of a segment
132    * with an edge of the clip box.
133    * The segment must be known to intersect the edge.
134    *
135    * @param a first endpoint of the segment
136    * @param b second endpoint of the segment
137    * @param edgeIndex index of box edge
138    * @return the intersection point with the box edge
139    */
intersection(Coordinate a, Coordinate b, int edgeIndex)140   private Coordinate intersection(Coordinate a, Coordinate b, int edgeIndex) {
141     Coordinate intPt;
142     switch (edgeIndex) {
143     case BOX_BOTTOM:
144       intPt = new Coordinate(intersectionLineY(a, b, clipEnvMinY), clipEnvMinY);
145       break;
146     case BOX_RIGHT:
147       intPt = new Coordinate(clipEnvMaxX, intersectionLineX(a, b, clipEnvMaxX));
148       break;
149     case BOX_TOP:
150       intPt = new Coordinate(intersectionLineY(a, b, clipEnvMaxY), clipEnvMaxY);
151       break;
152     case BOX_LEFT:
153     default:
154       intPt = new Coordinate(clipEnvMinX, intersectionLineX(a, b, clipEnvMinX));
155     }
156     return intPt;
157   }
158 
intersectionLineY(Coordinate a, Coordinate b, double y)159   private double intersectionLineY(Coordinate a, Coordinate b, double y) {
160     double m = (b.x - a.x) / (b.y - a.y);
161     double intercept = (y - a.y) * m;
162     return a.x + intercept;
163   }
164 
intersectionLineX(Coordinate a, Coordinate b, double x)165   private double intersectionLineX(Coordinate a, Coordinate b, double x) {
166     double m = (b.y - a.y) / (b.x - a.x);
167     double intercept = (x - a.x) * m;
168     return a.y + intercept;
169   }
170 
isInsideEdge(Coordinate p, int edgeIndex)171   private boolean isInsideEdge(Coordinate p, int edgeIndex) {
172     boolean isInside = false;
173     switch (edgeIndex) {
174     case BOX_BOTTOM: // bottom
175       isInside = p.y > clipEnvMinY;
176       break;
177     case BOX_RIGHT: // right
178       isInside = p.x < clipEnvMaxX;
179       break;
180     case BOX_TOP: // top
181       isInside = p.y < clipEnvMaxY;
182       break;
183     case BOX_LEFT:
184     default: // left
185       isInside = p.x > clipEnvMinX;
186     }
187     return isInside;
188   }
189 
190 }
191