Offset Algorithm

[grg12]

Jack000: thank you for that paper - my previosu algorithm was much simplier (and faster) but could not generate multiple loops - at the end there was only one. New algorithm works better - but calculations take much much longer.

Larken: i'm using linked lists (std::list) to store primitives - most operations on chains involve inserting and deleting objects from container and resizing vector takes time.
"Chain inside chain" shuold be easy - create a infinite line starting from any node of "suspected chain" (direction of line is unimportant) and count how many times this line croses other chain - assuming that "other" chain is closed and does not intersect with "suspected" chain - when number of intersections is odd - "suspected" is inside "other"

Originally Posted by Larken If your origional chain is CW and you do an intesection check and then join all closed chains. The Ones to keep will all be CW and the gouging (bad) ones (to erase) will all be CCW.

Looks like i'm trying to reinvent the wheel Frankly speaking i started this project to give my brain some workout (you need something intersting to think of while coding (ctrl-c ctrl-v mostly) thousandth version of "that creative teaser animation") so i tried without looking at other's.

[Jack000]

to tell whether one chain is inside another, you could first detect whether the two intersect - if they do intersect, just return null or w/e, but if they don't intersect, choose one point on either chain and do a point in polygon. (if they don't intersect, either every point is inside or every point is outside)

here's an illustration of my offset method:



the butterfly was about 200ms for the offset, which is pretty good for flash/actionscript.

There are still some issues - because of the finite resolution of the bitmap, sometimes it leaves "stubbles", but it should be fairly easy to detect.

I'm squashing some bugs, but should be ready for a release soon

[Khalid]

awesome... Now i understand how the offset is made with the software..thanks for explanation

[jeff1000]

Nice pictures, how to fill area with bitmap? Do it works for pockets with islands?

[Jack000]

check out the open source forum, the app's been released :]

I'm using a feature of flash to generate the bitmap. Admittedly this is a bit of a hack, but I'm not smart enough to do it with voronoi diagrams..