Закройте границу многогранника

Question

У меня есть многогранник, у которого отсутствует одно лицо. У меня есть библиотечная функция, которая может помочь закрыть границу после отправки в массиве точек в порядке CCW:

class Mesh {
  // points need to be in CCW order when see from the ouside of this polyhedron
  void addAFace(std::vector<Point> points); 
}

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

Например, вершины должны быть в порядке 0, 1, 2, 3

---

Многогранник может быть невыпуклым.

Answer 1

Для выпуклого многогранника: получите любую точку Px в многограннике, не принадлежащем этой грани (например, для вершины 4, 5, 6 или 7 для вашего примера) и проверьте знак тройного произведения - должен быть отрицательным для порядка CCW

 ((P1 - P0) .cross. (P2 - P1)) .dot. (Px - P1)  

Если нет гарантии, что P0-P3 правильно упорядочены, то необходимо проверить признаки тройных произведений для всех триплетов всех граней вершин

Если многоугольник вогнутый, вам нужна точка возле заданной грани, но лежащая внутри многогранника. Например, выберите любой триплет последовательных вершин с острым внутренним углом, возьмите центр треугольника и сдвиньте этот центр по нормали на небольшое расстояние. Убедитесь, что смещенная точка находится внутри, иначе сделайте отражение