Class IndexedPointInAreaLocator

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.locate;
13
14	import java.util.ArrayList;
15	import java.util.Iterator;
16	import java.util.List;
17
18	import org.locationtech.jts.algorithm.RayCrossingCounter;
19	import org.locationtech.jts.geom.Coordinate;
20	import org.locationtech.jts.geom.Geometry;
21	import org.locationtech.jts.geom.LineSegment;
22	import org.locationtech.jts.geom.LineString;
23	import org.locationtech.jts.geom.LinearRing;
24	import org.locationtech.jts.geom.Location;
25	import org.locationtech.jts.geom.Polygonal;
26	import org.locationtech.jts.geom.util.LinearComponentExtracter;
27	import org.locationtech.jts.index.ArrayListVisitor;
28	import org.locationtech.jts.index.ItemVisitor;
29	import org.locationtech.jts.index.intervalrtree.SortedPackedIntervalRTree;
30
31
32	/**
33	* Determines the {@link Location} of {@link Coordinate}s relative to
34	* an areal geometry, using indexing for efficiency.
35	* This algorithm is suitable for use in cases where
36	* many points will be tested against a given area.
37	* <p>
38	* The Location is computed precisely, in that points
39	* located on the geometry boundary or segments will
40	* return {@link Location.BOUNDARY}.
41	* <p>
42	* {@link Polygonal} and {@link LinearRing} geometries
43	* are supported.
44	* <p>
45	* The index is lazy-loaded, which allows
46	* creating instances even if they are not used.
47	* <p>
48	* Thread-safe and immutable.
49	*
50	* @author Martin Davis
51	*
52	*/
53	public class IndexedPointInAreaLocator
54	implements PointOnGeometryLocator
55	{
56
57	private Geometry geom;
58	private IntervalIndexedGeometry index = null;
59
60	/**
61	* Creates a new locator for a given {@link Geometry}.
62	* {@link Polygonal} and {@link LinearRing} geometries
63	* are supported.
64	*
65	* @param g the Geometry to locate in
66	*/
67	public IndexedPointInAreaLocator(Geometry g)
68	{
69	if (! (g instanceof Polygonal \|\| g instanceof LinearRing))
70	throw new IllegalArgumentException("Argument must be Polygonal or LinearRing");
71	geom = g;
72	}
73
74	/**
75	* Determines the {@link Location} of a point in an areal {@link Geometry}.
76	*
77	* @param p the point to test
78	* @return the location of the point in the geometry
79	*/
80	public int locate(Coordinate p)
81	{
82	// avoid calling synchronized method improves performance
83	if (index == null) createIndex();
84
85	RayCrossingCounter rcc = new RayCrossingCounter(p);
86
87	SegmentVisitor visitor = new SegmentVisitor(rcc);
88	index.query(p.y, p.y, visitor);
89
90	/*
91	// MD - slightly slower alternative
92	List segs = index.query(p.y, p.y);
93	countSegs(rcc, segs);
94	*/
95
96	return rcc.getLocation();
97	}
98
99	/**
100	* Creates the indexed geometry, creating it if necessary.
101	*/
102	private synchronized void createIndex() {
103	if (index == null) {
104	index = new IntervalIndexedGeometry(geom);
105	// no need to hold onto geom
106	geom = null;
107	}
108	}
109
110	private static class SegmentVisitor
111	implements ItemVisitor
112	{
113	private RayCrossingCounter counter;
114
115	public SegmentVisitor(RayCrossingCounter counter)
116	{
117	this.counter = counter;
118	}
119
120	public void visitItem(Object item)
121	{
122	LineSegment seg = (LineSegment) item;
123	counter.countSegment(seg.getCoordinate(0), seg.getCoordinate(1));
124	}
125	}
126
127	private static class IntervalIndexedGeometry
128	{
129	private boolean isEmpty = false;
130	private SortedPackedIntervalRTree index= new SortedPackedIntervalRTree();
131
132	public IntervalIndexedGeometry(Geometry geom)
133	{
134	if (geom.isEmpty())
135	isEmpty = true;
136	else
137	init(geom);
138	}
139
140	private void init(Geometry geom)
141	{
142	List lines = LinearComponentExtracter.getLines(geom);
143	for (Iterator i = lines.iterator(); i.hasNext(); ) {
144	LineString line = (LineString) i.next();
145	Coordinate[] pts = line.getCoordinates();
146	addLine(pts);
147	}
148	}
149
150	private void addLine(Coordinate[] pts)
151	{
152	for (int i = 1; i < pts.length; i++) {
153	LineSegment seg = new LineSegment(pts[i-1], pts[i]);
154	double min = Math.min(seg.p0.y, seg.p1.y);
155	double max = Math.max(seg.p0.y, seg.p1.y);
156	index.insert(min, max, seg);
157	}
158	}
159
160	public List query(double min, double max)
161	{
162	if (isEmpty)
163	return new ArrayList();
164
165	ArrayListVisitor visitor = new ArrayListVisitor();
166	index.query(min, max, visitor);
167	return visitor.getItems();
168	}
169
170	public void query(double min, double max, ItemVisitor visitor)
171	{
172	if (isEmpty)
173	return;
174	index.query(min, max, visitor);
175	}
176	}
177
178	}
179
180
181
182