Class FacetSequence

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.distance;
14
15	import org.locationtech.jts.algorithm.Distance;
16	import org.locationtech.jts.geom.Coordinate;
17	import org.locationtech.jts.geom.CoordinateSequence;
18	import org.locationtech.jts.geom.Envelope;
19	import org.locationtech.jts.geom.Geometry;
20	import org.locationtech.jts.geom.LineSegment;
21
22	/**
23	* Represents a sequence of facets (points or line segments)
24	* of a {@link Geometry}
25	* specified by a subsequence of a {@link CoordinateSequence}.
26	*
27	* @author Martin Davis
28	*
29	*/
30	public class FacetSequence
31	{
32	private Geometry geom = null;
33	private CoordinateSequence pts;
34	private int start;
35	private int end;
36
37	/**
38	* Creates a new sequence of facets based on a {@link CoordinateSequence}
39	* contained in the given {@link Geometry}.
40	*
41	* @param geom the geometry containing the facets
42	* @param pts the sequence containing the facet points
43	* @param start the index of the start point
44	* @param end the index of the end point + 1
45	*/
46	public FacetSequence(Geometry geom, CoordinateSequence pts, int start, int end)
47	{
48	this.geom = geom;
49	this.pts = pts;
50	this.start = start;
51	this.end = end;
52	}
53
54	/**
55	* Creates a new sequence of facets based on a {@link CoordinateSequence}.
56	*
57	* @param pts the sequence containing the facet points
58	* @param start the index of the start point
59	* @param end the index of the end point + 1
60	*/
61	public FacetSequence(CoordinateSequence pts, int start, int end)
62	{
63	this.pts = pts;
64	this.start = start;
65	this.end = end;
66	}
67
68	/**
69	* Creates a new sequence for a single point from a {@link CoordinateSequence}.
70	*
71	* @param pts the sequence containing the facet point
72	* @param start the index of the point
73	*/
74	public FacetSequence(CoordinateSequence pts, int start)
75	{
76	this.pts = pts;
77	this.start = start;
78	this.end = start + 1;
79	}
80
81	public Envelope getEnvelope()
82	{
83	Envelope env = new Envelope();
84	for (int i = start; i < end; i++) {
85	env.expandToInclude(pts.getX(i), pts.getY(i));
86	}
87	return env;
88	}
89
90	public int size()
91	{
92	return end - start;
93	}
94
95	public Coordinate getCoordinate(int index)
96	{
97	return pts.getCoordinate(start + index);
98	}
99
100	public boolean isPoint()
101	{
102	return end - start == 1;
103	}
104
105	/**
106	* Computes the distance between this and another
107	* <tt>FacetSequence</tt>.
108	*
109	* @param facetSeq the sequence to compute the distance to
110	* @return the minimum distance between the sequences
111	*/
112	public double distance(FacetSequence facetSeq)
113	{
114	boolean isPoint = isPoint();
115	boolean isPointOther = facetSeq.isPoint();
116	double distance;
117
118	if (isPoint && isPointOther) {
119	Coordinate pt = pts.getCoordinate(start);
120	Coordinate seqPt = facetSeq.pts.getCoordinate(facetSeq.start);
121	distance = pt.distance(seqPt);
122	}
123	else if (isPoint) {
124	Coordinate pt = pts.getCoordinate(start);
125	distance = computeDistancePointLine(pt, facetSeq, null);
126	}
127	else if (isPointOther) {
128	Coordinate seqPt = facetSeq.pts.getCoordinate(facetSeq.start);
129	distance = computeDistancePointLine(seqPt, this, null);
130	}
131	else {
132	distance = computeDistanceLineLine(facetSeq, null);
133	}
134	return distance;
135	}
136
137	/**
138	* Computes the locations of the nearest points between this sequence
139	* and another sequence.
140	* The locations are presented in the same order as the input sequences.
141	*
142	* @return a pair of {@link GeometryLocation}s for the nearest points
143	*/
144	public GeometryLocation[] nearestLocations(FacetSequence facetSeq)
145	{
146	boolean isPoint = isPoint();
147	boolean isPointOther = facetSeq.isPoint();
148	GeometryLocation[] locs = new GeometryLocation[2];
149
150	if (isPoint && isPointOther) {
151	Coordinate pt = pts.getCoordinate(start);
152	Coordinate seqPt = facetSeq.pts.getCoordinate(facetSeq.start);
153	locs[0] = new GeometryLocation(geom, start, new Coordinate(pt));
154	locs[1] = new GeometryLocation(facetSeq.geom, facetSeq.start, new Coordinate(seqPt));
155	}
156	else if (isPoint) {
157	Coordinate pt = pts.getCoordinate(start);
158	computeDistancePointLine(pt, facetSeq, locs);
159	}
160	else if (isPointOther) {
161	Coordinate seqPt = facetSeq.pts.getCoordinate(facetSeq.start);
162	computeDistancePointLine(seqPt, this, locs);
163	// unflip the locations
164	GeometryLocation tmp = locs[0];
165	locs[0] = locs[1];
166	locs[1] = tmp;
167	}
168	else {
169	computeDistanceLineLine(facetSeq, locs);
170	}
171	return locs;
172	}
173
174	private double computeDistanceLineLine(FacetSequence facetSeq, GeometryLocation[] locs)
175	{
176	// both linear - compute minimum segment-segment distance
177	double minDistance = Double.MAX_VALUE;
178
179	for (int i = start; i < end - 1; i++) {
180	Coordinate p0 = pts.getCoordinate(i);
181	Coordinate p1 = pts.getCoordinate(i + 1);
182	for (int j = facetSeq.start; j < facetSeq.end - 1; j++) {
183	Coordinate q0 = facetSeq.pts.getCoordinate(j);
184	Coordinate q1 = facetSeq.pts.getCoordinate(j + 1);
185
186	double dist = Distance.segmentToSegment(p0, p1, q0, q1);
187	if (dist < minDistance) {
188	minDistance = dist;
189	if (locs != null) updateNearestLocationsLineLine(i, p0, p1, facetSeq, j, q0, q1, locs);
190	if (minDistance <= 0.0) return minDistance;
191	}
192	}
193	}
194	return minDistance;
195	}
196
197	private void updateNearestLocationsLineLine(int i, Coordinate p0, Coordinate p1, FacetSequence facetSeq, int j,
198	Coordinate q0, Coordinate q1, GeometryLocation[] locs) {
199	LineSegment seg0 = new LineSegment(p0, p1);
200	LineSegment seg1 = new LineSegment(q0, q1);
201	Coordinate[] closestPt = seg0.closestPoints(seg1);
202	locs[0] = new GeometryLocation(geom, i, new Coordinate(closestPt[0]));
203	locs[1] = new GeometryLocation(facetSeq.geom, j, new Coordinate(closestPt[1]));
204	}
205
206	private double computeDistancePointLine(Coordinate pt, FacetSequence facetSeq, GeometryLocation[] locs)
207	{
208	double minDistance = Double.MAX_VALUE;
209
210	for (int i = facetSeq.start; i < facetSeq.end - 1; i++) {
211	Coordinate q0 = facetSeq.pts.getCoordinate(i);
212	Coordinate q1 = facetSeq.pts.getCoordinate(i + 1);
213	double dist = Distance.pointToSegment(pt, q0, q1);
214	if (dist < minDistance) {
215	minDistance = dist;
216	if (locs != null) updateNearestLocationsPointLine(pt, facetSeq, i, q0, q1, locs);
217	if (minDistance <= 0.0) return minDistance;
218	}
219	}
220	return minDistance;
221	}
222
223	private void updateNearestLocationsPointLine(Coordinate pt,
224	FacetSequence facetSeq, int i, Coordinate q0, Coordinate q1,
225	GeometryLocation[] locs) {
226	locs[0] = new GeometryLocation(geom, start, new Coordinate(pt));
227	LineSegment seg = new LineSegment(q0, q1);
228	Coordinate segClosestPoint = seg.closestPoint(pt);
229	locs[1] = new GeometryLocation(facetSeq.geom, i, new Coordinate(segClosestPoint));
230	}
231
232	public String toString()
233	{
234	StringBuffer buf = new StringBuffer();
235	buf.append("LINESTRING ( ");
236	Coordinate p = new Coordinate();
237	for (int i = start; i < end; i++) {
238	if (i > start)
239	buf.append(", ");
240	pts.getCoordinate(i, p);
241	buf.append(p.x + " " + p.y);
242	}
243	buf.append(" )");
244	return buf.toString();
245	}
246	}
247