Sign in to follow this  
RunningInt

Can anyone think of a nice way to solve this triangle filling problem?

Recommended Posts

RunningInt    133
Given a set of vertices connected in a ring to enclose a bounded 2D region: 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.

Share this post


Link to post
Share on other sites
SuperNerd    100
An invalid triangle will either have one of the sides intersect any of the original line segments on the shape or will intersect the original lines segments an odd number of times when extended infanatly.

Share this post


Link to post
Share on other sites
Zipster    2359
Any decent algorithm that isn't super logic-heavy or hopelessly riddled with special and/or degenerate cases will probably involve line tests, since they're simple and robust. From there, it's just a matter of doing something like sweeping for convex polygons, only checking for intersections and reverse sweep directions.

Share this post


Link to post
Share on other sites
mooserman352    168
what about trying something like this:
(assume you have the vertices named V1 to Vn, so that any Ax is connected to Vx and Vx+1 [you know what i mean])

So pick three consecutive vertices, see if they form a triangle and if the barycenter of the triangle lies inside of the initial polygon. If not, move to the next 3 vertices.

If so, remove this triangle from the initial polygon (essentially drop the middle coordinate), and do the process again with the reduced polygon, until you are done.

I haven't tried this, but i think it should work for non-degenerate polygons, since it seems to me intuitively (though i haven't proven it) that such a triangle should exist for any polygon, and removing such a triangle from the polygon also results in a nondegenerate polygon.

Share this post


Link to post
Share on other sites
alvaro    21246
Quote:
Original post by mooserman352
what about trying something like this:
(assume you have the vertices named V1 to Vn, so that any Ax is connected to Vx and Vx+1 [you know what i mean])

So pick three consecutive vertices, see if they form a triangle and if the barycenter of the triangle lies inside of the initial polygon. If not, move to the next 3 vertices.

If so, remove this triangle from the initial polygon (essentially drop the middle coordinate), and do the process again with the reduced polygon, until you are done.


That won't work. Three consecutive points whose barycenter is inside the polygon don't necessarily form a triangle completely contained in the polygon. Think of a non-convex 4-side polygon for an example of how this may not work.

What you can do is find a vertex where the polygon is concave (if there are none, you have a convex polygon and any simple triangulation attempt will work). From this vertex you can always find another vertex such that the line between them is completely contained in the polygon. Split the polygon in two using that line and iterate on both sides. That's about the best algorithm I can think of (I have thought about this problem before, but I haven't done any serious research about it).

Share this post


Link to post
Share on other sites
mooserman352    168
good catch. [nope, nevermind]

there should be an easy test to see if three consecutive vertices are locally convex. perhaps crossing some combination of the edges will do it?

[Edited by - mooserman352 on November 7, 2006 9:37:36 PM]

Share this post


Link to post
Share on other sites
Bob Janova    769
I think splitting the poly into guaranteed convex ones and then triangulating each of those would be the best way. You should be able to find poly-splitting (is this 'tesselation'?) algorithms relatively easily.

Share this post


Link to post
Share on other sites
alvaro    21246
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[b],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[i]);
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[b],p[o],p[i],p[p.next_vertex(i)]))
continue;
if(ccw(p[b],p[o],p[i])<=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[i]);
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[i]);
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[i]);
sub_p.push_back(p[b]);
sub_triangulation=split(sub_p);
for(unsigned i=0;i<sub_triangulation.size();++i)
result.push_back(sub_triangulation[i]);
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[i];
for(unsigned j=0;j<p.size();++j)
std::cout << ", "+2*(j==0) << '(' << p[j].x << ',' << p[j].y << ')';
std::cout << std::endl;
}
}



Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this