CODEWITHSUNDEEP
algorithmmathgeometrypolygons
Christian Wolf
Christian Wolf

Reputation: 1237

How to intersect multiple polygons?

I am looking for an algorithm with the following input and output:

Input: A set of polygons in a plane. E.g. P1...Pn and S. (P1...Pn might be concave, S is convex.)

Output: The area of theset of polygons in this plane that equals the difference of S and the union of P1...Pn.

I found algorithms to intersect or merge TWO polygons. But since each of those operations might produce several polygons I createt tons of polygons if I did it naively.

So: How to handle the intersection of multiple polygons?

It would be ok, if all polygons are connected together since only the area is what I am after. My thought was to use directed polygons to simulate holes but then I again have the problem to find out if I have a "minimal representation" as n could blow up. [Do you understand what I am talking about? It's quite strange...)

Upvotes: 2

Views: 1702

Answers (3)

n. m. could be an AI
n. m. could be an AI

Reputation: 120079

The most straightforward approach would be decomposing your concave polygons into convex ones. Then intersecting two convex polygons is almost trivial.

Upvotes: 0

Eric Bainville
Eric Bainville

Reputation: 9906

You could throw all edges together into a sweep line algorithm. It may not be optimal (?) but at least you will get the minimal representation you are looking for.

Upvotes: 4

ElKamina
ElKamina

Reputation: 7817

One solution is to convert each polygon into a bunch of triangles. Once you do that it is fairly easy to find union/intersection/difference between a set of areas since you can perform the same functions trivially on a triangle (result on two triangles may include up to 6 triangles).

Upvotes: 0

Related Questions