Как выпустить выпуклый многоугольник на правые треугольники, выровненные по осям X и Y?

Question

Для выпуклого многоугольника, представленного множеством вершин (мы можем предположить, что они находятся в порядке против часовой стрелки), как этот многоугольник можно разбить на множество правых треугольников, ноги которых выровнены с X- и Y- оси?

Поскольку я, вероятно, не хватает какой-то математическую терминологию, «ноги» это то, что я называю эти две линии, которые не гипотенузы (извинения заранее, если я ударил по математике жаргоне в лице - краткие поправки дополнительный кредит).

Answer 1

Я не уверен, что это возможно. Подумайте о квадрате, который уже выровнен со сторонами на осях X и Y. Как вы рисуете треугольники, используя вершины, которые также выровнены по осям X, Y?

Или фактические стороны многоугольника, разрешенные вдоль оси x, y. Это означает, что вы можете просто нарисовать линию по диагонали квадрата. Если это так, это может быть трудно сделать с более сложным многоугольником, где некоторые стороны выровнены по осям, а другие - нет.

Answer 2

Я не уверен, что существует общее решение поставленного вопроса. Проблема заключается в совпадении с битом X и Y. Это означает, что каждая вершина должна быть спроецирована на противоположную сторону многоугольника как в направлениях X, так и в Y, а также на новые вершины, созданные в этих точках пересечения. Но этот процесс должен продолжаться для каждой новой вершины, добавленной таким образом. Вам может повезти, и этот процесс прекратится (потому что уже есть вершина, размещенная на противоположной стороне), но в общем случае это будет продолжаться.

Если вы выбрали это ограничение, то предложение Neil N кажется мне хорошим.

Answer 3

Я не уверен в написании алгоритма для этого, но кажется вполне возможным сделать это для любого выпуклого многоугольника на листе бумаги. Для каждой вершины проецируйте линию вертикально или горизонтально из этой вершины, пока она не встретит другую из этих вертикальных или горизонтальных линий. Для вершин с небольшими изменениями угла, где смежные стороны движутся в одном и том же направлении в терминах x и y, вам нужно будет добавить две строки из вершины, одну горизонтальную и одну виртуальную. После того, как вы это сделали, вы должны остаться с полигоном в центре многоугольника, но со сторонами, которые являются вертикальными или горизонтальными, поскольку стороны были сформированы линиями, сделанными из вершин исходного многоугольника. Поскольку эти стороны являются вертикальными или горизонтальными, эту форму можно легко подразделить на несколько треугольников с одной горизонтальной стороной, одной вертикальной стороной и одной гипотенузой.

Answer 4

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

Каждая вершина определяет горизонтальную линию. Для V вершин, то у вас будет набор V строк. Отменить любые линии, которая соответствует одному из следующих критериев:

• Вершина или вершины, определяющие, что линия/имеют самый высокий или самый низкий компонент Y (если одна вершина, эта линия пересекает многоугольник только в этой точке, если два , эта линия совпадает с краем многоугольника)
• Если две вершины имеют одинаковые Y-координаты в противном случае, сохраните только одну из этих строк (она дублируется).

Результат будет напоминать «обвязку» многоугольника.

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

Каждое пересечение определяет вертикальный сегмент. Сегмент содержится внутри многоугольника (если он совпадает с ребром, его можно отбросить), а другой конец соответствует либо другой горизонтальной линии, либо краю многоугольника, если это край сам по себе горизонтален. Определение дела снова является вопросом простого сравнения коордов. Наконец, может быть 0-2 дополнительных вертикальных сегмента, определяемых вершинами с наивысшими и/или низшими Y-координатами, если есть только один из них.

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

Все готово.

Answer 5

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

Если у вас есть трапеция, верх и низ которой параллельны оси X, вы можете легко визуализировать ее с помощью четырех правых треугольников. Позвоните, чтобы сформировать горизонтальную трапецию.

Если у вас есть треугольник с одной стороной, параллельной оси X, вы можете сделать это с помощью 2 правых треугольников - или вы можете рассмотреть вырожденный случай трапеции с верхней частью дна, имеющей длину ноль.

Начните с верхней или нижней части выпуклой оболочки (т. Е. Найдите координату с min или max y) и разделите ее на горизонтальные трапеции.

Это не сложно написать код, чтобы он работал так же хорошо, как и с невыпуклыми многоугольниками.

Answer 6

Я думаю, что это невозможно в общем случае.

Рассмотрим многоугольник {(0, 1), (1, 0), (2, 0)}

. 
.. 

Этот треугольник не может быть разбита на конечное число треугольников, как вы описали.