Learn how to a build a cloud-first strategyRegister Now

x
?
Solved

Concave polygon to triangles

Posted on 2009-04-16
3
Medium Priority
?
484 Views
Last Modified: 2013-12-26
Hi,

I have a 2d concave polygon, defined as a list of x,y points. I want to decompose it into a set of triangles. Is there some pre-made algorithm already written in java/c/c++ anyone knows of that will do this for me?

Thanks
0
Comment
Question by:DJ_AM_Juicebox
  • 2
3 Comments
 
LVL 92

Accepted Solution

by:
objects earned 2000 total points
ID: 24163186
0
 
LVL 85

Expert Comment

by:ozo
ID: 24164154
If the polygon is not self intersecting, there should be at least one pair of adjacent edges with interior angle less than 180 degrees and with no other vertices contained within the triangle formed by those edges.
Remove that triangle, and replace the two edges with a new edge joining the end points to form a new polygon.
repeat until you are down one triangle
0
 
LVL 85

Expert Comment

by:ozo
ID: 24171065
A Delaunay triangulation of the vertices of a concave polygon can contain triangles that are outside of the polygon.
Is that what you wanted?.
0

Featured Post

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

In this post we will learn how to make Android Gesture Tutorial and give different functionality whenever a user Touch or Scroll android screen.
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
Viewers will learn about the regular for loop in Java and how to use it. Definition: Break the for loop down into 3 parts: Syntax when using for loops: Example using a for loop:
This tutorial covers a step-by-step guide to install VisualVM launcher in eclipse.
Suggested Courses
Course of the Month21 days, 7 hours left to enroll

810 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question