Регулярно распределенная ортогональная сетка триангуляции Делоне (вычисление параболоидных коэффи- циентов)

Я пытаюсь построить триангуляцию Делоне для очень конкретного случая, когда входные координаты x и y являются ортогональными и относительно равноудаленными.

Учитывая, что размер данных относительно велик (точки триангуляции 1000x1200) и что алгоритм ***** не знает о моем дополнительном ортогональном условии, триангуляция относительно медленная (25 секунд на моей машине).

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

В следующем графике я обозначил каждый из треугольников индексом, начальным направлением определения вершин и вершин:

В этом случае у меня есть и x и y координаты [-1, 1.33, 3.67, 6] и [2, 4.5, 7, 9.5, 12] соответственно.

В настоящее время я использую обертки SciPy для *****, и мне удалось построить вершины и соответствующую информацию о соседе, но мне трудно определить атрибут equations (как кратко сказано в http://docs.scipy.org/doc/scipy-dev/reference/generated/scipy.spatial.**********.html).

По сути, я считаю, что эти значения являются параметрами каждого треугольника, нормального к параболоиду, определяемого атрибутами paraboloid_scale и paraboloid_shift, но не могут придумать магические числа, подходящие для интерпретации *****. Должны быть значения n_dimensions + 1 для каждой вершины, и в SciPy есть код, который вычисляет расстояние каждой вершины от заданной точки:

dist = d.equations[isimplex*(d.ndim+2) + d.ndim+1]
for k in xrange(d.ndim+1):
 dist += d.equations[isimplex*(d.ndim+2) + k] * point[k]

Итак, мои вопросы:

  • Я правильно интерпретировал атрибут equation?
  • Есть ли там инструмент, который делает это для меня?
  • Можно ли вычислить значения параметра equation, учитывая мой ортогональный и в основном равноудаленный случай, не пройдя через *****?
1 ответ

Чтобы вычислить триангуляцию 2D Delaunay, ***** поднимает 2D-точки в 3D на параболоид, затем вычисляет нижнюю выпуклую оболочку этих трехмерных точек, а триангуляция 2D Delaunay - это проекция в 2D-плоскости этого 3D нижнего выпуклого корпус.

Посмотрите изображение, взятое из здесь:

Для каждой грани триангуляции 2D Delaunay соответствующая 3D-гиперплоскость представляет собой трехмерную плоскость, проходящую через три поднятые 3D-точки. Если триангуляция - Делоне, эта гиперплоскость соответствует пустому кругу в 2D. См. Это изображение, взятое из здесь:

licensed under cc by-sa 3.0 with attribution.