Thread: c++ triangulation problem

  1. #1
    Registered User
    Join Date
    Dec 2007
    Posts
    23

    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

  2. #2
    Registered User
    Join Date
    Oct 2009
    Location
    While(1)
    Posts
    377
    I dont think so writing an alogo in C++ for this will be tougher why u r searchin for a lib

  3. #3
    3735928559
    Join Date
    Mar 2008
    Location
    RTP
    Posts
    838
    Code:
    #include <math.h>
    that should have all the trig functions you need.

  4. #4
    i've lost my mind
    Join Date
    Jun 2008
    Posts
    26
    #include <cmath>, not <math.h>.

    /me points at forum title.

  5. #5
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    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.

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #7
    Registered User
    Join Date
    Dec 2007
    Posts
    23
    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

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    As I suspected, you'll need to find a variant of the Convex-Hull Algorithm.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  9. #9
    Registered User
    Join Date
    Dec 2007
    Posts
    23
    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..?

  10. #10
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  11. #11
    Registered User
    Join Date
    Sep 2007
    Posts
    4
    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.

  12. #12
    Registered User
    Join Date
    Dec 2007
    Posts
    23
    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?

  13. #13
    3735928559
    Join Date
    Mar 2008
    Location
    RTP
    Posts
    838
    well, this is quite an interesting problem afterall!

  14. #14
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by m37h0d View Post
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  15. #15
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    I just looked up "Delaunay Triangulation" and it seems to be exactly what you want.
    What more do you need us for?!
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help understanding a problem
    By dnguyen1022 in forum C++ Programming
    Replies: 2
    Last Post: 04-29-2009, 04:21 PM
  2. Memory problem with Borland C 3.1
    By AZ1699 in forum C Programming
    Replies: 16
    Last Post: 11-16-2007, 11:22 AM
  3. Someone having same problem with Code Block?
    By ofayto in forum C++ Programming
    Replies: 1
    Last Post: 07-12-2007, 08:38 AM
  4. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 02:51 PM
  5. WS_POPUP, continuation of old problem
    By blurrymadness in forum Windows Programming
    Replies: 1
    Last Post: 04-20-2007, 06:54 PM