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