Submitted by mark on Thu, 10/22/2015 - 22:01
Got it. My mistake. I assumed that splitting curves at their horizontal extrema would be enough. But in the case below the green curve ended up above the blue curve in the sweep line buffer. That's because SweepComp is using the end points of the curve (red line) and then of course the green line ends up above the blue one.
I could solve that by also splitting curves at the vertical extremas (orange line)... or by using the left point's control point?
Submitted by mark on Sat, 10/17/2015 - 06:46
Regarding my last post I found two issues:
- The sorting order of line segments 3 and 4 in the sweep line buffer is wrong.
- Line 27 was calculated to be inside the resolution of the union operation.
Either I screwed up elsewhere, or there are still some issues in the original implementation. *sigh* And it all looked so good a few days ago.
Submitted by mark on Sun, 10/11/2015 - 14:19
Slowly getting there. paper.js's solveCubic() algorithm lacked precision so I replaced it with the one from the GNU Scientific Library whose algorithm has street cred for about 500 years. I also simplified the way curves are stored, which resolved another source of issues.
In the picture below I fail to find the intersection between the segments number 3 and 31:
Submitted by mark on Sun, 10/04/2015 - 13:50
I began extending the algorithm to handle paths containing Bézier curve segments:
This shows how far I've got. After the next step everything will drown in errors.
Submitted by mark on Wed, 09/30/2015 - 00:05
Guess what! After fixing the 3rd issue, the algorithm suddenly feels stable. And because I'm so happy about it, below is a picture of my scribbling paper used to get there. Oh the irony of it: Requiring paper to get rid of paper. :)
Submitted by mark on Sun, 09/27/2015 - 16:23
I replaced the algorithm which calculates the line intersections. The next class of errors are cases where dividing a line would place it somewhere else within the sweep line buffer. Currently the line's flags are calculated, then the line is divided and because the division might have changed the position of some lines in the sweep line buffer, the flags are recalculated for some known cases.
I found one case where this didn't happen and it seems that there are more.
A more reliable approach might be to reevaluate the order within the sweep line buffer and act accordingly. From there I could even brute force a list of all cases where the flags need to be recalculated.
Submitted by mark on Tue, 09/22/2015 - 11:04
Submitted by mark on Mon, 09/21/2015 - 22:45
I'm beginning to grasp the algorithm. Pretty clever. The problem might be that the code to calculate line intersections isn't stable.
Submitted by mark on Wed, 09/16/2015 - 07:49
Each iteration of the sweep algorithm is now printed into a PDF file. The trouble is that in a special case of overlapping lines of the subject and clipping polygons, none of these lines end up in the result when at least one should.
Submitted by mark on Wed, 09/09/2015 - 11:58
What we see here is this:
- the black line with the crosses is the previous polygon (subj)
- the blue line with the circles is the polygon to be added (clip)
- the red line is the result of the union operation (result)
My assumption is that the point on the right might be the same for subj and clip and this is causes the routine constructing the result from the sweep events to pick another point. In this case where the red line goes straight upwards it picked the next point right to it.
Which is strange, there shouldn't be a sweep event connecting these points at all...