How to imagine a polygon with a hole (s)?

Question

It is usually popular for working with polygons with their vertices sorted by CW or CCW in vectors (matrices 2 * 1 or 1 * 2). However, how to set up polygons with holes in vectors?

I am going to apply a different process to these polygons, so I want me to be able to work, so that I can work easily or efficiently (for example, how to specify such polygons in my program to make my algorithms easier?)

polygons 2D and I program in MATLAB.

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

Answer 1

As already mentioned, a polygon with holes can be represented as an external border, plus zero or more internal borders, all of which are mutually non-overlapping *. If you use a non-zero number of the winding to determine inside / outside, do not forget to specify the inner borders in the opposite direction, as the outer borders (counterclockwise for outward and clockwise for the interior or vice versa), so that the integral contours are zero inside the holes.

FYI, this definition / presentation is formalized in the OpenGIS Simple Function Specification ( PDF ).

Regarding the submission:

I probably would have an array of cells from K Nx2 matrices, where the first element in the array of cells is the outer border and the rest of the elements (if any) in the array of cells are inner borders. I would use an array of cells, because there cannot be the same number of points on each border.

* nonoverlapping = except for individual points, for example. diamond inside the square:

Answer 2

You can break a polygon with a hole in it into two shapes without a hole. When you perform contour integration in a complex plane, you can create a “slice” from one edge of the polygon, which will lead you to the edge of the hole; integrate around one side of the hole and back; then cross the other side for the second polygon. As a result, you get two integrals for each section, which cancel each other out.

Is the “visibility graph” for calculating the emissivity with shading? Or a graphical ray tracing algorithm?

Answer 3

Polygon as well as a list of polygonal holes. Just make sure the different polygons do not overlap.

What are you planning to do with this thing?

Answer 4

It seems that each hole is just a polygon inside the polygon itself. Perhaps you could store a vector as you describe for an external polygon, and then a vector of more polygonal vectors for holes.

Answer 5

Presumably, you will need to have a tree structure if you want it to be as general as possible (i.e. polygons with polygonal holes, inside which there are polygons with holes inside ...). Matlab is not very good at representing tree structures efficiently, but here is one idea ...

Have a structural array of polygons.

Each polygon is a structure with two fields, “corners” and “children”.

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

The "children" field is a structural array of polygons.

Here is an example of some code to make a triangle with dummy children that are holes (they are really not valid, although they will probably 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 can continue to recursively identify children that alternate between creating holes and filling them.

Answer 6

What exactly do you mean by "visibility chart"?

Two "full" polygons, two states are possible: +1 or -1.

If you represent a hole, you have one with state +1 and one with state -1, which is a hole, resulting in state 0.
If you have overlapping polygons, you will get a final state> 1. Then you can calculate the boundaries of the new polygon.
If you have two polygons with holes that intersect, first calculate the state of the new polygon consisting of the outer borders of the two old ones, and then process the holes.

In any case ... I think you will get a general principle.

I don’t know how to do it in Matlab, I have used it only slightly so far and even for very simple things.