com.mizar.geometry
Class DouglasPeucker

java.lang.Object
  extended by com.mizar.geometry.DouglasPeucker

public class DouglasPeucker
extends java.lang.Object

When handling geo-spatial data it is not uncommon to be forced to work with polylines and polygons that contain far more vertices than is appropriate or acceptable for the application. However, it may be unacceptable to correct that problem at the source by simplifying the original data. It may be that the original data is not within the application's control or the simplification might be required for a specific purpose relative to the scale of an operation. An example of this might be the creation of a significantly simplified object for the purpose of visualization or highlighting a geometry. It would not make sense to render a 1500 vertex polygon to Well Known Text (WKT) format, send that large object to a client browser, and to re-render that in JavaScript when, for the purposes of highlighting a polygon, a 150 vertex polygon is indistinguishable from the original.

This class provides methods to simplify or reduce 2D vector data using the well known Douglas-Peucker algorithm.

From http://en.wikipedia.org/wiki/Ramer-Douglas-Peucker_algorithm

The starting curve is an ordered set of points or lines and the distance dimension ? > 0. The original (unsmoothed) curve is shown in 0 and the final output curve is shown in blue on row 4.

The algorithm recursively divides the line. Initially it is given all the points between the first and last point. It automatically marks the first and last point to be kept. It then finds the point that is furthest from the line segment with the first and last points as end points (this point is obviously furthest on the curve from the approximating line segment between the end points). If the point is closer than ? to the line segment then any points not currently marked to keep can be discarded without the smoothed curve being worse than ?.

If the point furthest from the line segment is greater than ? from the approximation then that point must be kept. The algorithm recursively calls itself with the first point and the worst point and then with the worst point and the last point (which includes marking the worst point being marked as kept). When the recursion is completed a new output curve can be generated consisting of all (and only) those points that have been marked as kept.


Constructor Summary
DouglasPeucker()
           
 
Method Summary
static java.lang.Double perpendicularDistance(XY point1, XY point2, XY point)
           
static double[] reduce(double[] points, double tolerance)
           
static java.util.List<XY> reduce(java.util.List<XY> points, java.lang.Double tolerance)
          The method uses the Douglas Peucker algorithim to reduce the number of points.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

DouglasPeucker

public DouglasPeucker()
Method Detail

reduce

public static double[] reduce(double[] points,
                              double tolerance)
Parameters:
points -
tolerance -
Returns:

reduce

public static java.util.List<XY> reduce(java.util.List<XY> points,
                                        java.lang.Double tolerance)
The method uses the Douglas Peucker algorithim to reduce the number of points.

Parameters:
points -
tolerance -
Returns:

perpendicularDistance

public static java.lang.Double perpendicularDistance(XY point1,
                                                     XY point2,
                                                     XY point)
Parameters:
point1 -
point2 -
point -
Returns: