Concave Polygon Line Clipping without Degenerate Edges

Question

I have search and researched the internet last days to find a suitable method for my problem.

Problem:

Clip a concave polygon against an infinite line without direction (Actually a polygon against a plane in 3d but the problem is similar i think). Currently i use Sutherland-Hodgman but the resulting polygons sometimes contains zero-area parts created from degenerate edges and it also do not support polygons containing holes.

The best algorithm i have found that could solve my problem is the Weiler-Atherton algorithm but it is for clipping against a polygon with clockwise edges and all i have is an infinite line (in 3d a plane) missing direction info.

Question:

Is there a algorithm to clip a concave polygon that suits my needs or do anyone have a suggestion on how to modify the Weiler-Atherton algorithm to work for this case? There are webpages that suggests it can be generalized to support more cases but i can not figure it out.

//Regards Eiken

Answer 1

You could use a polygon clipper* to solve this by converting the line into a clipping polygon. Assuming you aren't clipping in a near horizontal plane, just make sure the critical (clipping) edge of the clipping polygon is a little larger than the subject polygon's vertical dimensions (ie the edge extends a above and below the subject polygon). If clipping in a near horizontal plane, make sure the critical edge is a little wider than the subject.

*eg Clipper - http://sourceforge.net/projects/polyclipping/

Disclosure: I'm the author of Clipper, so there's the potential for a personal bias.

Answer 2

Found a suitable algorithm in Graphic Gems V which solves my problem. If someone have the same problem this is the reference:

Glassner, A., ''Clipping a Concave Polygon'' , in Graphics Gems V, A. Paeth, ed., Academic Press, Cambridge, 1995