Concave polygon to triangles

Posted on 2009-04-16
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
    LVL 92

    Accepted Solution

    LVL 84

    Expert Comment

    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 84

    Expert Comment

    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

    Free Trending Threat Insights Every Day

    Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

    Join & Write a Comment

    Suggested Solutions

    What is RenderMan: RenderMan is a not any particular piece of software. RenderMan is an industry standard, defining set of rules that any rendering software should use, to be RenderMan-compliant. Pixar's RenderMan is a flagship implementation of …
    Introduction This article is the first of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article explains our test automation goals. Then rationale is given for the tools we use to a…
    Viewers learn about the “while” loop and how to utilize it correctly in Java. Additionally, viewers begin exploring how to include conditional statements within a while loop and avoid an endless loop. Define While Loop: Basic Example: Explanatio…
    Viewers will learn about if statements in Java and their use The if statement: The condition required to create an if statement: Variations of if statements: An example using if statements:

    728 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

    Need Help in Real-Time?

    Connect with top rated Experts

    18 Experts available now in Live!

    Get 1:1 Help Now