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

Question

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

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

Answer 1

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

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

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

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

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

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

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

Вы сделали.

Answer 2

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

Answer 3

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

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

.
 ..

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

Answer 4

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

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

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

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

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

Answer 5

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

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

Answer 6

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

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