Class RayCrossingCounter

1	/*
2	* Copyright (c) 2016 Vivid Solutions.
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	package org.locationtech.jts.algorithm;
13
14	import org.locationtech.jts.geom.Coordinate;
15	import org.locationtech.jts.geom.CoordinateSequence;
16	import org.locationtech.jts.geom.Location;
17	import org.locationtech.jts.geom.Polygonal;
18
19	/**
20	* Counts the number of segments crossed by a horizontal ray extending to the right
21	* from a given point, in an incremental fashion.
22	* This can be used to determine whether a point lies in a {@link Polygonal} geometry.
23	* The class determines the situation where the point lies exactly on a segment.
24	* When being used for Point-In-Polygon determination, this case allows short-circuiting
25	* the evaluation.
26	* <p>
27	* This class handles polygonal geometries with any number of shells and holes.
28	* The orientation of the shell and hole rings is unimportant.
29	* In order to compute a correct location for a given polygonal geometry,
30	* it is essential that <b>all</b> segments are counted which
31	* <ul>
32	* <li>touch the ray
33	* <li>lie in in any ring which may contain the point
34	* </ul>
35	* The only exception is when the point-on-segment situation is detected, in which
36	* case no further processing is required.
37	* The implication of the above rule is that segments
38	* which can be a priori determined to <i>not</i> touch the ray
39	* (i.e. by a test of their bounding box or Y-extent)
40	* do not need to be counted. This allows for optimization by indexing.
41	* <p>
42	* This implementation uses the extended-precision orientation test,
43	* to provide maximum robustness and consistency within
44	* other algorithms.
45	*
46	* @author Martin Davis
47	*
48	*/
49	public class RayCrossingCounter
50	{
51	/**
52	* Determines the {@link Location} of a point in a ring.
53	* This method is an exemplar of how to use this class.
54	*
55	* @param p the point to test
56	* @param ring an array of Coordinates forming a ring
57	* @return the location of the point in the ring
58	*/
59	public static int locatePointInRing(Coordinate p, Coordinate[] ring)
60	{
61	RayCrossingCounter counter = new RayCrossingCounter(p);
62
63	for (int i = 1; i < ring.length; i++) {
64	Coordinate p1 = ring[i];
65	Coordinate p2 = ring[i-1];
66	counter.countSegment(p1, p2);
67	if (counter.isOnSegment())
68	return counter.getLocation();
69	}
70	return counter.getLocation();
71	}
72
73	/**
74	* Determines the {@link Location} of a point in a ring.
75	*
76	* @param p
77	* the point to test
78	* @param ring
79	* a coordinate sequence forming a ring
80	* @return the location of the point in the ring
81	*/
82	public static int locatePointInRing(Coordinate p, CoordinateSequence ring) {
83	RayCrossingCounter counter = new RayCrossingCounter(p);
84
85	Coordinate p1 = new Coordinate();
86	Coordinate p2 = new Coordinate();
87	for (int i = 1; i < ring.size(); i++) {
88	ring.getCoordinate(i, p1);
89	ring.getCoordinate(i - 1, p2);
90	counter.countSegment(p1, p2);
91	if (counter.isOnSegment())
92	return counter.getLocation();
93	}
94	return counter.getLocation();
95	}
96
97	private Coordinate p;
98	private int crossingCount = 0;
99	// true if the test point lies on an input segment
100	private boolean isPointOnSegment = false;
101
102	public RayCrossingCounter(Coordinate p)
103	{
104	this.p = p;
105	}
106
107	/**
108	* Counts a segment
109	*
110	* @param p1 an endpoint of the segment
111	* @param p2 another endpoint of the segment
112	*/
113	public void countSegment(Coordinate p1, Coordinate p2) {
114	/**
115	* For each segment, check if it crosses
116	* a horizontal ray running from the test point in the positive x direction.
117	*/
118
119	// check if the segment is strictly to the left of the test point
120	if (p1.x < p.x && p2.x < p.x)
121	return;
122
123	// check if the point is equal to the current ring vertex
124	if (p.x == p2.x && p.y == p2.y) {
125	isPointOnSegment = true;
126	return;
127	}
128	/**
129	* For horizontal segments, check if the point is on the segment.
130	* Otherwise, horizontal segments are not counted.
131	*/
132	if (p1.y == p.y && p2.y == p.y) {
133	double minx = p1.x;
134	double maxx = p2.x;
135	if (minx > maxx) {
136	minx = p2.x;
137	maxx = p1.x;
138	}
139	if (p.x >= minx && p.x <= maxx) {
140	isPointOnSegment = true;
141	}
142	return;
143	}
144	/**
145	* Evaluate all non-horizontal segments which cross a horizontal ray to the
146	* right of the test pt. To avoid double-counting shared vertices, we use the
147	* convention that
148	* <ul>
149	* <li>an upward edge includes its starting endpoint, and excludes its
150	* final endpoint
151	* <li>a downward edge excludes its starting endpoint, and includes its
152	* final endpoint
153	* </ul>
154	*/
155	if (((p1.y > p.y) && (p2.y <= p.y))
156	\|\| ((p2.y > p.y) && (p1.y <= p.y))) {
157	int orient = Orientation.index(p1, p2, p);
158	if (orient == Orientation.COLLINEAR) {
159	isPointOnSegment = true;
160	return;
161	}
162	// Re-orient the result if needed to ensure effective segment direction is upwards
163	if (p2.y < p1.y) {
164	orient = -orient;
165	}
166	// The upward segment crosses the ray if the test point lies to the left (CCW) of the segment.
167	if (orient == Orientation.LEFT) {
168	crossingCount++;
169	}
170	}
171	}
172
173	/**
174	* Reports whether the point lies exactly on one of the supplied segments.
175	* This method may be called at any time as segments are processed.
176	* If the result of this method is <tt>true</tt>,
177	* no further segments need be supplied, since the result
178	* will never change again.
179	*
180	* @return true if the point lies exactly on a segment
181	*/
182	public boolean isOnSegment() { return isPointOnSegment; }
183
184	/**
185	* Gets the {@link Location} of the point relative to
186	* the ring, polygon
187	* or multipolygon from which the processed segments were provided.
188	* <p>
189	* This method only determines the correct location
190	* if <b>all</b> relevant segments must have been processed.
191	*
192	* @return the Location of the point
193	*/
194	public int getLocation()
195	{
196	if (isPointOnSegment)
197	return Location.BOUNDARY;
198
199	// The point is in the interior of the ring if the number of X-crossings is
200	// odd.
201	if ((crossingCount % 2) == 1) {
202	return Location.INTERIOR;
203	}
204	return Location.EXTERIOR;
205	}
206
207	/**
208	* Tests whether the point lies in or on
209	* the ring, polygon
210	* or multipolygon from which the processed segments were provided.
211	* <p>
212	* This method only determines the correct location
213	* if <b>all</b> relevant segments must have been processed.
214	*
215	* @return true if the point lies in or on the supplied polygon
216	*/
217	public boolean isPointInPolygon()
218	{
219	return getLocation() != Location.EXTERIOR;
220	}
221	}
222