CODEWITHSUNDEEP
c#algorithm
Graviton
Graviton

Reputation: 83254

Algorithm to compute the remaining polygon after subtraction

I have a big polygon (Pa). Inside the polygon there are a lot of small "holes", as shown:

Here are a few condition for the holes:

  1. The holes cannot overlap one another
  2. The holes cannot go outside the outer polygon
  3. However, the holes can touch the outer polygon edge

How to obtain the remaining polygon ( or the polygon list) in an efficient manner? The easiest way ( brute force way) is to take the Pa, and gradually computing the remaining polygon by subtracting out the holes. Although this idea is feasible, but I suspect that there is a more efficient algorithm.

Edit: I'm not asking about how to perform polygon clipping ( or subtraction) algorithm! In fact that's something I would do by brute force. I'm asking in addition to the polygon clipping method ( take the main polygon and then gradually clip the holes out), is there other more efficient way?

Upvotes: 6

Views: 3878

Answers (4)

Daren Thomas
Daren Thomas

Reputation: 70314

This is very hard to do in a general manner. You can find source code for a solution here:

General Polygon Clipper (GPC)

Upvotes: 3

Lucero
Lucero

Reputation: 60190

I agree with salva, but my post is going to address the drawing part. Basically, you can add up all lines of the main and the hole polygons together and thereby get a single complex polygon.

The algorithm itself is not very complicted and it is nicely explained in the Polygon Fill Teaching Tool.

Upvotes: 1

salva
salva

Reputation: 10234

Well, if you use the right representation for your polygon you would not need to do anything. Just append the list of edges of the holes to the list of edges of Pa.

The only consideration you should have is that if some hole vertex or edge can touch Pa edge, you will have to perform some simplification there.

A different problem is rendering that polygon into a bitmap!

Upvotes: 2

ferosekhanj
ferosekhanj

Reputation: 1074

You can do like this.

  1. Draw the main polygon with a color in a bitmap.
  2. Draw the holes with another color in the same bitmap.
  3. Then extract the polygon by running marching square algorithm with the main polygons color as threshold.
  4. The output will contain all the points that belong to that polygon.
  5. You can sort the points if you want it as a continous closed polygon.

Upvotes: 0

Related Questions