Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
A simplified polyline that has only enough line segments to accurately represent the original polyline.
//
// Copyright 2012 Frank A. Krueger
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
using System;
using System.Collections.Generic;
using System.Drawing;
namespace Praeclarum.Geometry
{
/// <summary>
/// A simplified polyline that has only enough line segments to
/// accurately represent the original polyline. This is very handy for reducing touch
/// strokes and other high-resolution input to only points that matter.
/// </summary>
/// <remarks>
/// The algorithm starts with the most simplfied version of the polyline: a
/// single line segment connecting the end points. It then recursively splits this
/// segment and all others, one at a time, until the accuracy requirement is met
/// or there's nothing left to split.
/// </remarks>
public class SimplifiedPolyline
{
public PointF[] Points { get; private set; }
public SimplifiedPolyline (PointF[] inputPolyline, float accuracy)
{
if (inputPolyline == null)
throw new ArgumentNullException ("inputPolyline");
if (inputPolyline.Length < 2)
throw new ArgumentException ("inputPolyline needs must have more than 1 point", "inputPolyline");
if (accuracy < 0)
throw new ArgumentException ("accuracy must be >= 0", "accuracy");
//
// Init
//
var segs = new List<Segment> {
new Segment (inputPolyline, 0, inputPolyline.Length),
};
var worstIndex = 0;
//
// Smooth
//
while (segs [worstIndex].CanSplit &&
segs [worstIndex].FarthestPointDistance > accuracy) {
var newSeg = segs [worstIndex].Split ();
segs.Insert (worstIndex + 1, newSeg);
worstIndex = FindWorstSegment (segs);
}
//
// Get the resulting polyline
//
var outputPolyline = new PointF [segs.Count + 1];
for (var i = 0; i < segs.Count; i++) {
outputPolyline [i] = segs [i].StartPoint;
}
outputPolyline [segs.Count] = segs [segs.Count - 1].EndPoint;
Points = outputPolyline;
}
static int FindWorstSegment (List<Segment> segs)
{
var worstIndex = 0;
var worstDistance = segs [worstIndex].FarthestPointDistance;
for (var i = 1; i < segs.Count; i++) {
if (segs [i].FarthestPointDistance > worstDistance) {
worstIndex = i;
worstDistance = segs [worstIndex].FarthestPointDistance;
}
}
return worstIndex;
}
class Segment
{
readonly PointF[] points;
readonly int startIndex;
int length;
int farthestPointIndex;
public float FarthestPointDistance { get; private set; }
public PointF StartPoint { get { return points [startIndex]; } }
public PointF EndPoint { get { return points [startIndex + length - 1]; } }
public Segment (PointF[] points, int startIndex, int length)
{
this.points = points;
this.startIndex = startIndex;
this.length = length;
FindFarthestPoint ();
}
public bool CanSplit { get { return length > 2; } }
public Segment Split ()
{
if (!CanSplit)
throw new InvalidOperationException ("Can't split, too few points");
var newSeg = new Segment (points, farthestPointIndex, (startIndex + length) - farthestPointIndex);
length = farthestPointIndex - startIndex + 1;
FindFarthestPoint ();
return newSeg;
}
void FindFarthestPoint ()
{
farthestPointIndex = startIndex;
FarthestPointDistance = 0;
var p1 = StartPoint;
var p2 = EndPoint;
var lastIndex = startIndex + length - 2;
for (var i = startIndex + 1; i <= lastIndex; i++) {
var d = DistanceToLineSegment (p1.X, p1.Y, p2.X, p2.Y, points [i].X, points [i].Y);
if (d > FarthestPointDistance) {
farthestPointIndex = i;
FarthestPointDistance = d;
}
}
}
public override string ToString ()
{
return string.Format ("{0} -> {1}", startIndex, startIndex + length - 1);
}
/// <summary>
/// http://local.wasp.uwa.edu.au/~pbourke/geometry/pointline/
/// </summary>
static float DistanceToLineSegment (float p1X, float p1Y, float p2X, float p2Y, float p3X, float p3Y)
{
var x21 = p2X - p1X;
var y21 = p2Y - p1Y;
var x31 = p3X - p1X;
var y31 = p3Y - p1Y;
var d = x21 * x21 + y21 * y21;
if (d == 0) {
return (float)Math.Sqrt (x31 * x31 + y31 * y31);
}
var u = (x31 * x21 + y31 * y21) / d;
if (u <= 0) {
return (float)Math.Sqrt (x31 * x31 + y31 * y31);
} else if (u >= 1) {
var x32 = p3X - p2X;
var y32 = p3Y - p2Y;
return (float)Math.Sqrt (x32 * x32 + y32 * y32);
} else {
var dx = x31 - u * x21;
var dy = y31 - u * y21;
return (float)Math.Sqrt (dx * dx + dy * dy);
}
}
}
}
}
@atheken

This comment has been minimized.

Copy link

commented Mar 23, 2013

Awesome, I actually implemented this algo for a MonoTouch app recently. For the sake of Google, this algorithm is known as the Ramer-Douglas-Peucker Algorithm (http://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm). Thanks for publishing a version in C#!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.