Триангуляционное множество точек на произвольной плоскости в трехмерном пространстве

Question

У меня есть набор точек в трехмерном пространстве. С максимальной ошибкой 10^-5 я могу разместить плоскость через них (ошибка - расстояние от точки до плоскости).

Есть ли способ триангулировать эти точки на этой произвольной плоскости? Я пробовал Бойера-Уотсона, но это работает только тогда, когда ошибка равна 0. Все остальное, и оно не будет триангулировать, или я не получу хорошую триангуляцию (перекрывающиеся треугольники).

редактировать

Я думаю, что нашел проблему. Под определенными углами алгоритм Бойера-Ватсона не будет работать, потому что мой расчет обводного центра отключен. Как я могу рассчитать центр окружности треугольника в 3D?

Answer 1

Так как я знаю точки на плоскости, я могу вычислить вектор. Этот вектор лежит на плоскости. Далее я вычисляю центр масс точек.

Используя вектор и центр масс, я могу создать большой треугольник на плоскости.

        Vertex p1 = new Vertex(dir * 3000 + center);
        Vertex p2 = new Vertex(Quaternion.AngleAxis(120, plane.normal) * dir * 3000 + center);
        Vertex p3 = new Vertex(Quaternion.AngleAxis(240, plane.normal) * dir * 3000 + center);

Теперь, когда у меня есть вмещающий треугольник, я могу просто использовать Бойера-Ватсона. Для кругового центра в 3D я использую:

Vector3 ac = p3 - p1;
    Vector3 ab = p2 - p1;
    Vector3 abXac = Vector3.Cross(ab, ac);

    circumceter = p1 + (Vector3.Cross(abXac, ab) * ac.sqrMagnitude + Vector3.Cross(ac, abXac) * ab.sqrMagnitude) / (2 * abXac.sqrMagnitude);

И теперь у меня есть триангулированный набор точек на произвольной плоскости в 3D.