8

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).

Kamran Bigdely
  • 7,946
  • 18
  • 66
  • 86

6 Answers6

6

As others have mentioned, a polygon with holes can be represented as an exterior boundary, plus zero or more interior boundaries, all of which are mutually nonoverlapping*. If you use nonzero winding number to determine inside/outside, be sure to specify your interior boundaries in the opposite direction as the exterior boundaries (counterclockwise for exterior and clockwise for interior, or vice-versa) so that the contour integrals are zero inside the holes.

FYI, tis kind of definition/representation has been formalized in the OpenGIS Simple Features Specification (PDF).

As far as representation:

I'd probably have a cell array of K Nx2 matrices, where the first element in the cell array is the exterior boundary, and the remaining elements (if any) in the cell array are the interior boundaries. I would use a cell array because there may not be the same number of points on each boundary.

*nonoverlapping = except at individual points, e.g. a diamond inside a square:

alt text alt text

Community
  • 1
  • 1
Jason S
  • 184,598
  • 164
  • 608
  • 970
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?

duffymo
  • 305,152
  • 44
  • 369
  • 561
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?

Beta
  • 96,650
  • 16
  • 149
  • 150
  • I'm going to calculate visibility graph of these polygons(with or without holes). – Kamran Bigdely Jun 25 '09 at 22:33
  • how to represent "list of polygonal holes" ? I want a general, nice way to represnt them(especially in MATLAB). – Kamran Bigdely Jun 25 '09 at 22:37
  • Is that like shadows? Ray tracing? That's simple: you must have a function to decide whether a ray intersects a simple polygon (no holes). Then the ray intersects the polygon-with-holes iff it intersects the polygon and does not intersect any of the holes. – Beta Jun 25 '09 at 22:40
  • 1
    How to represent? Maybe a vector of vectors: the first vector is the polygon, the rest (if any) are the holes. – Beta Jun 25 '09 at 22:43
1

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.

captncraig
  • 22,118
  • 17
  • 108
  • 151
1

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.

Mr Fooz
  • 109,094
  • 6
  • 73
  • 101
  • If you know that you'll never have anti-holes, you could still use the same data structure, but maybe you'd want to rename 'children' as 'holes'. – Mr Fooz Jun 26 '09 at 11:08
  • If you count concentric face islands as one face you will not satisfy the Euler-Poincaré Formula. I don't know if that's important for any application, but it's reason enough for me to scrap the complexity and just let an island in a hole be a separate face. – Samuel Danielson Feb 07 '20 at 13:39
0

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.

Rook
  • 60,248
  • 49
  • 165
  • 242