Триангуляция произвольного 4-вершинного многоугольника

Question

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

Результат должен выглядеть следующим образом:

Треугольник 1: v1,v2, v3 Треугольник 2: v2, v3, v4

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

Answer 1

Вы должны разбить это на два шага:

1) Сортировка вершин по часовой стрелке. См. этот вопрос и ответы на него .

2) Найдите диагональ, которая находится внутри четырехугольника (если четырехугольник вогнутый, только один из них будет внутри. Если выпуклый, оба они). См. этот вопрос и ответы на него .

Как только вы это поймете, должно быть очевидно, как найти два треугольника.

Answer 2

Ну что ж, вот еще одна домашняя работа ...

Если вы не имеете представления о координатах, вы можете быть ввернуты. Разделите это как v1, v2, v3 и v2, v3, v4. Вы не можете сделать хуже, чем это. Если вы знаете площади или как-то их рассчитываете, читайте дальше.

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

Давайте назовем площади треугольников A, B, C, D:

Существует всего 2 ^ 4/2 способа разделить набор треугольников.

Если A + B + C + D минимально, у вас либо ошибка в расчете площади, либо у вас есть отрезок.

Если такой случай, как A- (B + C + D), минимален, ваш полигон на самом деле A с дополнительной вершиной. Кроме того, вы можете сделать 3 четырехугольника из B, C, D, если хотите.

Если регистр, подобный (A + B) - (C + D), минимален, вы можете выбрать A, B или C, D

Answer 3

Если вы на самом деле пытаетесь их визуализировать, вы должны создать вершину посередине и сделать 4 треугольника со средней точкой в ​​качестве одного из вершин.В противном случае я не вижу, что не так с движением (v1, v2, v3), (v2, v3, v4)

[EDIT:]

Извините, я думаю о 3D.Это не относится.

Answer 4

Это невозможно, если вы не знаете координаты.

Для первого треугольника выберите любые три точки.Неважно, какой;вы получите работоспособный треугольник.

Для второго треугольника найдите «дальнюю» точку и удалите ее, подставив оставшуюся точку.

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

Учитывая первый треугольник (A, B, C) и четвертую точку D, дальней точкой является точка в треугольнике (представьте, что A), где пересекаются отрезки (A, D) и (B, C).Все просто.

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