IndexedFacetDistance.java
/*
* Copyright (c) 2016 Martin Davis.
*
* All rights reserved. This program and the accompanying materials
* are made available under the terms of the Eclipse Public License 2.0
* and Eclipse Distribution License v. 1.0 which accompanies this distribution.
* The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
* and the Eclipse Distribution License is available at
*
* http://www.eclipse.org/org/documents/edl-v10.php.
*/
package org.locationtech.jts.operation.distance;
import org.locationtech.jts.geom.Coordinate;
import org.locationtech.jts.geom.Geometry;
import org.locationtech.jts.geom.Lineal;
import org.locationtech.jts.geom.Polygonal;
import org.locationtech.jts.geom.Puntal;
import org.locationtech.jts.index.strtree.ItemBoundable;
import org.locationtech.jts.index.strtree.ItemDistance;
import org.locationtech.jts.index.strtree.STRtree;
/**
* Computes the distance between the facets (segments and vertices)
* of two {@link Geometry}s
* using a Branch-and-Bound algorithm.
* The Branch-and-Bound algorithm operates over a
* traversal of R-trees built
* on the target and the query geometries.
* <p>
* This approach provides the following benefits:
* <ul>
* <li>Performance is dramatically improved due to the use of the
* R-tree index
* and the pruning due to the Branch-and-Bound approach
* <li>The spatial index on the target geometry is cached
* which allow reuse in an repeated query situation.
* </ul>
* Using this technique is usually much more performant
* than using the brute-force {@link Geometry#distance(Geometry)}
* when one or both input geometries are large,
* or when evaluating many distance computations against
* a single geometry.
* <p>
* This class is thread-safe.
*
* @author Martin Davis
*
*/
public class IndexedFacetDistance
{
private static final FacetSequenceDistance FACET_SEQ_DIST = new FacetSequenceDistance();
/**
* Computes the distance between facets of two geometries.
* <p>
* For geometries with many segments or points,
* this can be faster than using a simple distance
* algorithm.
*
* @param g1 a geometry
* @param g2 a geometry
* @return the distance between facets of the geometries
*/
public static double distance(Geometry g1, Geometry g2)
{
IndexedFacetDistance dist = new IndexedFacetDistance(g1);
return dist.distance(g2);
}
/**
* Tests whether the facets of two geometries lie within a given distance.
*
* @param g1 a geometry
* @param g2 a geometry
* @param distance the distance limit
* @return true if two facets lie with the given distance
*/
public static boolean isWithinDistance(Geometry g1, Geometry g2, double distance) {
IndexedFacetDistance dist = new IndexedFacetDistance(g1);
return dist.isWithinDistance(g2, distance);
}
/**
* Computes the nearest points of the facets of two geometries.
*
* @param g1 a geometry
* @param g2 a geometry
* @return the nearest points on the facets of the geometries
*/
public static Coordinate[] nearestPoints(Geometry g1, Geometry g2) {
IndexedFacetDistance dist = new IndexedFacetDistance(g1);
return dist.nearestPoints(g2);
}
private STRtree cachedTree;
private Geometry baseGeometry;
/**
* Creates a new distance-finding instance for a given target {@link Geometry}.
* <p>
* Distances will be computed to all facets of the input geometry.
* The facets of the geometry are the discrete segments and points
* contained in its components.
* In the case of {@link Lineal} and {@link Puntal} inputs,
* this is equivalent to computing the conventional distance.
* In the case of {@link Polygonal} inputs, this is equivalent
* to computing the distance to the polygon boundaries.
*
* @param geom a Geometry, which may be of any type.
*/
public IndexedFacetDistance(Geometry geom) {
this.baseGeometry = geom;
cachedTree = FacetSequenceTreeBuilder.build(geom);
}
/**
* Computes the distance from the base geometry to
* the given geometry.
*
* @param g the geometry to compute the distance to
*
* @return the computed distance
*/
public double distance(Geometry g)
{
STRtree tree2 = FacetSequenceTreeBuilder.build(g);
Object[] obj = cachedTree.nearestNeighbour(tree2,
FACET_SEQ_DIST);
FacetSequence fs1 = (FacetSequence) obj[0];
FacetSequence fs2 = (FacetSequence) obj[1];
return fs1.distance(fs2);
}
/**
* Computes the nearest locations on the base geometry
* and the given geometry.
*
* @param g the geometry to compute the nearest location to
* @return the nearest locations
*/
public GeometryLocation[] nearestLocations(Geometry g)
{
STRtree tree2 = FacetSequenceTreeBuilder.build(g);
Object[] obj = cachedTree.nearestNeighbour(tree2,
FACET_SEQ_DIST);
FacetSequence fs1 = (FacetSequence) obj[0];
FacetSequence fs2 = (FacetSequence) obj[1];
return fs1.nearestLocations(fs2);
}
/**
* Compute the nearest locations on the target geometry
* and the given geometry.
*
* @param g the geometry to compute the nearest point to
* @return the nearest points
*/
public Coordinate[] nearestPoints(Geometry g) {
GeometryLocation[] minDistanceLocation = nearestLocations(g);
Coordinate[] nearestPts = toPoints(minDistanceLocation);
return nearestPts;
}
private static Coordinate[] toPoints(GeometryLocation[] locations) {
if (locations == null)
return null;
Coordinate[] nearestPts = new Coordinate[] {
locations[0].getCoordinate(),
locations[1].getCoordinate() };
return nearestPts;
}
/**
* Tests whether the base geometry lies within
* a specified distance of the given geometry.
*
* @param g the geometry to test
* @param maxDistance the maximum distance to test
* @return true if the geometry lies with the specified distance
*/
public boolean isWithinDistance(Geometry g, double maxDistance) {
// short-ciruit check
double envDist = baseGeometry.getEnvelopeInternal().distance(g.getEnvelopeInternal());
if (envDist > maxDistance)
return false;
STRtree tree2 = FacetSequenceTreeBuilder.build(g);
return cachedTree.isWithinDistance(tree2,
FACET_SEQ_DIST, maxDistance);
}
private static class FacetSequenceDistance
implements ItemDistance
{
public double distance(ItemBoundable item1, ItemBoundable item2) {
FacetSequence fs1 = (FacetSequence) item1.getItem();
FacetSequence fs2 = (FacetSequence) item2.getItem();
return fs1.distance(fs2);
}
}
}