三角測量算法

Question

我決定創建一個簡單的演示，將多邊形分成三角形集。這裏我到目前爲止：

給出了一個連續頂點列表（P1）形成多邊形邊（多邊形在大多數情況下不是凸的）;三角形組在多邊形P1內需要

循環遍歷所有頂點並找到一個（V），將滿足下子句：從多邊形

1. 刪除v和保存新一個到P2先前頂點到連接到它的下一個一個V- 形成不交叉任何的P2 邊緣的 線

2. v不是內部P2

如果這些得到滿足，我們可以將其替換P1（P2 + 三角形（prev（V），V，未來（V））），直到P1包含超過3個頂點重複此動作。

所以，問題是：這個算法是否正確，以及如何使用C/C++使用最明顯和最簡單的方式來實現？

Answer 1

我想你在描述ear clipping method。該方法的代碼爲http://cs.smith.edu/~orourke/books/ftp.html;這是書Computational Geometry in C中描述的代碼。

Answer 2

似乎我完成了這個算法的實現。請驗證它是否有人。謝謝！

typedef struct Point 
{ 
    float x, y; 
}; 

class MooPolygon 
{ 
    private: 
     vector<Point> points; 

     int isVertexEar(int n, const vector<Point> &p) 
     { 
      return (isVertexInsideNewPoly(n, p) && !isEdgeIntersect(n, p)); 
     } 

     int isEdgeIntersect(int n, const vector<Point> &p) 
     { 
      Point v = p[n]; 
      vector<Point> a; 

      for (size_t i = 0; i < p.size(); i++) 
       if (i != n) 
        a.push_back(p[i]); 

      int c = 0, cnt = a.size(), prev = (cnt + (n - 1)) % cnt, next = n % cnt; 

      Point v1 = a[prev], v2 = a[next]; 

      for (size_t i = 0, j = cnt - 1; i < cnt; j = i++) 
      { 
       if (prev == i || prev == j || next == i || next == j) 
        continue; 

       Point v4 = a[j], v3 = a[i]; 

       float denominator = ((v4.y - v3.y) * (v2.x - v1.x)) - ((v4.x - v3.x) * (v2.y - v1.y)); 

       if (!denominator) 
        continue; 

       float ua = (((v4.x - v3.x) * (v1.y - v3.y)) - ((v4.y - v3.y) * (v1.x - v3.x)))/denominator; 
       float ub = (((v2.x - v1.x) * (v1.y - v3.y)) - ((v2.y - v1.y) * (v1.x - v3.x)))/denominator; 

       //float x = v1.x + (ua * (v2.x - v1.x)), y = v1.y + (ua * (v2.y - v1.y)); 

       if (ua >= 0 && ua <= 1 && ub >= 0 && ub <= 1) 
       { 
        c = 1; 
        break; 
       } 
      } 

      return c; 
     } 

     int isVertexInsideNewPoly(int n, const vector<Point> &p) 
     { 
      Point v = p[n]; 
      vector<Point> a; 

      for (size_t i = 0; i < p.size(); i++) 
       if (i != n) 
        a.push_back(p[i]); 

      int c = 1; 

      for (size_t i = 0, j = a.size() - 1; i < a.size(); j = i++) 
      { 
       if ((((a[i].y <= v.y) && (v.y < a[j].y)) || ((a[j].y <= v.y) && (v.y < a[i].y))) && (v.x > (a[j].x - a[i].x) * (v.y - a[i].y)/(a[j].y - a[i].y) + a[i].x)) 
        c = !c; 
      } 

      return c; 
     } 

     float dist(Point a, Point b) 
     { 
      return sqrt( ((a.x - b.x) * (a.x - b.x)) + (((a.y - b.y) * (a.y - b.y))) ); 
     } 

    public: 
     void push(const Point &p) 
     { 
      for (size_t i = 0; i < points.size(); i++) 
      { 
       if (dist(points[i], p) < 7.f) 
       { 
        points.push_back(points[i]); 

        return; 
       } 
      } 

      points.push_back(p); 
     } 

     void pop() 
     { 
      if (points.size() > 0) 
       points.pop_back(); 
     } 

     void clear() 
     { 
      points.clear(); 
     } 

     Point v(int index) 
     { 
      return points[index]; 
     } 

     size_t size() 
     { 
      return points.size(); 
     } 

     void triangulate() 
     { 
      vector<Point> a; 

      for (size_t i = 0; i < points.size(); i++) 
      { 
       a.push_back(points[i]); 
      } 

      points.clear(); 

      for (size_t t = a.size() - 1, i = 0, j = 1; i < a.size(); t = i++, j = (i + 1) % a.size()) 
      { 
       if (a.size() == 3) 
       { 
        points.push_back(a[0]); 
        points.push_back(a[1]); 
        points.push_back(a[2]); 

        break; 
       } 

       if (isVertexEar(i, a)) 
       { 
        points.push_back(a[t]); 
        points.push_back(a[i]); 
        points.push_back(a[j]); 

        a.erase(a.begin() + i, a.begin() + i + 1); 

        t = a.size() - 1; 
        i = 0; 
        j = 1; 
       } 
      } 
     } 
}; 

Answer 3

我還不能評論，所以我寫了這個答案。

我試過了代碼，它的工作原理，但我不得不糾正錯誤首先在下面的行。該生產線是在爲循環在你的類的推（）功能：

points.push_back(points[i]); 

你是不是經過點推，但矢量本身的空元素。我改行

points.push_back(p); 

它工作。