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

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

Details

Reviewers
rahn
nienhueser
Summary

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

Repository
R34 Marble
Lint
Lint Skipped
Unit
Unit Tests Skipped
dkolozsvari retitled this revision from to Implementing the Weiler-Atherton polygon clipping algorithm for Marble's ClipPainter.Aug 2 2016, 6:34 PM
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.

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
src/lib/marble/ClipPainter.cpp
117

Seems unused.

152

Should be

const QSharedPointer<Point>& nextPoint

I guess? (+const). Same below.

778

const auto & (+const)

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

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

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.