sweep line intersections has anyone got experience ?

Klunk

I've been playing around with various sweepline algorithms for finding 2d polygon intersections, and everyone I've tried has missed an intersection or two/three/four.... but there doesn't seem to be any rhyme or reason (not that i've found to date) as to why e.g. .....

is it an elegant  but ultimately failed solution ? otherwise it's the n squared brute force solution

Klunk

think I know what going on with this version, it doesn't distinguish between closed and open poly lines  
fixed it

works out @ a max of 98  500 ish comparisons with the sweepline (plus a bit for some pre sort initiialization) vs 9604 with brute force
it's witch craft !!!

a self intersecting abomination

Eric Chadwick

Love seeing your work on this, fun stuff!

Klunk

thanks, lets say I enjoy a challenge I'm working on an efficient method of "rationalizing" any poly shapes/edge outlines etc so it doesn't break other tools (First rule of Tools, Artists break everything! ).... you could just union them all to get a "bounding" poly but then you can't have holes. Max sdk has a built in OrganizeCurves routine which works as expected 80% of the time and some other stuff I have is similar but different. 

Klunk

made some progress that I'm happy with.... top is "rationalised" to the bottom

though self intersection ( oooh er missus! ) is still a bugbear

Klunk

making some progress on self intersection.....

the bottom version result was seperated by hand to show the result most of my tools
don't mind touching polylines just overlapping and self intersecting

Klunk

think i'm almost there now....

the horror show top left can be made to work in a "sensible" way. there was some soul searching on whether a spline intersecting 2 other splines though wholly contained  within them is considered a hole of the 2 combined..... i thought yes.... but resolving that was a mind ****! It's always nice to know you've not been on a fools errand