7 ms·

Map Simplification with Visvalingam's Algorithm

118 points by jashkenas 14y ago

andrewcooke 14y ago
can anyone clarify "There is no guarantee that removing a point increases the area of the adjacent triangles; thus, the algorithm considers the effective area as the larger of the associated triangle and the previously-removed triangle" - it does't appear in the original paper (afaict) which seems to emphasise that the method is point-based (implying no such "memory"). and i can't see why it's needed. it's clearly there in the source, but i don't understand the comment there, either. what am i missing?! (i understand the lack of a guarantee of increasing area - what i don't understand why the algorithm should "care"; once the point is gone, it is gone...).
- mbostock 14y ago
  The line from the original paper is in section 3.3: "If its calculated area is less than that of the last point to be eliminated, use the latter's area instead. (This ensures that the current point cannot be eliminated without eliminating previously eliminated points.)"
  - andrewcooke 14y ago
    ah, thanks. and i think i understand now - it doesn't affect filtering, but it makes the precalculated list have a monotonic value that can be used to select a "degree of smoothing". maybe.
wcarey 14y ago
This is a surprisingly different algorithm from Douglas-Ramer-Peucker. Visvalingam's algorithm gradually removes detail, while Peucker gradually restores removed detail. I'm really curious, too, how Visvalingam performs when the variance of the heights of the triangles is large. Intuitively, it seems like it'd be much more aggressive than Peucker about removing spikes in data, which, depending on what you were aiming at, could be good or bad. Imagine processing a polyline whose coordinates are: [0,0],[4,2],[8,0],[9,-9],[10,0],[14,1],[18,0] Peucker would preserve [9,-9] until very last. It seems like Visvalingam would remove that relatively early. edit: Either way, it's a nice algorithm to add to the quiver.
mbostock 14y ago
The source code is here, if you're interested: http://bost.ocks.org/mike/simplify/simplify.js http://bost.ocks.org/mike/simplify/simplify.js I'll probably package it up as a Node module so that it's easy to enable dynamic simplification of GeoJSON files. (A more efficient representation of shapes would also be helpful, though I like the convenience of plain text.) Or possibly a D3 plugin; it might be useful to extend the d3.geo.path shape generator to support more efficient dynamic filtering of points.
- hadley 14y ago
  Have you experimented with topologically consistent simplification? In my experience, that's the hard part - otherwise when simplifying (e.g.) state borders, the borders no longer match up.
  - mbostock 14y ago
    No, but that's next on my list! I'm familiar with at least one approach—identify borders shared by multiple features, simplify those independently, then stitch everything back together. I'm curious as to whether you can identify shared points and then use the average area of the associated triangles to prioritize removal.
    - cpher 14y ago
      I would be impressed to see an implementation of this. Topology is absolutely critical for serious GIS applications. Of course, ESRI makes it looks easy within their software, but I haven't seen what a basic algorithm looks like for this task. Good luck!
    - regularfry 14y ago
      It seems a superficially similar problem to 3d mesh reduction.
grandalf 14y ago
Where's Michigan? I'd be curious how the algorithm handled a shape like that.
- mbostock 14y ago
  These are cultural vectors, and so the sovereign territory includes the Great Lakes. Though, come to think of it, I should have picked the physical vectors if I wanted to stick to the coastline paradox theme!
  - grandalf 14y ago
    Interesting. I'll have to read more about the nuances of the algorithm.
