Connected lines 2 polygon algorithm?
Author
Hullo!
I've been working on an algorithm for converting a series of connected lines, or vertices, into a triangular patch. If the connected lines define a convex region this is relatively simple to do but it's quite complex when it comes to non-convex thingies.
I've managed to create something that works quite well, but it's kind of slow... it involves starting with two vertices and testing which third vertex will make a triangle not overlapping any already created triangle that is still inside the original body being converted, this is repeated until a good match is found. I also use some basic culling so that vertices which cannot be part of any new triangle are removed from the list of vertices being concidered.
Anyway, I was wondering if there is a well-known algorithm for building a non-overlapping triangular mesh from a set of lines, or if there is perhaps some better approach I can use instead... i.e. rendering polygons with OpenGL. I tried rendering my lines as polygonal patches in OpenGL but it didn't work and I've read that GL_POLYGON only supports convex polygons. Maybe there is a way to easily divide a non-convex polygon into convex sub-polygons?
The operation you're talking about is called Triangulation. If you look for papers about it you'll find that easily coded algorithms typically run in O(n^2) where n is the number of vertices. Good (hard to code) algorithms run in O(nlogn) or o(nlogn), and there is one theoretical algorithm (impossible to code) that runs in O(n).
One algorithm that I have coded, which is fairly robust keeps a linked list of vertices that surround the untriangulated region (so it starts off containing all of the vertices of the polygon in the order which they surround the region). Then you take three adjacent vertices and check that the triangle they form is valid (contains no other vertices in the set). If that triangle is invalid, you move forward one and try the next three adjacent vertices, if the triangle is valid, you add it to the triangle list, and remove the middle of the three vertices from the untriangulated region list. Stop when you have only three vertices left in the linked list (don't forget to add that triangle though).
This algorithm runs in O(n^2), but has very low overhead, and is very very easy to code.
Good luck!
One algorithm that I have coded, which is fairly robust keeps a linked list of vertices that surround the untriangulated region (so it starts off containing all of the vertices of the polygon in the order which they surround the region). Then you take three adjacent vertices and check that the triangle they form is valid (contains no other vertices in the set). If that triangle is invalid, you move forward one and try the next three adjacent vertices, if the triangle is valid, you add it to the triangle list, and remove the middle of the three vertices from the untriangulated region list. Stop when you have only three vertices left in the linked list (don't forget to add that triangle though).
This algorithm runs in O(n^2), but has very low overhead, and is very very easy to code.
Good luck!
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
