Как найти триангуляции Делоне грани, содержащие заданные точки

Question

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

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

Answer 1

Для данного треугольника ABC точка находится внутри треугольника, если она находится на той же стороне линии AB, что и точка C на той же стороне линии BC, что и точка A, и на том же сторона линии AC как точка B есть. Вы можете предварительно оптимизировать эту проверку для каждого треугольника и проверить их все, пока не найдете треугольник (ы), в котором он находится. Подробнее см. this page.

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

Answer 2

Я предполагаю, что треугольники не пересекаются, за исключением общих ребер.

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

Более надежный способ:

1. Найти ближайший край с точки
2. Выберите один из треугольников касаясь этого края
3. сделать одну проверку для этого треугольника (точка лежит на той же стороне, что и третья вершина треугольника)
4. Если «внутри» - вернуть этот треугольник
5. Если «снаружи» - возвращает другой треугольник на этой кромке (или «ничего», если нет другого треугольника)

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

Для # 1 вы можете использовать что-то вроде квадроцикла, как предлагает Майкл Уайлд.

Answer 3

Триангуляция Делоне сама по себе является структурой данных поиска. Вероятность реализации триангуляции Delaunay, вероятно, имеет функции определения местоположения. Как вы вычислили триангуляцию Деланея ваших очков?

CGAL имеет реализацию двумерных и трехмерных триангуляций. Полученная структура данных способна локализовать любую точку, используя прогулку от данной точки. См., Например, that chapter of the manual. CGAL - это библиотека C++, но она имеет python bindings.

Answer 4

Этот простой пример триангулирует 10 случайных точек, еще 3 случайных точек генерируются и, если они попадают в треугольнике, вершины приведены:

import numpy as np 
from pyhull.delaunay import DelaunayTri 

def sign(a,b,c): 
    return (a[0]-c[0])*(b[1]-c[1])-(b[0]-c[0])*(a[1]-c[1]) 

def findfacet(p,simplice): 
    c,b,a = simplice.coords 
    b1 = sign(p,a,b) < 0.0 
    b2 = sign(p,b,c) < 0.0 
    b3 = sign(p,c,a) < 0.0 
    return b1 == b2 == b3 

data = np.random.randn(10, 2) 
dtri = DelaunayTri(data) 

interpolate = np.random.randn(3, 2) 

for point in interpolate: 
    for triangle in dtri.simplices: 
     if findfacet(point,triangle): 
      print "Point",point,"inside",triangle.coords 
     break 

Использование matplotlib для визуализации (код опущен):

пунктирные голубые линии теперь соединяют точку интерполировать с вершинами треугольника он лежит внутри. Черные линии - это выпуклая оболочка, а сплошные голубые линии - триангуляция delaunay.