Как изобразить многоугольник с отверстием (ями)?

Question

Обычно популярно работать с полигонами с их вершинами, отсортированными по CW или CCW по векторам (2*1 или 1*2 матрицы). Однако, как сформулировать полигоны с дырками в векторах?

Я собираюсь применить различные процессы к этим полигонам, поэтому мне нужен способ представления, с которым я мог бы работать легко и эффективно (например, как указать такой тип полигонов в моей программе, чтобы упростить мои алгоритмы?)

полигоны 2D и я программирую в MATLAB.

РЕДАКТИРОВАТЬ 1: Я собираюсь рассчитать график видимости этих полигонов (с отверстиями или без).

Answer 1

Как уже упоминалось, многоугольник с дырками может быть представлен как внешняя граница плюс ноль или более внутренних границ, которые все взаимно не перекрываются *. Если вы используете ненулевой номер обмотки для определения внутри / снаружи, не забудьте указать свои внутренние границы в противоположном направлении в качестве внешних границ (против часовой стрелки для внешней стороны и по часовой стрелке для внутренней части или наоборот), чтобы интегральные контуры были нулевыми внутри отверстия.

К вашему сведению, такое определение / представление было формализовано в Спецификации простых возможностей OpenGIS ( PDF).

Насколько представление:

Вероятно, у меня был бы массив ячеек из K Nx2 матриц, где первый элемент в массиве ячеек - это внешняя граница, а остальные элементы (если они есть) в массиве ячеек - это внутренние границы. Я бы использовал массив ячеек, потому что на каждой границе не может быть одинакового количества точек.

* non-overlapping = за исключением отдельных точек, например, ромб внутри квадрата:

Answer 2

Вы можете разбить многоугольник с отверстием в нем на две формы без отверстия. Когда вы выполняете интеграцию контуров в сложной плоскости, вы можете создать "разрез" от одного края многоугольника, который приведет вас к краю отверстия; интегрировать вокруг одной стороны отверстия и обратно; затем пройдите вокруг другой стороны для второго многоугольника. В результате вы получите два интеграла по путям вдоль каждого разреза, которые нейтрализуют друг друга.

"График видимости" - это для расчета коэффициента радиационного обзора с затенением? Или графический алгоритм трассировки лучей?

Answer 3

Кажется, что каждая дыра - это просто многоугольник внутри самого многоугольника. Возможно, вы могли бы сохранить вектор, который вы описываете для внешнего многоугольника, а затем вектор с несколькими векторами многоугольников для дырок.

Answer 4

Многоугольник, плюс список многоугольных отверстий. Просто убедитесь, что различные полигоны не пересекаются.

Что вы планируете делать с этим?

Answer 5

Предположительно, вы захотите иметь древовидную структуру, если хотите, чтобы она была как можно более общей (то есть полигоны с многоугольными отверстиями, в которых есть многоугольники с отверстиями внутри,...). Matlab не очень хорош для эффективного представления древовидных структур, но вот одна из идей...

Есть структура-массив полигонов.

Каждый многоугольник - это структура с двумя полями: "Углы" и "Дети".

Поле "углы" содержит матрицу (x,y) координат углов, доступ к которым осуществляется как "data{polyIdx}.corners(:,cornerIdx)".

Поле 'children' является структурным массивом полигонов.

Вот пример кода для создания треугольника с фиктивными дочерними элементами, которые являются дырками (хотя они на самом деле недопустимы, потому что они, вероятно, будут перекрываться:

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

Вы можете продолжать рекурсивно определять дочерние элементы, которые чередуются между созданием отверстий и их заполнением.

Answer 6

Что именно вы имеете в виду под "графом видимости"?

Два "полных" полигона, возможно два состояния: +1 или -1.

Если вы представляете дыру, у вас есть одна с состоянием +1 и одна с состоянием -1, которая представляет дыру, в результате в состоянии 0.
Если у вас есть перекрывающиеся полигоны, вы получите результирующее состояние>1. Затем вы можете рассчитать границы нового многоугольника.
Если у вас есть два многоугольника с отверстиями, которые пересекаются, то сначала рассчитайте состояние нового многоугольника, который состоит из внешних границ двух старых, а затем разберитесь с отверстиями.

В любом случае,... я думаю, вы понимаете общий принцип.

Понятия не имею, как это сделать в Matlab, я пока использовал его лишь незначительно, и даже для очень простых вещей.