Тест точки в Делоне из облака точек без сетки

Я предполагаю, что вы находитесь в 2D без коллинеарных точек. То, что я предлагаю, работает и в 3D. Постройте Kd-дерево, содержащее все точки. Затем найдите двух ближайших соседей точки P. Постройте описанную окружность.

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

Для реализации вы можете использовать, например, CGAL, который предоставляет Orthogonal_incremental_nearest_neighbor, функция has_on_bounded_side из класса Triangle_2 и функция circumcenter.

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