tshadwell 14y ago
It is strange to try to notice the subtle changes of an algorithm that tries to minimise visual change as much as possible.
uuilly 14y ago
I wrote an implementation of this for this project: http://vimeo.com/uuorld http://vimeo.com/uuorld It's MUCH harder if you want adjacent borders to line up w/o gaps. You have to find all shared verts, run the smoothing algo on them, do the same for the coastlines / islands and then put all the pieces back together. I think 10% of my code was cleaning dirty data (removing duplicate points, detecting and fixing self intersection) 80% of my code was breaking everything up and putting it back together and 10% was the Visvalingam / Whyatt algo. The biggest time sink was dealing w/ messy data. Between countries, states, counties, zip codes, neighborhoods etc, we hit A LOT of crappy corner cases. If anyone else is endeavoring to do the same, contact me and I can probably save you a week of work.
- whiskers 14y ago
  Willy, I've tried e-mailing you through your about.me site, but it seems to get stuck on "Sending..." (and showing the spinner). The message I sent was: "I'd be very interested in any data you might have of this type (to overlay on a 3D model of Earth I'm building for a flight tracking project). What data do you have?" If you could respond via the address in my profile I'd be most grateful!
  - uuilly 14y ago
    Willy dot Pell at gmail dot com
ubasu 14y ago
Of course, I am sure many realise that this is applicable to visualising anything of a fractal nature, e.g. plotting stock price history at various zoom levels.
JonnieCache 14y ago
This is used to great effect with the Alchemy software synthesizer's "Detail" knob, allowing you to edit sounds with surgical precision or to make broad strokes. Hand-editing additive sounds is almost impossible without it. Alchemy in general is a jaw dropping piece of kit. It would give the UX types here a seizure though...
vog 14y ago
This is a great alternative to Ramer-Douglas-Peucker. However, it is not quite what I need for my application (where I'm still searching for a good algorithm, maybe I have to develop my own). The problem is that the area always shrinks (for a convex curve). This is simply because all those polygon simplifiers work by selecting a subset of the points, and removing points (from a convex curve) means that you always "cut corners". For my application, this is totally undesirable. I'm starting with a convex polygon, and the simplified polygon should fully enclose the original polygon. Thus, the simplified polygon has to consist of points outside the original polygon. Is there any existing algorithm which accomplishes that? That is, which adds to the (convex) polygon rather than removing from it?
- 7952 14y ago
  Try adding addittional points or even smoothing before running the simplification algorithm.
- bazzargh 14y ago
  Given segments AB BC CD such that the angle between AC and CD is less than 180 degrees, add the candidate point E where AB CD meet when extended. This is always outside a convex polygon. Choose the next candidate to minimize the area of BEC. The resulting polygon is also convex. Iterate. Once you reach a rectangle or a triangle there will be no more candidates.
  - vog 14y ago
    Nice to see that others have the same ideas! I also thought about that option at first, but this adds too much when the angle between AB and CD is small. So my current approach is to take ABCDE and replace BC and CD with that of the (infinitely many) tangents on C where the resulting area is minimal. Then B' is the intersection of the ray AB with that tangent. D' is corresponding intersection with ray ED. ABCDE is then replaced with AB'D'E (i.e. B->B', C removed, D->D'). Although I didn't yet do the math to find the optimal tangent on each point, it shouldn't be too hard to find that one. Note that the simple ABCD approach is a degenerate case from this new approach: You just always choose the tangent to be BC. So I expect the new approach to produce strictly better results. However, is there anything more elaborate than that? I don't belive I'm the first one who formulates that problem...
davidjohnstone 14y ago
I've had an interest in polyline simplification for the last couple of weeks, and I eventually stumbled upon the Ramer–Douglas–Peucker algorithm and a JavaScript [1] and Python [2] implementation of it. However, one thing it doesn't do (and Visvalingam’s algorithm doesn't either) is remove loops. In many cases you wouldn't want that, but sometimes you just want to draw a line that looks right, and being able to remove redundant parts of the polyline would be very helpful. For example, in the case where you have a GPS track of a run where you run to a nearby oval, do ten laps, and then run home, and you want the simplest polyline that looks right. 1: https://github.com/mourner/simplify-js https://github.com/mourner/simplify-js 2: https://github.com/omarestrella/simplify.py/ https://github.com/omarestrella/simplify.py/

118 points by jashkenas 14y ago

can anyone clarify "There is no guarantee that removing a point increases the area of the adjacent triangles; thus, the algorithm considers the effective area as the larger of the associated triangle and the previously-removed triangle" - it does't appear in the original paper (afaict) which seems to emphasise that the method is point-based (implying no such "memory"). and i can't see why it's needed. it's clearly there in the source, but i don't understand the comment there, either. what am i missing?! (i understand the lack of a guarantee of increasing area - what i don't understand why the algorithm should "care"; once the point is gone, it is gone...).

mbostock 14y ago
The line from the original paper is in section 3.3: "If its calculated area is less than that of the last point to be eliminated, use the latter's area instead. (This ensures that the current point cannot be eliminated without eliminating previously eliminated points.)"
- andrewcooke 14y ago
  ah, thanks. and i think i understand now - it doesn't affect filtering, but it makes the precalculated list have a monotonic value that can be used to select a "degree of smoothing". maybe.

wcarey 14y ago

This is a surprisingly different algorithm from Douglas-Ramer-Peucker. Visvalingam's algorithm gradually removes detail, while Peucker gradually restores removed detail. I'm really curious, too, how Visvalingam performs when the variance of the heights of the triangles is large. Intuitively, it seems like it'd be much more aggressive than Peucker about removing spikes in data, which, depending on what you were aiming at, could be good or bad. Imagine processing a polyline whose coordinates are: [0,0],[4,2],[8,0],[9,-9],[10,0],[14,1],[18,0] Peucker would preserve [9,-9] until very last. It seems like Visvalingam would remove that relatively early. edit: Either way, it's a nice algorithm to add to the quiver.

mbostock 14y ago

The source code is here, if you're interested: http://bost.ocks.org/mike/simplify/simplify.js http://bost.ocks.org/mike/simplify/simplify.js I'll probably package it up as a Node module so that it's easy to enable dynamic simplification of GeoJSON files. (A more efficient representation of shapes would also be helpful, though I like the convenience of plain text.) Or possibly a D3 plugin; it might be useful to extend the d3.geo.path shape generator to support more efficient dynamic filtering of points.

hadley 14y ago
Have you experimented with topologically consistent simplification? In my experience, that's the hard part - otherwise when simplifying (e.g.) state borders, the borders no longer match up.
- mbostock 14y ago
  No, but that's next on my list! I'm familiar with at least one approach—identify borders shared by multiple features, simplify those independently, then stitch everything back together. I'm curious as to whether you can identify shared points and then use the average area of the associated triangles to prioritize removal.
  - cpher 14y ago
    I would be impressed to see an implementation of this. Topology is absolutely critical for serious GIS applications. Of course, ESRI makes it looks easy within their software, but I haven't seen what a basic algorithm looks like for this task. Good luck!
  - regularfry 14y ago
    It seems a superficially similar problem to 3d mesh reduction.

grandalf 14y ago

Where's Michigan? I'd be curious how the algorithm handled a shape like that.

mbostock 14y ago
These are cultural vectors, and so the sovereign territory includes the Great Lakes. Though, come to think of it, I should have picked the physical vectors if I wanted to stick to the coastline paradox theme!
- grandalf 14y ago
  Interesting. I'll have to read more about the nuances of the algorithm.

tshadwell 14y ago

It is strange to try to notice the subtle changes of an algorithm that tries to minimise visual change as much as possible.

uuilly 14y ago

I wrote an implementation of this for this project: http://vimeo.com/uuorld http://vimeo.com/uuorld It's MUCH harder if you want adjacent borders to line up w/o gaps. You have to find all shared verts, run the smoothing algo on them, do the same for the coastlines / islands and then put all the pieces back together. I think 10% of my code was cleaning dirty data (removing duplicate points, detecting and fixing self intersection) 80% of my code was breaking everything up and putting it back together and 10% was the Visvalingam / Whyatt algo. The biggest time sink was dealing w/ messy data. Between countries, states, counties, zip codes, neighborhoods etc, we hit A LOT of crappy corner cases. If anyone else is endeavoring to do the same, contact me and I can probably save you a week of work.

whiskers 14y ago
Willy, I've tried e-mailing you through your about.me site, but it seems to get stuck on "Sending..." (and showing the spinner). The message I sent was: "I'd be very interested in any data you might have of this type (to overlay on a 3D model of Earth I'm building for a flight tracking project). What data do you have?" If you could respond via the address in my profile I'd be most grateful!
- uuilly 14y ago
  Willy dot Pell at gmail dot com

ubasu 14y ago

Of course, I am sure many realise that this is applicable to visualising anything of a fractal nature, e.g. plotting stock price history at various zoom levels.

JonnieCache 14y ago

This is used to great effect with the Alchemy software synthesizer's "Detail" knob, allowing you to edit sounds with surgical precision or to make broad strokes. Hand-editing additive sounds is almost impossible without it. Alchemy in general is a jaw dropping piece of kit. It would give the UX types here a seizure though...

vog 14y ago

This is a great alternative to Ramer-Douglas-Peucker. However, it is not quite what I need for my application (where I'm still searching for a good algorithm, maybe I have to develop my own). The problem is that the area always shrinks (for a convex curve). This is simply because all those polygon simplifiers work by selecting a subset of the points, and removing points (from a convex curve) means that you always "cut corners". For my application, this is totally undesirable. I'm starting with a convex polygon, and the simplified polygon should fully enclose the original polygon. Thus, the simplified polygon has to consist of points outside the original polygon. Is there any existing algorithm which accomplishes that? That is, which adds to the (convex) polygon rather than removing from it?

7952 14y ago
Try adding addittional points or even smoothing before running the simplification algorithm.
bazzargh 14y ago
Given segments AB BC CD such that the angle between AC and CD is less than 180 degrees, add the candidate point E where AB CD meet when extended. This is always outside a convex polygon. Choose the next candidate to minimize the area of BEC. The resulting polygon is also convex. Iterate. Once you reach a rectangle or a triangle there will be no more candidates.
- vog 14y ago
  Nice to see that others have the same ideas! I also thought about that option at first, but this adds too much when the angle between AB and CD is small. So my current approach is to take ABCDE and replace BC and CD with that of the (infinitely many) tangents on C where the resulting area is minimal. Then B' is the intersection of the ray AB with that tangent. D' is corresponding intersection with ray ED. ABCDE is then replaced with AB'D'E (i.e. B->B', C removed, D->D'). Although I didn't yet do the math to find the optimal tangent on each point, it shouldn't be too hard to find that one. Note that the simple ABCD approach is a degenerate case from this new approach: You just always choose the tangent to be BC. So I expect the new approach to produce strictly better results. However, is there anything more elaborate than that? I don't belive I'm the first one who formulates that problem...

davidjohnstone 14y ago

I've had an interest in polyline simplification for the last couple of weeks, and I eventually stumbled upon the Ramer–Douglas–Peucker algorithm and a JavaScript [1] and Python [2] implementation of it. However, one thing it doesn't do (and Visvalingam’s algorithm doesn't either) is remove loops. In many cases you wouldn't want that, but sometimes you just want to draw a line that looks right, and being able to remove redundant parts of the polyline would be very helpful. For example, in the case where you have a GPS track of a run where you run to a nearby oval, do ten laps, and then run home, and you want the simplest polyline that looks right. 1: https://github.com/mourner/simplify-js https://github.com/mourner/simplify-js 2: https://github.com/omarestrella/simplify.py/ https://github.com/omarestrella/simplify.py/