The ClipPainter up until now used the Sutherland-Hodgman polygon clipping algorithm. The Sutherland-Hodgman renders borderline issues when clipping concave polygons, but that is fine for rendering. The problem arrives, when those borderlines become visible, as in the osm-simplify tool's BaseClipper. For that, there is another polygon clipping algorithm, which clips concave polygons correctly, that is the Weiler-Atherton.
Details
Details
- Reviewers
nienhueser rahn
I've implemented the algorithm into ClipPainter for testing purposes, but in the end it should be used only for the BaseClipper in the osm-simplify tool.
Diff Detail
Diff Detail
- Repository
- R34 Marble
- Lint
Lint Skipped - Unit
Unit Tests Skipped
Comment Actions
Improved the algorithm to be faster and more readable. Still need to write comments for it. There is one little issue which I worked out with a simple break, so it wouldn't crash. The cause is somehow related to the intersections added at the cornerpoints, because the Weilner-Atherton algorithm is not prepared for that(in a perfect, mathematical world, it can't even occur). Besides that little issue(which is not even visible most of the times), the clipping works fine.
Any suggestions are welcome. I'm moving on to implement this in BaseClipper.
Comment Actions
Sounds great! The patch does not apply unfortunately, it seems to be based on a revision before 640cf6e. Can you update it to latest master?
Comment Actions
The clipping algorithm works perfectly now, there are no major issues, except for the case when the same polygon appears twice on the viewport(ie. when zoomed out enough to see the world map twice or three times), but that case will not apply for the osm-simplify tool's tile cutting algorithm anyway, so I think we can overlook that.