Как рассчитать супертригулярное окружение множества точек в алгоритме Бойера-Ватсона?

Question

Во-первых, извините за мой плохой английский. Следуйте моему вопросу, в алгоритме Бойера-Ватсона, мы должны найти супер-треугольное окружение всех точек. Но как мы можем вычислить координатор (x, y) трех вершин этого супертреугольного? У кого-нибудь есть функция для этого? Огромное спасибо.

Answer 1

У меня нет доказательства для этого, но то, что первое приходит на ум, это делает что-то с получением convex hull вашего набора точек

1. Get the convex hull of the group of points. 
2. Initialize the variable smallest = infinity. 
3. For each point P in convex hull do the following: 
     Find the point farthest away from P call it Q. 
     Set N1 = point to the left of P (counter-clockwise along convex hull). 
      N2 = point to the right of P (clockwise along convex hull). 
      L1 = line that intersects Q and is perpendicular to the line PQ. 
      L2 = line that intersects P and N1. 
      L3 = line that intersects P and N2. 
      A = area of the triangle thats formed by the intersections of L1,L2,L3. 
     If A < smallest, then set smallest = A. 
4. Return smallest 

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

class Triangle{ 
    Point p1; 
    Point p2; 
    Point p3; 
    double Area; 
    //etc... 
} 

и изменить smallest нравится или что-то, так что вы в конечном итоге отслеживания точек.