Is there a .NET library or example code out there that is useful for optimizing points on a line or decimation?

I have a large set of datapoints (all 2D that represent a edges of a shape) where there exists many that all line up in straight lines a series of many points (pixels) I would like to optimize the data by removing the points that make up straight lines (same vector) and leave only the last two end points of the series to define the line and ignore all the points in b开发者_开发百科etween (decimation).

Line series that are strictly on X and Y axis of a grid presents one level of complexity. The second level is diagonal lines that when applied to a grid (i.e. pixels) some lines may need to be determined through interpolating a pattern. (i.e. 1 up 3 over, 1 up 4 over, 1 up 5 and so on represents a straight line)

I would like to leverage any existing libraries or example code snippets out there that might already exist instead of reinventing the wheel totally from scratch.

Any pointers, tips, code suggestions, algorithms, partial solutions, etc would be appreciated.

This is going to be a .NET project, but I am well versed in other languages as well (ruby, perl, python) so if such an example exists in similar languages, it would be useful to me.

Thanks

• Adding link to sample data set: http://pastie.org/1015421
• Adding a sample image to show the goal of the optimization / decimation

alt text http://www.streamline-ss.com/tmp/point_optimization.png

Updated:

• We were able to change the incoming data set to be optimized to be a unit-less grid/pixel location based data set from the original source instead of the interpolated unit based locations (to avoid the variances the calculated grid)
• The example of this input data set (unoptimized) is here http://pastie.org/1017486
• So far, I've been able to write a routine that will remove the duplicates, and remove any points that have the same x or same y as the previous point
• Need to find a way to identify reoccurring patterns and eliminate all but the end points of the beginning and end patterns - for straight line decimation.
• I still haven't found a library, class or code snippet out there where someone has already done this but it seems to me that this is not a new challenge and someone surely has invented this wheel

---

what about Douglas Peucker algorithm wikipedia NetTopologySuite has an implemnetation of it i have used it for simplifying GPX tracks

if you convert your data to a LineString then it is dead simple to use

GisSharpBlog.NetTopologySuite.Simplify.DouglasPeuckerLineSimplifier simplifyer = new GisSharpBlog.NetTopologySuite.Simplify.DouglasPeuckerLineSimplifier(lineString.Coordinates);
simplifyer.DistanceTolerance = 5;//some number that makes sense;
GeoAPI.Geometries.ILinearString simplifyedLineString = new GisSharpBlog.NetTopologySuite.Geometries.LineString(simplifyer.Simplify());

---

There is a really good GIS library called Net Topology Suite that has a lot of geometry type functions. This may cover the functionality you're looking for. It is LGPL licensed. I used it to do polygon intersections with much success.