Implementing the Weiler-Atherton polygon clipping algorithm for Marble's ClipPainter

Authored by dkolozsvari on Aug 2 2016, 6:34 PM.



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.

Test Plan

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

R34 Marble
Lint Skipped
Unit Tests Skipped
dkolozsvari updated this revision to Diff 5644.Aug 2 2016, 6:34 PM
dkolozsvari retitled this revision from to Implementing the Weiler-Atherton polygon clipping algorithm for Marble's ClipPainter.
dkolozsvari updated this object.
dkolozsvari edited the test plan for this revision. (Show Details)
dkolozsvari added reviewers: rahn, nienhueser.
dkolozsvari set the repository for this revision to R34 Marble.
dkolozsvari added a project: Marble.
dkolozsvari added a subscriber: Marble.
dkolozsvari updated this revision to Diff 5708.Aug 7 2016, 4:36 AM

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.

nienhueser edited edge metadata.Aug 7 2016, 9:07 AM

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?

nienhueser added inline comments.Aug 7 2016, 9:18 AM

Seems unused.


Should be

const QSharedPointer<Point>& nextPoint

I guess? (+const). Same below.


const auto & (+const)

dkolozsvari updated this revision to Diff 5724.Aug 7 2016, 6:10 PM
dkolozsvari edited edge metadata.

Generated the diff to the latest version of Marble and some minor changes.

dkolozsvari marked 3 inline comments as done.Aug 7 2016, 6:12 PM

Added const qualifiers.

dkolozsvari updated this revision to Diff 5750.Aug 9 2016, 7:17 AM

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.

nienhueser accepted this revision.Oct 22 2016, 7:57 AM
nienhueser edited edge metadata.

Pushed some time ago already.

This revision is now accepted and ready to land.Oct 22 2016, 7:57 AM
nienhueser closed this revision.Oct 22 2016, 7:58 AM

Pushed some time ago already.