How to represent a polygon with hole(s) ?

Question

It's usually popular to work with polygons with their vertices sorted CW or CCW in vectors(2*1 or 1*2 matrices). However, how to state polygons with holes in vectors?

I'm going to apply various process on these polygons, so I want a way of representing with which I could work easily or efficiently.(i.e how to state that kind of polygons in my program in order to ease my algorithms?)

polygons are 2D and I'm programming in MATLAB.

EDIT 1 : I'm going to calculate visibility graph of these polygons(with or without holes).

Answer 1

A polygon, plus a list of polygonal holes. Just be sure the various polygons don't intersect.

What do you plan to do with this thing?

Answer 2

It sounds like each hole is just a polygon inside the polygon itself. Perhaps you could store a vector like you describe for the outer polygon, then a vector of more polygon vectors for the holes.

Answer 3

What exactly do you mean under "a visibility graph" ?

Two "full" poligons, two states possible, either +1 or -1.

If you're representing a hole, you've got one with state +1 and one with state -1, which represents a hole, resulting in state 0.
If you've got overlapping polygons, you'll end up with resultant state >1. Then you can calculate the borders of a new polygon.
If you've got two polygons with holes that intersect, then first calculate the state of a new polygon which consists of outer borders of the two old ones, then deal with holes.

Anyways, ... I think you get the general principle.

Have no idea how to do it in matlab, I used it only marginally so far, and even that for very simple things.

Answer 4

You can break a polygon with a hole in it into two shapes without a hole. When you're doing contour integration in a complex plane, you can create a "cut" from one edge of the polygon that brings you to the edge of the hole; integrate around one side of the hole and back; then traverse around the other side for the second polygon. You end up with two path integrals along each cut that cancel each other out.

"visibility graph" - is this for a radiation view factor calculation with shading? Or a ray-tracing graphics algorithm?

Answer 5

Presumably you'll want to have a tree structure if you want this to be as generic as possible (i.e. polygons with polygonal holes that have polygons inside them with holes inside that, ...). Matlab isn't really great at representing tree structures efficiently, but here's one idea...

Have a struct-array of polygons.

Each polygon is a struct with two fields, 'corners', and 'children'.

The 'corners' field contains a matrix of (x,y) coordinates of the corners, accessed as "data{polyIdx}.corners(:,cornerIdx)".

The 'children' field is a struct-array of polygons.

Here's an example of some code to make a triangle with bogus children that are holes (they aren't really valid though because they will likely overlap:

polygon = struct;
npoints = 3;
polygon.corners = rand(2,npoints);
polygon.children = struct;
nchildren = 5;
for c=1:nchildren
    polygon.children(c).corners = rand(2,npoints);
    polygon.children(c).children = struct;
end

You could continue to recursively define children that alternate between creating holes and filling them.