This is harder than I thought it was going to be. It took me about an hour to write this, and it seems to work. If you find an example where it doesn't, please let me know.
#include <iostream>#include <vector>struct Point2D { double x,y; Point2D(double x, double y):x(x),y(y){ }};/* The next two functions are from Segdewick's "Algorithms in ..." books */int ccw(Point2D const &p0, Point2D const &p1, Point2D const &p2){ double dx1 = p1.x - p0.x; double dy1 = p1.y - p0.y; double dx2 = p2.x - p0.x; double dy2 = p2.y - p0.y; if(dx1*dy2 > dy1*dx2) return +1; if(dx1*dy2 < dy1*dx2) return -1; if((dx1*dx2 < 0) || (dy1*dy2 < 0)) return -1; if((dx1*dx1+dy1*dy1) < (dx2*dx2+dy2*dy2)) return +1; return 0;}bool intersect(Point2D const &l1_p1, Point2D const &l1_p2, Point2D const &l2_p1, Point2D const &l2_p2){ return ((ccw(l1_p1, l1_p2, l2_p1) *ccw(l1_p1, l1_p2, l2_p2)) <= 0) && ((ccw(l2_p1, l2_p2, l1_p1) *ccw(l2_p1, l2_p2, l1_p2)) <= 0);}struct Polygon : std::vector<Point2D> { unsigned next_vertex(unsigned vertex) const { ++vertex; if(vertex==size()) vertex=0; return vertex; }};std::vector<Polygon> split(Polygon const &p){ std::vector<Polygon> result; unsigned n=p.size(); if(n==3){ result.push_back(p); return result; } unsigned a=0,b=1,c=2; do{ if(ccw(p[a],p,p[c])<0) goto non_convex; a=b,b=c,c=p.next_vertex(c); }while(a!=0); for(unsigned i=2;i<n;++i){ Polygon triangle; triangle.push_back(p[0]); triangle.push_back(p[i-1]); triangle.push_back(p); result.push_back(triangle); } return result; non_convex: unsigned o=p.next_vertex(c); for(unsigned i=p.next_vertex(o);i!=a;i=p.next_vertex(i)){ if(i==o || !intersect(p,p[o],p,p[p.next_vertex(i)])) continue; if(ccw(p,p[o],p)<=0) o=i; else o=p.next_vertex(i); } Polygon sub_p; for(unsigned i=b;i!=o;i=p.next_vertex(i)) sub_p.push_back(p); sub_p.push_back(p[o]); std::vector<Polygon> sub_triangulation=split(sub_p); for(unsigned i=0;i<sub_triangulation.size();++i) result.push_back(sub_triangulation); sub_p.erase(sub_p.begin(),sub_p.end()); for(unsigned i=o;i!=b;i=p.next_vertex(i)) sub_p.push_back(p); sub_p.push_back(p); sub_triangulation=split(sub_p); for(unsigned i=0;i<sub_triangulation.size();++i) result.push_back(sub_triangulation); return result;}int main(){ Polygon p; p.push_back(Point2D(4,0)); p.push_back(Point2D(10,4)); p.push_back(Point2D(5,2)); p.push_back(Point2D(7,7)); p.push_back(Point2D(3,6)); p.push_back(Point2D(6,5)); p.push_back(Point2D(0,5)); p.push_back(Point2D(1,1)); p.push_back(Point2D(4,4)); std::vector<Polygon> triangulation = split(p); for(unsigned i=0;i<triangulation.size();++i){ Polygon p=triangulation; for(unsigned j=0;j<p.size();++j) std::cout << ", "+2*(j==0) << '(' << p[j].x << ',' << p[j].y << ')'; std::cout << std::endl; }}
What method would be best to connect the vertices so that the interior of the shape was filled up with tesselating triangles? eg:
At first I thought only the vertices mattered, and some simple algorithm could just taking each vertex one by one and connecting it to another vertex, making sure that triangles don't overlap. But the shape can be concave:
Which leads to a few additional complications because some triangles created between vertices would be invalid:
I have noticed that for N vertices N-2 triangles must be created to fill the interior of the 2D region. That's about the only nice consistant thing I have found in this problem.
I am eventually looking for a nice simple algorithm (not necessarily a fast one). You know the kind you hit yourself on the head and go "argh why didnt I think of that". One of the sub-problems that I am interested in is: given any 3 of the vertices, how can you tell whether the triangle formed by those vertices falls inside, outside, or overlaps the bounded shape. I think that's at least half the battle. Of course I could do something nasty like use segment intersection tests all over the place, but that's precisely the kind of thing im trying to avoid..if I can. If anyone spots any useful starting ideas that would be very helpful!
The reason I am after a solution for this problem is to use it to automatically fill in holes in a 3D mesh after a vertex has been removed. The vertices will be removed if the triangles they are connected to are relatively coplanar. Ie this is to be used to reduce redundant triangles in a model.
