如何計算Bowyer-Watson算法中的一組點的超三角形？

Question

首先，對不起我的英文不好。按照我的問題，在Bowyer-Watson算法中，我們必須找到一個超三角形環繞的所有點。但是，我們如何計算該超三角形的3個垂直座標（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喜歡什麼讓你最終跟蹤的要點。