Ah. That’s O(n^2) and won’t handle self-intersecting paths, which are extremely common in the real world :(
In other words: Lorenzetto trapezoidation is half of libtess. The problem I had is that monotone polygon decomposition is really hard to make work, maybe impossible, while preserving curves. So I just threw that part out. End result: A simple approach.
-
-
What’s become clear to me is that trapezoids are a much more natural mesh representation than triangles for 2D vector paths. Keith Packard came to the same conclusion a decade ago, BTW.
-
Indeed, it’s a variation on the classic scanline algorithm.
- 1 more reply
New conversation -
-
-
I suppose Pathfinder has to deal with a lot of skinny horizontal triangles instead ;-) At one stage I considered a post triangulation merging algorithm.
-
Yep, it does have a lot of skinny triangles. But I’m willing to accept that drawback because it’s so simple. I want to ship and have the code be maintainable :)
- 5 more replies
New conversation -
-
-
For reference, this paper details the quad-edge data structure used by libTess: http://www.sccg.sk/~samuelcik/dgs/quad_edge.pdf …
Thanks. Twitter will use this to make your timeline better. UndoUndo
-
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.
