Эффективный способ построения треугольников с краев/линий?

Question

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

Как я могу эффективно проверить, какие точки являются частью треугольника? Я мог проверять точки падения каждого края и постепенно строить тройку точек, но это звучит значительно медленнее (o (n^2)?). Есть ли что-то вроде linesweep или так для этого?

ура.

Answer 1

Края определяют неориентированный граф G, а треугольники представляют собой набор циклов в G с length=3.

Геометрические триангуляции, как правило, имеют относительно низкую узловой степени (степень d этого числа ребер, примыкающих к каждому узлу, d<=10 является типичным для геометрических триангуляции) и, как таковые, здесь является достаточно эффективным O(n*d^3) алгоритма, который может быть использован для построения множество треугольников.

1. Настройка графоподобной структуры данных, обеспечивающей доступ к списку ребер, смежных с каждым узлом.

2. Итерации по всем узлам. Рассмотрим все пары ребер, смежных с данным узлом i. Для данной пары ребер, смежных с i, мы имеем потенциальный узловой триплет i,j,k. Этот триплет является треугольником, если есть узел, соединяющий края j,k, который можно проверить, просмотрев список краев j,k.

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

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

Надеются, что это помогает.

Answer 2

Если у вас есть 2-мерная настройка, как вы описали, то у вас есть полностью триангулированный плоский граф (без пересечения ребер при исключении конечных точек), который охватывает выпуклую оболочку ваших точек. В этом случае, если сортировать края вокруг каждой вершины круговыми в соответствии с углом, который они создают с вершиной, то вы точно знаете, что каждая пара соседних краев образует треугольник. Кроме того, каждый треугольник можно найти таким образом, если вы выполните эту процедуру для каждой вершины. Каждый треугольник будет найден 3 раза, когда вы будете перебирать все вершины. Вы можете использовать хеш-таблицу для обнаружения дубликатов или сортировать все свои треугольники, когда вы закончите, чтобы идентифицировать дубликаты. Если вы используете хеш-таблицу, то общая сложность, если у вас есть V-вершины, есть O (V log d), где d - максимальная степень вершины (поскольку общее число ребер линейно по числу вершин, потому что у вас есть плоский график). Таким образом, абсолютным худшим случаем является O (V log V), что является самым худшим случаем, если сортировать все треугольники для поиска дубликатов (поскольку максимальное количество треугольников также линейно по числу вершин). Единственное предостережение для этой работы состоит в том, что вам нужно знать соседние вершины (т. Е. Случайные ребра) для каждой вершины.