search

mapbox / wagyu

A general library for geometry operations of union, intersections, difference, and xor
Other
166 stars 33 forks source link

Intersection and Snap Rounding Documentation #42

Open flippmoke opened 8 years ago

flippmoke commented 8 years ago

It is not intuitive right away how the intersection processing and the snap rounding is done in the code. Documentation should be added and put in the /docs directory of the repository.

MaheshNaikM commented 8 years ago

yes , please ..then i can play around with your code .I normally do area comparion with a debugged murta clipper I have which uses double precision and i also have a arbitrary precion super slow version of the same.Only problem is it is also arbitrary in execution speeds.!. does snap rounding provided non intersecting output contours(rings).

flippmoke commented 8 years ago

Note -- adding previous conversation from email with @MaheshNaikM here for historical purposes:

Basically, if you took all of the points created by a vatti prior to doing your actual clipping you could collect all the integer coordinates they pass through as "hot pixels". Then as you are doing your vatti loop and finding intersections, you simply "snap" points that are prior to the intersections (and any other point additions) to the points they pass through. This is a form snap rounding - see http://doc.cgal.org/latest/Snap_rounding_2/index.html

Additionally my intersection processing is different from Angus in that it also finds the intersection location as a floating point calculation first. This helps sort properly the order of intersections prior to rounding the point back to integer coordinates for the actual intersection processing.

flippmoke commented 8 years ago

@MaheshNaikM

does snap rounding provided non intersecting output contours(rings).

Snap rounding will prevent intersecting segments, but will not prevent intersection at points. Intersections at points is cleaned up in the do_simple_polygons() method following the vatti algorithm.

For example - this ring has an intersection at a point and is not valid as per the OGC specification. It should be 2 separate rings to be valid.

screen shot 2016-11-01 at 8 30 59 am

The next image is an example of an intersection of edges that is not on a point. This will not happen as a result of the snap rounding and intersection processing from vatti.

screen shot 2016-11-01 at 8 34 14 am
MaheshNaikM commented 8 years ago

My understanding of output is that if I put the output back in for a union no intersections should be reported.!(this fails in the original..limited edition...Angus Vatti.If one can have non intersecting contours then i can use them as a generator of a non intersecting collection of contours(rings in your notation). Clipping is only one use of vattis method. I am planning to provide a generator for a non intersecting polygon collection akin to random number generator.!.

On Tue, Nov 1, 2016 at 7:06 PM, Blake Thompson notifications@github.com wrote:

@MaheshNaikM https://github.com/MaheshNaikM

does snap rounding provided non intersecting output contours(rings).

Snap rounding will prevent intersecting segments, but will not prevent intersection at points. Intersections at points is cleaned up in the do_simple_polygons() method following the vatti algorithm.

For example - this ring has an intersection at a point and is not valid as per the OGC specification. It should be 2 separate rings to be valid.

[image: screen shot 2016-11-01 at 8 30 59 am] https://cloud.githubusercontent.com/assets/1794907/19891372/cf225c8a-a00d-11e6-83ed-d793c6931800.png

The next image is an example of an intersection of edges that is not on a point. This will not happen as a result of the snap rounding and intersection processing from vatti.

[image: screen shot 2016-11-01 at 8 34 14 am] https://cloud.githubusercontent.com/assets/1794907/19891464/43bfa58e-a00e-11e6-8138-4d25e95daeb2.png

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/mapbox/wagyu/issues/42#issuecomment-257567801, or mute the thread https://github.com/notifications/unsubscribe-auth/AFbTLLOx71qFg0rYdKu7VOz-m0TLugu9ks5q50BfgaJpZM4KlBnV .

MaheshNaikM commented 4 years ago

I have a mutated version of Murtas generic polygon clipper.3 Algorithmic bugs/worms removed.Data structures changed for speedup ....gpc 2.31/2.32/2.33 had such problems that the outputs were unreliable and in reality useless.