Как взять (N) -симплексные ребра?

Question

В алгоритме quickhull необходимо построить конус на множестве ребер.

Ребро считается субимплексом с удалением одной вершины.Требуется, чтобы добавление вершины к ребру образовало симплекс, как если бы эта вершина была просто заменена.

Например, при хранении симплексов в виде списков вихрей, для треугольника, определенного с вершиной {p0, p1ребра, p2}: {p1, p2}, {p2, p0}, {p0, p1} - в этом порядке индекса.Теперь, при добавлении новой вершины p в конец списка вершин ребра, новые треугольники: {p1, p2, p}, {p2, p0, p}, {p0, p1, p} Они имеют ту же ориентацию, как если бы они были оригинальнымиТреугольник был наклонен.

Для треугольника ребро, противоположное р1, имеет обратный порядок остальных вершин.Для тетраэдра, это для p0 и p2.

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

Хорошо.В общем случае хранения вершины set недостаточно для представления симплекса, если его ориентация имеет значение.Один и тот же набор может представлять эквивалентные симплексы с разным знаком объема. список может сохранять ориентацию, но нетривиально извлечь его только из порядка.Таким образом, ни множества, ни списки сами по себе не являются хорошим решением (для представления как симплекса, так и его ребер).

Answer 1

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

Если вы заменяете каждую вершину v[i] поочередно новой точкой p, самая простая последовательная вещь, которую нужно сделать, это заменить ее точкой, которую она заменяет.Таким образом, для треугольника {v0,v1,v2} вы получите новые треугольники {p,v1,v2}, {v0,p,v1} и {v0,v1,p}.

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

В приведенном выше примере замена p на конечную вершину приведет к изменению ориентации, если p уже не является конечной.В этом случае вы можете исправить это, поменяв местами первые две вершины.(обратите внимание, что это уникальное решение только для 3-вершинных симплексов - оно не применимо для 2-симплексов и одного из нескольких решений для N> 3-симплексов).

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

Answer 2

А ребро симплекса не имеет ориентации само по себе.

Только N-симплекс в N-измерениях имеет определенную ориентацию.Это определяется перекрестным произведением N векторов pi-p0 (объем со знаком).Для симуляций меньших размеров в пространстве больших размерностей такое перекрестное произведение не может быть построено.

Для этой сложной задачи (создание новых симплексов с ребрами другого) ребро может быть представлено (упорядоченным) списком вершин иИндекс, куда добавить новую точку, чтобы она была на той же стороне, что и удаленная вершина.Учитывая порядок зацикливания списка (не уверен, что он универсален), его можно повернуть так, чтобы индекс был либо 0, либо 1.