Thread: Re: [Algorithms] 2D Polygon Simplification
Brought to you by:
vexxed72
From: Conor S. <bor...@ya...> - 2007-12-29 12:49:44
|
You could use the "area" of an edge collapse as a metric (which in turn is the amount of area that is taken or added to your shape if the collapse occurred). A simple edge collapse having the area of a triangle (formed by the 2 original edges and the "collapsed" edge). Cheers, Conor ----- Original Message ---- From: Paul at Home <pa...@ru...> To: gda...@li... Sent: Saturday, December 29, 2007 8:06:20 PM Subject: [Algorithms] 2D Polygon Simplification I have a 2D outline of the world (literally, the Earth) and it's in monstrously high detail. I need to simplify it but I'm struggling for ideas. I've written my own edge collapse routine and it kinda works but I can't help but feel it should be a lot better. I'm wondering if there's a resource on the net for a standard algorithm or something ? I've searched but I can't find anything due to being swamped by tri-mesh algorithms that just aren't solving the same problem. The best results I've had whilst experimenting are just removing smaller edges first and putting one of the ends at the midpoint. Not a dot product in sight. This just implies that I'm not using corner sharpness the best way when I've tried that. When you want extreme simplification, the trivial "easy" answers I've tried just aren't cutting it. They don't preserve area well enough, nor general shape (even when I favour bend-acuteness over length). I think I need edge-collapse (over point collapse), but the "strength" calculation needs to take into account how bendy the adjoining corners are, combined with overal length of the edge and maybe some area calculation. Or something. Anyone ? Regards, Paul Johnson. www.rubicondev.com ____________________________________________________________________________________ Be a better friend, newshound, and know-it-all with Yahoo! Mobile. Try it now. http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ |
From: Bill B. <wb...@gm...> - 2007-12-29 20:16:50
|
On Dec 29, 2007 9:49 PM, Conor Stokes <bor...@ya...> wrote: > > You could use the "area" of an edge collapse as a metric (which in turn is > the amount of area that is taken or added to your shape if the collapse > occurred). A simple edge collapse having the area of a triangle (formed by > the 2 original edges and the "collapsed" edge). I have implemented something like this. In my case I also needed to ensure that the simplified boundary completely enclosed the original boundary, but if you don't need that, just using an area metric should work well, and be pretty easy to implement too. --bb |
From: Robin G. <rob...@gm...> - 2007-12-29 22:39:57
|
Another vote for the area preserving collapse - iteratively remove the vertex that changes the enclosed area the least. Strictly this requires closed loops. Another way of thinking about the problem is to imagine taking a sequence of four vertices and fitting a quadratic curve to them that passes through the end points. You are then free to pick any point on that fitted curve as an approximation to the two internal points you are replacing with a single one, according to whatever metric you want. Area preservation is a good quality to have, as is minimal approximation error to the original curve. The example of taking three points and losing the middle one is the same as fitting a linear curve through the end points and decimating the middle point. And by extension you can see taking more points into your approximation leads to cubic, quartic or higher "basis functions". I call them basis functions because this process is exactly what happens when you are compressing a 1D signal using a Wavelet Transform - you approximate a piece of the function with a curve that obeys certain rules, take a specific point on that fitted curve (usually the center point) and record only the difference between that approximated point and the original. The reverse of this decimation only requires us to add the differences to the current version of the curve to get a better approximation. So yes, there's a bit of precedence to your problem! - Robin Green. On Dec 29, 2007 9:49 PM, Conor Stokes <bor...@ya...> wrote: > > You could use the "area" of an edge collapse as a metric |
From: Paul at H. <pa...@ru...> - 2007-12-30 00:07:04
|
ok, that's enough votes for this one. I'll give it a bash. Thanks all. :) (Though I'm still surprised there isn't a definitive algorithm/webpage with all this on) Regards, Paul Johnson. www.rubicondev.com ----- Original Message ----- From: "Robin Green" <rob...@gm...> To: "Game Development Algorithms" <gda...@li...> Sent: Saturday, December 29, 2007 10:40 PM Subject: Re: [Algorithms] 2D Polygon Simplification > Another vote for the area preserving collapse - iteratively remove the > vertex that changes the enclosed area the least. Strictly this > requires closed loops. > > Another way of thinking about the problem is to imagine taking a > sequence of four vertices and fitting a quadratic curve to them that > passes through the end points. You are then free to pick any point on > that fitted curve as an approximation to the two internal points you > are replacing with a single one, according to whatever metric you > want. Area preservation is a good quality to have, as is minimal > approximation error to the original curve. The example of taking three > points and losing the middle one is the same as fitting a linear curve > through the end points and decimating the middle point. And by > extension you can see taking more points into your approximation leads > to cubic, quartic or higher "basis functions". > > I call them basis functions because this process is exactly what > happens when you are compressing a 1D signal using a Wavelet Transform > - you approximate a piece of the function with a curve that obeys > certain rules, take a specific point on that fitted curve (usually the > center point) and record only the difference between that approximated > point and the original. The reverse of this decimation only requires > us to add the differences to the current version of the curve to get a > better approximation. > > So yes, there's a bit of precedence to your problem! > > - Robin Green. > > > On Dec 29, 2007 9:49 PM, Conor Stokes <bor...@ya...> > wrote: >> >> You could use the "area" of an edge collapse as a metric > > ------------------------------------------------------------------------- > This SF.net email is sponsored by: Microsoft > Defy all challenges. Microsoft(R) Visual Studio 2005. > http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/ > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > > |