1 package org.opentrafficsim.core.geometry;
2
3 import java.awt.geom.Line2D;
4 import java.awt.geom.Path2D;
5 import java.awt.geom.Point2D;
6 import java.awt.geom.Rectangle2D;
7 import java.util.ArrayList;
8 import java.util.Arrays;
9 import java.util.List;
10
11 import org.locationtech.jts.geom.Coordinate;
12 import org.locationtech.jts.geom.Geometry;
13 import org.locationtech.jts.geom.LineString;
14
15 /**
16 * <p>
17 * Copyright (c) 2013-2019 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved. <br>
18 * BSD-style license. See <a href="http://opentrafficsim.org/docs/license.html">OpenTrafficSim License</a>.
19 * </p>
20 * $LastChangedDate: 2015-07-24 02:58:59 +0200 (Fri, 24 Jul 2015) $, @version $Revision: 1147 $, by $Author: averbraeck $,
21 * initial version Mar 31, 2016 <br>
22 * @author <a href="http://www.tbm.tudelft.nl/averbraeck">Alexander Verbraeck</a>
23 * @author <a href="http://www.tudelft.nl/pknoppers">Peter Knoppers</a>
24 */
25 public class OTSShape extends OTSLine3D
26 {
27 /** */
28 private static final long serialVersionUID = 20160331;
29
30 /** The underlying shape (only constructed if needed). */
31 private Path2D shape = null;
32
33 /**
34 * Construct a new OTSShape (closed shape).
35 * @param points OTSPoint3D...; the array of points to construct this OTSLine3D from.
36 * @throws OTSGeometryException when the provided points do not constitute a valid line (too few points or identical
37 * adjacent points)
38 */
39 public OTSShape(final OTSPoint3D... points) throws OTSGeometryException
40 {
41 super(points);
42 }
43
44 /**
45 * Construct a new OTSShape (closed shape) from an array of Coordinate.
46 * @param coordinates Coordinate[]; the array of coordinates to construct this OTSLine3D from
47 * @throws OTSGeometryException when the provided points do not constitute a valid line (too few points or identical
48 * adjacent points)
49 */
50 public OTSShape(final Coordinate[] coordinates) throws OTSGeometryException
51 {
52 super(coordinates);
53 }
54
55 /**
56 * Construct a new OTSShape (closed shape) from a LineString.
57 * @param lineString LineString; the lineString to construct this OTSLine3D from.
58 * @throws OTSGeometryException when the provided LineString does not constitute a valid line (too few points or identical
59 * adjacent points)
60 */
61 public OTSShape(final LineString lineString) throws OTSGeometryException
62 {
63 super(lineString);
64 }
65
66 /**
67 * Construct a new OTSShape (closed shape) from a Geometry.
68 * @param geometry Geometry; the geometry to construct this OTSLine3D from
69 * @throws OTSGeometryException when the provided Geometry do not constitute a valid line (too few points or identical
70 * adjacent points)
71 */
72 public OTSShape(final Geometry geometry) throws OTSGeometryException
73 {
74 super(geometry);
75 }
76
77 /**
78 * Construct a new OTSShape (closed shape) from a List<OTSPoint3D>.
79 * @param pointList List<OTSPoint3D>; the list of points to construct this OTSLine3D from.
80 * @throws OTSGeometryException when the provided points do not constitute a valid line (too few points or identical
81 * adjacent points)
82 */
83 public OTSShape(final List<OTSPoint3D> pointList) throws OTSGeometryException
84 {
85 super(pointList);
86 }
87
88 /**
89 * Construct a new OTSShape (closed shape) from a Path2D.
90 * @param path Path2D; the Path2D to construct this OTSLine3D from.
91 * @throws OTSGeometryException when the provided points do not constitute a valid line (too few points or identical
92 * adjacent points)
93 */
94 public OTSShape(final Path2D path) throws OTSGeometryException
95 {
96 super(path);
97 }
98
99 /**
100 * @return shape
101 */
102 public final Path2D getShape()
103 {
104 if (this.shape == null)
105 {
106 calculateShape();
107 }
108 return this.shape;
109 }
110
111 /**
112 * calculate the java.awt.Shape, and close it if needed.
113 */
114 private void calculateShape()
115 {
116 this.shape = new Path2D.Double();
117 this.shape.moveTo(getPoints()[0].x, getPoints()[0].y);
118 for (int i = 1; i < getPoints().length; i++)
119 {
120 this.shape.lineTo(getPoints()[i].x, getPoints()[i].y);
121 }
122 this.shape.closePath();
123 }
124
125 /**
126 * @param point OTSPoint3D; the point to check if it is inside the shape
127 * @return whether the point is inside the shape
128 */
129 public final boolean contains(final OTSPoint3D point)
130 {
131 return getShape().contains(point.x, point.y);
132 }
133
134 /**
135 * Check if this OTSShape completely covers a rectangular region.
136 * @param rectangle Rectangle2D; the rectangular region
137 * @return boolean; true if this OTSShape completely covers the region; false otherwise (or when the implementation of
138 * java.awt.geom.Path2D.contains found it prohibitively expensive to decide. Let us hope that this cannot happen
139 * with OTSShape objects. Peter has been unable to find out when this might happen.
140 */
141 public final boolean contains(final Rectangle2D rectangle)
142 {
143 return getShape().contains(rectangle);
144 }
145
146 /**
147 * @param otsShape OTSShape; the shape to test the intersection with
148 * @return whether the shapes intersect or whether one shape contains the other
149 */
150 public final boolean intersects(final OTSShape otsShape)
151 {
152 // step 1: quick check to see if the bounds intersect
153 if (!getEnvelope().intersects(otsShape.getEnvelope()))
154 {
155 return false;
156 }
157
158 // step 2: quick check to see if any of the points of shape 1 is in shape 2
159 for (OTSPoint3D p : getPoints())
160 {
161 if (otsShape.contains(p))
162 {
163 return true;
164 }
165 }
166
167 // step 3: quick check to see if any of the points of shape 2 is in shape 1
168 for (OTSPoint3D p : otsShape.getPoints())
169 {
170 if (contains(p))
171 {
172 return true;
173 }
174 }
175
176 // step 4: see if any of the lines of shape 1 and shape 2 intersect (expensive!)
177 Point2D prevPoint = getPoints()[this.size() - 1].getPoint2D();
178 // for (int i = 0; i < getPoints().length - 1; i++)
179 // {
180 for (OTSPoint3D point : this.getPoints())
181 {
182 Point2D nextPoint = point.getPoint2D();
183 Line2D.Double line1 = new Line2D.Double(prevPoint, nextPoint);
184 // Line2D.Double line1 = new Line2D.Double(this.getPoints()[i].getPoint2D(), this.getPoints()[i + 1].getPoint2D());
185 // for (int j = 0; j < otsShape.getPoints().length - 1; j++)
186 // {
187 Point2D otherPrevPoint = otsShape.getPoints()[otsShape.size() - 1].getPoint2D();
188 for (OTSPoint3D otherPoint : otsShape.getPoints())
189 {
190 Point2D otherNextPoint = otherPoint.getPoint2D();
191 // Line2D.Double line2 =
192 // new Line2D.Double(otsShape.getPoints()[j].getPoint2D(), otsShape.getPoints()[j + 1].getPoint2D());
193 Line2D.Double line2 = new Line2D.Double(otherPrevPoint, otherNextPoint);
194 if (line1.intersectsLine(line2))
195 {
196 double p1x = line1.getX1(), p1y = line1.getY1(), d1x = line1.getX2() - p1x, d1y = line1.getY2() - p1y;
197 double p2x = line2.getX1(), p2y = line2.getY1(), d2x = line2.getX2() - p2x, d2y = line2.getY2() - p2y;
198
199 double det = d2x * d1y - d2y * d1x;
200 if (det == 0)
201 {
202 /*- lines (partially) overlap, indicate 0, 1 or 2 (!) cross points
203 situations:
204 X============X X============X X============X X=======X X====X
205 X---------X X------X X----X X-------X X----X
206 a. 2 intersections b. 2 intersections c. 1 intersection d. 0 inters. e. 0 inters.
207 */
208 Point2D p1s = line1.getP1(), p1e = line1.getP2(), p2s = line2.getP1(), p2e = line2.getP2();
209 if ((p1s.equals(p2s) && p1e.equals(p2e)) || (p1s.equals(p2e) && p1e.equals(p2s)))
210 {
211 return true; // situation d.
212 }
213 if (p1s.equals(p2s) && line1.ptLineDist(p2e) > 0 && line2.ptLineDist(p1e) > 0)
214 {
215 return true; // situation e.
216 }
217 if (p1e.equals(p2e) && line1.ptLineDist(p2s) > 0 && line2.ptLineDist(p1s) > 0)
218 {
219 return true; // situation e.
220 }
221 if (p1s.equals(p2e) && line1.ptLineDist(p2s) > 0 && line2.ptLineDist(p1e) > 0)
222 {
223 return true; // situation e.
224 }
225 if (p1e.equals(p2s) && line1.ptLineDist(p2e) > 0 && line2.ptLineDist(p1s) > 0)
226 {
227 return true; // situation e.
228 }
229 }
230 else
231 {
232 double z = (d2x * (p2y - p1y) + d2y * (p1x - p2x)) / det;
233 if (Math.abs(z) < 10.0 * Math.ulp(1.0) || Math.abs(z - 1.0) > 10.0 * Math.ulp(1.0))
234 {
235 return true; // intersection at end point
236 }
237 }
238
239 }
240 otherPrevPoint = otherNextPoint;
241 }
242 prevPoint = nextPoint;
243 }
244 return false;
245 }
246
247 /**
248 * Create an OTSLine3D, while cleaning repeating successive points.
249 * @param points OTSPoint3D[]; the coordinates of the line as OTSPoint3D
250 * @return the line
251 * @throws OTSGeometryException when number of points < 2
252 */
253 public static OTSShape createAndCleanOTSShape(final OTSPoint3D[] points) throws OTSGeometryException
254 {
255 if (points.length < 2)
256 {
257 throw new OTSGeometryException(
258 "Degenerate OTSLine3D; has " + points.length + " point" + (points.length != 1 ? "s" : ""));
259 }
260 return createAndCleanOTSShape(new ArrayList<>(Arrays.asList(points)));
261 }
262
263 /**
264 * Create an OTSLine3D, while cleaning repeating successive points.
265 * @param pointList List<OTSPoint3D>; list of the coordinates of the line as OTSPoint3D; any duplicate points in this
266 * list are removed (this method may modify the provided list)
267 * @return OTSLine3D; the line
268 * @throws OTSGeometryException when number of non-equal points < 2
269 */
270 public static OTSShape createAndCleanOTSShape(final List<OTSPoint3D> pointList) throws OTSGeometryException
271 {
272 // clean successive equal points
273 int i = 1;
274 while (i < pointList.size())
275 {
276 if (pointList.get(i - 1).equals(pointList.get(i)))
277 {
278 pointList.remove(i);
279 }
280 else
281 {
282 i++;
283 }
284 }
285 return new OTSShape(pointList);
286 }
287
288 /**
289 * Small test.
290 * @param args String[]; empty
291 * @throws OTSGeometryException when construction fails
292 */
293 public static void main(final String[] args) throws OTSGeometryException
294 {
295 OTSShape s1 = new OTSShape(new OTSPoint3D(0, 0), new OTSPoint3D(10, 0), new OTSPoint3D(10, 10), new OTSPoint3D(0, 10));
296 OTSShape s2 = new OTSShape(new OTSPoint3D(5, 5), new OTSPoint3D(15, 5), new OTSPoint3D(15, 15), new OTSPoint3D(5, 15));
297 System.out.println("s1.intersect(s2): " + s1.intersects(s2));
298 System.out.println("s1.intersect(s1): " + s1.intersects(s1));
299 OTSShape s3 =
300 new OTSShape(new OTSPoint3D(25, 25), new OTSPoint3D(35, 25), new OTSPoint3D(35, 35), new OTSPoint3D(25, 35));
301 System.out.println("s1.intersect(s3): " + s1.intersects(s3));
302 }
303
304 /** {@inheritDoc} */
305 @Override
306 public final String toString()
307 {
308 return "OTSShape [shape=" + this.shape + "]";
309 }
310 }