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