Polygon Clipping

3
votes

The question I have here is quite hard for me to describe in words... So I'll use Pictures! In general, The issue I have is as follows:

Say I have Polygon A:

Polygon A

Which is intersected at two points by an open polygon B:

Polygon B Intersecting A

What algorithm can I form two closed polygons out of this intersection? (Note that there are three solutions here the one I'm searching for is highlighted)

enter image description here

The preferable solution is

  • The Smallest of all solutions given that:
  • A does not contain B

So, any suggestions on how to generate B (and a new A) after the intersection takes place? I'm new to Polygon Math (and 2D Shape interaction in general) so I have no idea where to start or where to look!

Thanks!

1
javascriptpolygonclipping
I believe what you are looking for is called polygon slicing, so you might search for that as well. Note that you can in theory end up with more than 2 sections depending on the line. – GrandmasterB
@GrandmasterB Woah! That stuff's intense... And way over my head too! Maybe there is a better solution to my problem. What I'm trying to do is fill up Polygon A with points, and have the user separate them into regions by drawing lines (hence the unclosed polygon B)... This is the only method I can think of though... Maybe I'll have to limit the user to a single line-stroke to simplify things? – Fuzzyzilla
Oh, I know. It sounds so simple at first :-) You might look around for existing libraries that do this. Some of the existing javascript graphics libs may have this functionality. – GrandmasterB
@GrandmasterB IDK... It seems a bit extreme to include an entire graphics library to perform one task... I'll look into it some more! Thanks! – Fuzzyzilla

1 Answers

0
votes

you "represent" your polygons by their contours. a contour is a, somehow ordered, sequence of vertices (each vertex is given by its planar coordinates, x and y). the segmented polyline you draw inside A is a part of the contour of your new poly, B. the other part of the same contour is one of the two halves of the contour A. you choose which of the two (you say the smallest, but it is not clear what that means...the smallest area ?).

in the end, you close the contour of B, by completing the series of vertices for it with that part of contour A that also belongs to B. that is the contour/representation of your desired polygonal region, that is your solution.

in case you got 2 Bs (one completed with the first "half" of contour A the other with the second), and want the one having the smallest area, you just compute the area for each of the two Bs (by using the coordinates of the contour vertices) and select the smallest. you can easily search for the formula that gives you the area of a 2D polygon by using the coordinates of its vertices or you can try to derive it yourself.