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

Question

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

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

полигоны являются двумерными, и я программирую в MATLAB.

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

Answer 1

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

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

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

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

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

Answer 2

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

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

Answer 3

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

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

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

Поле 'corners' содержит матрицу (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 4

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

Answer 5

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

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

Answer 6

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

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

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

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

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