Learn how to a build a cloud-first strategyRegister Now


Concave polygon to triangles

Posted on 2009-04-16
Medium Priority
Last Modified: 2013-12-26

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?

Question by:DJ_AM_Juicebox
  • 2
LVL 92

Accepted Solution

objects earned 2000 total points
ID: 24163186
LVL 85

Expert Comment

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
LVL 85

Expert Comment

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?.

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