Rosetta Code Sutherland-Hodgman clipping task

Forum > General

(1/1)

VTwin:
I spent some time searching for a pascal implementation of Sutherland-Hodgman polygon clipping.

Nothing on Rosetta Code, so I wrote the attached project following the Rosetta Code task. Should I submit it?

wp:
Submit where? Rosetta Code? Yes, for sure. But I think it is interesting also for fcl-image. In this case you should provide a stand-along procedure for the Lazarus GraphUtils unit and submit a patch (but using TPoint rather than TFPoint).

Since I spent some time with self-overlapping polygons and polygons with holes (https://wiki.freepascal.org/Developing_with_Graphics#Self-overlapping_polygons): Does your algorithm work in such cases, too? And I see the word "Inside" in your code. Does the algorithm depend on the selection of the even-odd or non-zero winding rules for polygon filling? Because they determine what is "inside".

VTwin:
Thanks for the response wp.

Sutherland-Hodgman clipping requires that the clipping region be a simple (not self-intersecting or with holes) convex polygon. The Wikipedia page

https://en.wikipedia.org/wiki/Sutherland%E2%80%93Hodgman_algorithm

has a nice summary. The pseudocode on that page is similar to my code, but I moved the "lines intersect" code so it is only called if one point is inside. This avoids the calculation when both points are outside.

The "inside" function is not the same as an "inside polygon" function. It computes which side of a clip region edge the point is on. One other point is that some of the Rosetta code examples use slope-intercept forms instead of parametric forms. I prefer to avoid the slope-intercept form, which can introduce infinities.

I have also implemented Cyrus-Beck and Cohen–Sutherland line segment clipping.

I will have a look at the GraphUtils unit to see if any of these might be useful additions.

EDIT: I am unsure about the restrictions on the subject polygon. It does not need to be convex, but I am unsure about self-intersecting or with holes. Maybe a few tests are in order.

Navigation

[0] Message Index