Polygon clipping by a line

[krtxmrtz]

(I wonder if this would be more appropriate for the game development codebank or the math forum).

This is a subroutine for clipping a general (convex or concave) polygon by a (infinite) straight line defined by 2 points.

The polygon is a closed contour with N vertices, such that points 1 and N are the same. A polygon UDT is used (see code below) which includes the coordinates of the vertices, the number of branches and pointers to the first point of each branch. Initially the polygon is supposed to have a single branch, but as a result of clipping it may be split into a number of individual closed contours.

The UDT definitions follow below. The subroutine comes next in a separate post as it's too long to fit in one post. Two screen shots show a demo polygon just before and after the clipping operation. A demo project is also included.

'Data type for the polygon vertices
Private Type punkt
    X As Single
    Y As Single
End Type
'Data type for the entire polygon
Private Type Polygon
    vertex() As punkt
    n As Integer        'Total number of vertices (first and last are the same)
    up() As Integer     'Pointers to the vertices where the polygons start:
    'when the polygon is plotted, we must go to them with "pen up"
    nups As Integer     'Number of sub-polygons (branches): initially 1
    'but after the polygon has been clipped, new polygons may be created
End Type