c++ triangulation problem

hi,

i am trying to solve to following problem:
out of a given number of vertices i need to calculate
a triangulation and receive the edges.
is there any library that would help to achieve this, or
can you give me any hint on this?

thanks,

toby

I dont think so writing an alogo in C++ for this will be tougher why u r searchin for a lib :)

Code:

---

#include <math.h>

---

that should have all the trig functions you need.

#include <cmath>, not <math.h>.

/me points at forum title. :p

You can calculate triangulation given the edges of the primitive in several ways. It is a simple matter if the primitive is convex and can be done by selecting one vertex and then creating edges between it and all the other vertices. This would be a brute force approach but it works and it can also be drawn via a triangle fan which is faster than a triangle list.

Are the verticies ordered (as in a polygon), or are there just a bunch of them which you first need to convert into a polygon using something like the convex-hull algorithm?
Then, as asked already, is the polygon convex or concave?

If the answer is convex then I'll consider your problem solved as per the above answers. Otherwise, let us know what you find by searching the web. We've just dropped plenty of things you can look up.

There are 4 verteces defining a rectangle, but within this rectangle, there is just a bunch of verteces at no specific order.
Could you give me a hint on how to solve this problem with <cmath>?

Thanks

As I suspected, you'll need to find a variant of the Convex-Hull Algorithm.

But if I am right, a complex-hull algorithm would just compute a hull around the whole group of verteces. Actually I am looking for a triangulation-algorithm for these verteces, though..?

A few Concave Hull Algorithm's see to also exist. A few links:
Concave Hull vs. Convex Hull
Andrew's Convex Hull Algorithm Demo
Such an algorithm has no perfect answer though. You're pretty much on your own to pick something that works well for you.

As far as I know cmath cannot do this for you. If you really wanna learn how to do this stuff buy a book on computational geometry such as Computational Geometry in C. The problem you will have with triangulation if it is not convex is you are not sure which vertices will contain a diagonal (obviously). Depending on what exactly your doing this for, I am not sure finding the convex hull will help you. Talking in just 2d, If you just have a bunch of random points you could come up with quite a few different polygons. So assuming you are receiving the polygons in ccw order and as you read in a vertice you connect it to the last one, and the final vertex read in connects to the first vertex. Now that you have a polygon, you go about it a few different ways. First you can just keep traversing around the polygon cutting off ears, which means your at a vertex, you check to see if you can draw a line between the two adjacent vertices, if so, then store the diagonal you found and then remove the vertex your are at from the polygon which is done by making the two adjacent vertices point to each other (think circular linked list). Just keep doing this until only one triangle is left. This is not the fastest approach, i think its n^2, but its a starting point for you.

If you want to get fancier you can break up the polygon into monotone mountains, i think that is done in nlogn, then you can triangulate each monotone mountain in linear time.

i am not exactly sure what you mean, but probably, there is a misunderstanding, so i think i'll just show you what i am trying to achieve (see file attached).

a bunch of vertices should be triangulated and as a result, i need to receive the faces and edges of the triangulation (not just the hull)... maybe this could be done using a delaunay triangulation?

well, this is quite an interesting problem afterall!

Quote:

---

Originally Posted by m37h0d

well, this is quite an interesting problem afterall!

---

Indeed!

They say a picture paints a thousand words, and that's certainly the case here!

Are you looking for just any solution, or an optimal one?

My mind is coming up with all sorts of ideas right now. The one that seems the most promising is to start with a set of lines that connect every point to every other point. Then find every pair of intersecting lines, and remove the longer of the two lines.

The only things left to do are to optimise it in terms of speed, and perhaps to optimise it towards making triangles that are closer to being equalateral, if desired. The greedy approach of picking the longest line to remove for each pair wouldn't produce the best outcome in every case. Perhaps sorting the intersecting pairs based on the ratio of the intersecting lines first would work well shape-wise. Get it working first, then go for speed.

I just looked up "Delaunay Triangulation" and it seems to be exactly what you want.
What more do you need us for?!