Learn how to a build a cloud-first strategyRegister Now

x
Solved

# Concave polygon to triangles

Posted on 2009-04-16
Medium Priority
484 Views
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
Question by:DJ_AM_Juicebox
• 2

LVL 92

Accepted Solution

objects earned 2000 total points
ID: 24163186
0

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
0

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

## Featured Post

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