001: /*
002: * The Unified Mapping Platform (JUMP) is an extensible, interactive GUI
003: * for visualizing and manipulating spatial features with geometry and attributes.
004: *
005: * Copyright (C) 2003 Vivid Solutions
006: *
007: * This program is free software; you can redistribute it and/or
008: * modify it under the terms of the GNU General Public License
009: * as published by the Free Software Foundation; either version 2
010: * of the License, or (at your option) any later version.
011: *
012: * This program is distributed in the hope that it will be useful,
013: * but WITHOUT ANY WARRANTY; without even the implied warranty of
014: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
015: * GNU General Public License for more details.
016: *
017: * You should have received a copy of the GNU General Public License
018: * along with this program; if not, write to the Free Software
019: * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
020: *
021: * For more information, contact:
022: *
023: * Vivid Solutions
024: * Suite #1A
025: * 2328 Government Street
026: * Victoria BC V8T 5G5
027: * Canada
028: *
029: * (250)385-6040
030: * www.vividsolutions.com
031: */
032:
033: package com.vividsolutions.jump.algorithm;
034:
035: import com.vividsolutions.jts.geom.*;
036: import com.vividsolutions.jump.geom.LineSegmentUtil;
037:
038: /**
039: * Implements algorithm for computing a distance metric
040: * which can be thought of as the "Vertex Hausdorff Distance".
041: * This is the Hausdorff distance restricted to vertices for
042: * one of the geometries.
043: * Also computes two points of the Geometries which are separated by the computed distance.
044: * <p>
045: * <b>NOTE: This algorithm does NOT compute the full Hausdorff distance correctly, but
046: * an approximation that is correct for a large subset of useful cases.
047: * One important part of this subset is Linestrings that are roughly parallel to each other,
048: * and roughly equal in length - just what is needed for line matching.
049: * </b>
050: */
051: public class VertexHausdorffDistance {
052:
053: public static double distance(Geometry g0, Geometry g1) {
054: VertexHausdorffDistance vhd = new VertexHausdorffDistance(g0,
055: g1);
056: return vhd.distance();
057: }
058:
059: private PointPairDistance ptDist = new PointPairDistance();
060:
061: public VertexHausdorffDistance(Geometry g0, Geometry g1) {
062: compute(g0, g1);
063: }
064:
065: public VertexHausdorffDistance(LineSegment seg0, LineSegment seg1) {
066: compute(seg0, seg1);
067: }
068:
069: public double distance() {
070: return ptDist.getDistance();
071: }
072:
073: public Coordinate[] getCoordinates() {
074: return ptDist.getCoordinates();
075: }
076:
077: private void compute(LineSegment seg0, LineSegment seg1) {
078: computeMaxPointDistance(seg0, seg1, ptDist);
079: computeMaxPointDistance(seg1, seg0, ptDist);
080: }
081:
082: /**
083: * Computes the maximum oriented distance between two line segments,
084: * as well as the point pair separated by that distance.
085: *
086: * @param seg0 the line segment containing the furthest point
087: * @param seg1 the line segment containing the closest point
088: * @param ptDist the point pair and distance to be updated
089: */
090: private void computeMaxPointDistance(LineSegment seg0,
091: LineSegment seg1, PointPairDistance ptDist) {
092: Coordinate closestPt0 = seg0.closestPoint(seg1.p0);
093: ptDist.setMaximum(closestPt0, seg1.p0);
094: Coordinate closestPt1 = seg0.closestPoint(seg1.p1);
095: ptDist.setMaximum(closestPt1, seg1.p1);
096: }
097:
098: private void compute(Geometry g0, Geometry g1) {
099: computeMaxPointDistance(g0, g1, ptDist);
100: computeMaxPointDistance(g1, g0, ptDist);
101: }
102:
103: private void computeMaxPointDistance(Geometry pointGeom,
104: Geometry geom, PointPairDistance ptDist) {
105: MaxPointDistanceFilter distFilter = new MaxPointDistanceFilter(
106: geom);
107: pointGeom.apply(distFilter);
108: ptDist.setMaximum(distFilter.getMaxPointDistance());
109: }
110:
111: public static class MaxPointDistanceFilter implements
112: CoordinateFilter {
113: private PointPairDistance maxPtDist = new PointPairDistance();
114: private PointPairDistance minPtDist = new PointPairDistance();
115: private EuclideanDistanceToPoint euclideanDist = new EuclideanDistanceToPoint();
116: private Geometry geom;
117:
118: public MaxPointDistanceFilter(Geometry geom) {
119: this .geom = geom;
120: }
121:
122: public void filter(Coordinate pt) {
123: minPtDist.initialize();
124: euclideanDist.computeDistance(geom, pt, minPtDist);
125: maxPtDist.setMaximum(minPtDist);
126: }
127:
128: public PointPairDistance getMaxPointDistance() {
129: return maxPtDist;
130: }
131: }
132: }
|