Algorithm for reducing number of points (preserving topology)

Topics: Algorithms
Oct 11, 2010 at 9:05 AM


I have an incredibly large number of points for display on a world map, numbering in the millions, arranged into individual cells. The cells are anything from rectangular to very varied boundaries following a coastline. On the boundaries of these cells, even on the straight lines, are an insane number of extra points which are completely unnecessary - SharpMap takes a long time to load them and a large time to re-draw the map every time it is scrolled/zoomed. I am sure these points can be reduced by at least 10x and still retain the overall topology of these cells. I am talking here about some kind of pre-processing before the data is even delivered to SharpMap but thought that this would still be the best place to ask.

I have been trying out various algorithms - the most promising so far has been a combination of my own tweaks (stepping through the points in turn and if either the lat or long is equal to the previous one, the new point is removed - this helps with any rectangular elements of a cell) and the Douglas-Peucker algorithm but the latter is not good at preserving topology. Silly things happen like the corner points of cells being chopped off leaving me with various cells with missing corners.

My results when googling are clouded by allsorts of unhelpful results regarding either splitting polygons for 3D graphics optimisation or the mathematical definition of topology - really struggling to even know where to look here.

Any help or suggestions would be greatly appreciated.

Oct 11, 2010 at 9:24 AM

Hello fredthefish,

if you take the latest NetTopologySuite assembly from you should have a TopologyPreservingSimplifier class at hand.

Hth FObermaier

Oct 12, 2010 at 11:29 AM

Thanks for the pointer - looks useful! Don't suppose you know of an example of how to load a bunch of lat/long's in as a polygon, simplify, and get the new lat/long's out?

Oct 12, 2010 at 12:49 PM

What might be easier - would there be a way of just running this on a SharpMap.Geometries.LineString ?

Oct 13, 2010 at 10:51 AM

Sorry, I have no code present, you may want to ask in the NetTopologySuite group.

hth FObermaier