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 com.vividsolutions.jts.geom.Coordinate;
12 import com.vividsolutions.jts.geom.Geometry;
13 import com.vividsolutions.jts.geom.LineString;
14
15 /**
16 * <p>
17 * Copyright (c) 2013-2016 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 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 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 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 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 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 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 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 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 for (int i = 0; i < getPoints().length - 1; i++)
178 {
179 Line2D.Double line1 = new Line2D.Double(this.getPoints()[i].getPoint2D(), this.getPoints()[i + 1].getPoint2D());
180 for (int j = 0; j < otsShape.getPoints().length - 1; j++)
181 {
182 Line2D.Double line2 =
183 new Line2D.Double(otsShape.getPoints()[j].getPoint2D(), otsShape.getPoints()[j + 1].getPoint2D());
184
185 if (line1.intersectsLine(line2))
186 {
187 double p1x = line1.getX1(), p1y = line1.getY1(), d1x = line1.getX2() - p1x, d1y = line1.getY2() - p1y;
188 double p2x = line2.getX1(), p2y = line2.getY1(), d2x = line2.getX2() - p2x, d2y = line2.getY2() - p2y;
189
190 double det = d2x * d1y - d2y * d1x;
191 if (det == 0)
192 {
193 /*- lines (partially) overlap, indicate 0, 1 or 2 (!) cross points
194 situations:
195 X============X X============X X============X X=======X X====X
196 X---------X X------X X----X X-------X X----X
197 a. 2 intersections b. 2 intersections c. 1 intersection d. 0 inters. e. 0 inters.
198 */
199 Point2D p1s = line1.getP1(), p1e = line1.getP2(), p2s = line2.getP1(), p2e = line2.getP2();
200 if ((p1s.equals(p2s) && p1e.equals(p2e)) || (p1s.equals(p2e) && p1e.equals(p2s)))
201 {
202 return true; // situation d.
203 }
204 if (p1s.equals(p2s) && line1.ptLineDist(p2e) > 0 && line2.ptLineDist(p1e) > 0)
205 {
206 return true; // situation e.
207 }
208 if (p1e.equals(p2e) && line1.ptLineDist(p2s) > 0 && line2.ptLineDist(p1s) > 0)
209 {
210 return true; // situation e.
211 }
212 if (p1s.equals(p2e) && line1.ptLineDist(p2s) > 0 && line2.ptLineDist(p1e) > 0)
213 {
214 return true; // situation e.
215 }
216 if (p1e.equals(p2s) && line1.ptLineDist(p2e) > 0 && line2.ptLineDist(p1s) > 0)
217 {
218 return true; // situation e.
219 }
220 }
221 else
222 {
223 double z = (d2x * (p2y - p1y) + d2y * (p1x - p2x)) / det;
224 if (Math.abs(z) < 10.0 * Math.ulp(1.0) || Math.abs(z - 1.0) < 10.0 * Math.ulp(1.0))
225 {
226 return true; // intersection at end point
227 }
228 }
229
230 }
231 }
232 }
233 return false;
234 }
235
236 /**
237 * Create an OTSLine3D, while cleaning repeating successive points.
238 * @param points the coordinates of the line as OTSPoint3D
239 * @return the line
240 * @throws OTSGeometryException when number of points < 2
241 */
242 public static OTSShape createAndCleanOTSShape(final OTSPoint3D[] points) throws OTSGeometryException
243 {
244 if (points.length < 2)
245 {
246 throw new OTSGeometryException("Degenerate OTSLine3D; has " + points.length + " point"
247 + (points.length != 1 ? "s" : ""));
248 }
249 return createAndCleanOTSShape(new ArrayList<>(Arrays.asList(points)));
250 }
251
252 /**
253 * Create an OTSLine3D, while cleaning repeating successive points.
254 * @param pointList List<OTSPoint3D>; list of the coordinates of the line as OTSPoint3D; any duplicate points in this
255 * list are removed (this method may modify the provided list)
256 * @return OTSLine3D; the line
257 * @throws OTSGeometryException when number of non-equal points < 2
258 */
259 public static OTSShape createAndCleanOTSShape(final List<OTSPoint3D> pointList) throws OTSGeometryException
260 {
261 // clean successive equal points
262 int i = 1;
263 while (i < pointList.size())
264 {
265 if (pointList.get(i - 1).equals(pointList.get(i)))
266 {
267 pointList.remove(i);
268 }
269 else
270 {
271 i++;
272 }
273 }
274 return new OTSShape(pointList);
275 }
276
277 /**
278 * Small test.
279 * @param args empty
280 * @throws OTSGeometryException when construction fails
281 */
282 public static void main(final String[] args) throws OTSGeometryException
283 {
284 OTSShape s1 = new OTSShape(new OTSPoint3D(0, 0), new OTSPoint3D(10, 0), new OTSPoint3D(10, 10), new OTSPoint3D(0, 10));
285 OTSShape s2 = new OTSShape(new OTSPoint3D(5, 5), new OTSPoint3D(15, 5), new OTSPoint3D(15, 15), new OTSPoint3D(5, 15));
286 System.out.println("s1.intersect(s2): " + s1.intersects(s2));
287 System.out.println("s1.intersect(s1): " + s1.intersects(s1));
288 OTSShape s3 =
289 new OTSShape(new OTSPoint3D(25, 25), new OTSPoint3D(35, 25), new OTSPoint3D(35, 35), new OTSPoint3D(25, 35));
290 System.out.println("s1.intersect(s3): " + s1.intersects(s3));
291 }
292
293 /** {@inheritDoc} */
294 @Override
295 public final String toString()
296 {
297 return "OTSShape [shape=" + this.shape + "]";
298 }
299 }