Yup! A couple of final tweaks on the old algorithm and a teeny-tiny problem surfaces.
I got sick of reading about how various algorithms can be implemented (eg. Vatti, Sutherland–Hodgman and a slew more). There are implementations in various languages and lots of academic papers but they all have common downfalls. They use the words or phrases such as "just" or "well-known" in their explanations or they limit their application to strict geometry inputs like perfect axis-aligned convex shapes.
I will elaborate on some of the pitfalls over time... as I find them.
Today, unexpected overlaps.
Two polygons:
The first image on the left is their original layout of the shapes and their vertices. The one on the right, subtitled (rolled), is one of the things I like to do with my geometry objects because it makes it easier for me to keep track of the vertices and where they intersect. I "roll" them so that vertex 0 has the shortest distance to it's extent origin... not the map origin or the group origin, just the shape's extent origin.
Does it need to be done? probably not, but I don't care anyway.
The images below are the results of a clip. During the process I added the intersection points onto the geometry... because I could. The first clue that things might be going fully as planned are shown on the right-most image on the top portion of the clip. The "only" difference in the clip in the 4 quadrants of the clip polygon is that it touches (aka, intersects) just a teeny bit with an extra segment (technically 2) on the polygon pl_ (see pl_new, point 8). The circuitous path in pl_n from points 2, 3, 4, 5, 6 was not what I wanted obviously. There is probably some "well known" algorithm that "just" orders them correctly, but I couldn't implement one without creating a whole load of classes and bloating my code 3-fold.
I use NumPy magic to determine the intersection points all at once and to categorize all the points as to whether:
From that I ordered the intersection points on each segment. There is no way of knowing this apriori since the intersections were returned with respect to the segment IDs meaning that on a segment where there were multiple intersections, there was no guarantee that the first intersection was the closest one to the start of the segment. That topic will be the topic of another blog since it is pretty cool and is probably "just" another "well known" algorithm that I couldn't find or figure out without code bloat. The result isn't too bad.. just some pesky little pokey bit sticking up from point 7 to 8.
You probably noticed that a couple of the point lables look blurry... that is because, there ae duplicate points on the segments.
Here it is, I "just" "simply" had to identify the segments that overlapped one another. It works great! see!
until you clip a polygon that happens to result in multipart outputs.
Or one that has a couple of stringy-bits connecting the parts
Details will come in future blogs.
So "just" remember that most of these can be implemented by "well-known' algorithms, so you don't need to roll them out on your own, unless you want to see how things work under the hood.
Homework