Class PlanarPolygon3D

1	/*
2	* Copyright (c) 2016 Martin Davis.
3	*
4	* All rights reserved. This program and the accompanying materials
5	* are made available under the terms of the Eclipse Public License 2.0
6	* and Eclipse Distribution License v. 1.0 which accompanies this distribution.
7	* The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
8	* and the Eclipse Distribution License is available at
9	*
10	* http://www.eclipse.org/org/documents/edl-v10.php.
11	*/
12
13	package org.locationtech.jts.operation.distance3d;
14
15	import org.locationtech.jts.algorithm.RayCrossingCounter;
16	import org.locationtech.jts.geom.Coordinate;
17	import org.locationtech.jts.geom.CoordinateSequence;
18	import org.locationtech.jts.geom.LineString;
19	import org.locationtech.jts.geom.Location;
20	import org.locationtech.jts.geom.Polygon;
21	import org.locationtech.jts.math.Plane3D;
22	import org.locationtech.jts.math.Vector3D;
23
24	/**
25	* Models a polygon lying in a plane in 3-dimensional Cartesian space.
26	* The polygon representation is supplied
27	* by a {@link Polygon},
28	* containing coordinates with XYZ ordinates.
29	* 3D polygons are assumed to lie in a single plane.
30	* The plane best fitting the polygon coordinates is
31	* computed and is represented by a {@link Plane3D}.
32	*
33	* @author mdavis
34	*
35	*/
36	public class PlanarPolygon3D {
37
38	private Plane3D plane;
39	private Polygon poly;
40	private int facingPlane = -1;
41
42	public PlanarPolygon3D(Polygon poly) {
43	this.poly = poly;
44	plane = findBestFitPlane(poly);
45	facingPlane = plane.closestAxisPlane();
46	}
47
48	/**
49	* Finds a best-fit plane for the polygon,
50	* by sampling a few points from the exterior ring.
51	* <p>
52	* The algorithm used is Newell's algorithm:
53	* - a base point for the plane is determined from the average of all vertices
54	* - the normal vector is determined by
55	* computing the area of the projections on each of the axis planes
56	*
57	* @param poly the polygon to determine the plane for
58	* @return the best-fit plane
59	*/
60	private Plane3D findBestFitPlane(Polygon poly)
61	{
62	CoordinateSequence seq = poly.getExteriorRing().getCoordinateSequence();
63	Coordinate basePt = averagePoint(seq);
64	Vector3D normal = averageNormal(seq);
65	return new Plane3D(normal, basePt);
66	}
67
68	/**
69	* Computes an average normal vector from a list of polygon coordinates.
70	* Uses Newell's method, which is based
71	* on the fact that the vector with components
72	* equal to the areas of the projection of the polygon onto
73	* the Cartesian axis planes is normal.
74	*
75	* @param seq the sequence of coordinates for the polygon
76	* @return a normal vector
77	*/
78	private Vector3D averageNormal(CoordinateSequence seq)
79	{
80	int n = seq.size();
81	Coordinate sum = new Coordinate(0,0,0);
82	Coordinate p1 = new Coordinate(0,0,0);
83	Coordinate p2 = new Coordinate(0,0,0);
84	for (int i = 0; i < n - 1; i++) {
85	seq.getCoordinate(i, p1);
86	seq.getCoordinate(i+1, p2);
87	sum.x += (p1.y - p2.y)*(p1.getZ() + p2.getZ());
88	sum.y += (p1.getZ() - p2.getZ())*(p1.x + p2.x);
89	sum.setZ(sum.getZ() + (p1.x - p2.x)*(p1.y + p2.y));
90	}
91	sum.x /= n;
92	sum.y /= n;
93	sum.setZ(sum.getZ() / n);
94	Vector3D norm = Vector3D.create(sum).normalize();
95	return norm;
96	}
97
98	/**
99	* Computes a point which is the average of all coordinates
100	* in a sequence.
101	* If the sequence lies in a single plane,
102	* the computed point also lies in the plane.
103	*
104	* @param seq a coordinate sequence
105	* @return a Coordinate with averaged ordinates
106	*/
107	private Coordinate averagePoint(CoordinateSequence seq) {
108	Coordinate a = new Coordinate(0,0,0);
109	int n = seq.size();
110	for (int i = 0; i < n; i++) {
111	a.x += seq.getOrdinate(i, CoordinateSequence.X);
112	a.y += seq.getOrdinate(i, CoordinateSequence.Y);
113	a.setZ(a.getZ() + seq.getOrdinate(i, CoordinateSequence.Z));
114	}
115	a.x /= n;
116	a.y /= n;
117	a.setZ(a.getZ() / n);
118	return a;
119	}
120
121	public Plane3D getPlane() {
122	return plane;
123	}
124
125	public Polygon getPolygon() {
126	return poly;
127	}
128
129	public boolean intersects(Coordinate intPt) {
130	if (Location.EXTERIOR == locate(intPt, poly.getExteriorRing()))
131	return false;
132
133	for (int i = 0; i < poly.getNumInteriorRing(); i++) {
134	if (Location.INTERIOR == locate(intPt, poly.getInteriorRingN(i)))
135	return false;
136	}
137	return true;
138	}
139
140	private int locate(Coordinate pt, LineString ring) {
141	CoordinateSequence seq = ring.getCoordinateSequence();
142	CoordinateSequence seqProj = project(seq, facingPlane);
143	Coordinate ptProj = project(pt, facingPlane);
144	return RayCrossingCounter.locatePointInRing(ptProj, seqProj);
145	}
146
147	public boolean intersects(Coordinate pt, LineString ring) {
148	CoordinateSequence seq = ring.getCoordinateSequence();
149	CoordinateSequence seqProj = project(seq, facingPlane);
150	Coordinate ptProj = project(pt, facingPlane);
151	return Location.EXTERIOR != RayCrossingCounter.locatePointInRing(ptProj, seqProj);
152	}
153
154	private static CoordinateSequence project(CoordinateSequence seq, int facingPlane)
155	{
156	switch (facingPlane) {
157	case Plane3D.XY_PLANE: return AxisPlaneCoordinateSequence.projectToXY(seq);
158	case Plane3D.XZ_PLANE: return AxisPlaneCoordinateSequence.projectToXZ(seq);
159	default: return AxisPlaneCoordinateSequence.projectToYZ(seq);
160	}
161	}
162
163	private static Coordinate project(Coordinate p, int facingPlane)
164	{
165	switch (facingPlane) {
166	case Plane3D.XY_PLANE: return new Coordinate(p.x, p.y);
167	case Plane3D.XZ_PLANE: return new Coordinate(p.x, p.getZ());
168	// Plane3D.YZ
169	default: return new Coordinate(p.y, p.getZ());
170	}
171	}
172
173
174	}
175