View Javadoc
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-2018 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&lt;OTSPoint3D&gt;.
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         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 the coordinates of the line as OTSPoint3D
250      * @return the line
251      * @throws OTSGeometryException when number of points &lt; 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&lt;OTSPoint3D&gt;; 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 &lt; 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 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 }