Recent

Author Topic: Rosetta Code Sutherland-Hodgman clipping task  (Read 593 times)

VTwin

  • Hero Member
  • *****
  • Posts: 1215
  • Former Turbo Pascal 3 user
Rosetta Code Sutherland-Hodgman clipping task
« on: June 01, 2023, 09:13:12 pm »
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?





“Talk is cheap. Show me the code.” -Linus Torvalds

Free Pascal Compiler 3.2.2
macOS 12.1: Lazarus 2.2.6 (64 bit Cocoa M1)
Ubuntu 18.04.3: Lazarus 2.2.6 (64 bit on VBox)
Windows 7 Pro SP1: Lazarus 2.2.6 (64 bit on VBox)

wp

  • Hero Member
  • *****
  • Posts: 11858
Re: Rosetta Code Sutherland-Hodgman clipping task
« Reply #1 on: June 01, 2023, 11:17:21 pm »
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

  • Hero Member
  • *****
  • Posts: 1215
  • Former Turbo Pascal 3 user
Re: Rosetta Code Sutherland-Hodgman clipping task
« Reply #2 on: June 01, 2023, 11:58:31 pm »
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.
« Last Edit: June 02, 2023, 12:21:41 am by VTwin »
“Talk is cheap. Show me the code.” -Linus Torvalds

Free Pascal Compiler 3.2.2
macOS 12.1: Lazarus 2.2.6 (64 bit Cocoa M1)
Ubuntu 18.04.3: Lazarus 2.2.6 (64 bit on VBox)
Windows 7 Pro SP1: Lazarus 2.2.6 (64 bit on VBox)

 

TinyPortal © 2005-2018