How to triangulate a concave polygon?

Question

I am just getting started with graphical programming and try to triangulate a concave polygon using opencv's Subdiv2D class which implements the Delaunay algorithm.

My code further bellow produces the following output, where the red lines mark the generated triangles. So far so good. However the algorithm also calculated a triangle for the part of the polygon which is concave.

What am I doing wrong here and how can I prevent that behaviour? I didn't find any form of constraints I could pass to the Subdiv2D functions.

One approach I could think of is the calculation of each triangles centroid and then test if its inside the polygon. But... is this really the way to go with this algo?

# -*- coding: utf-8 -*-
import numpy as np
import cv2

width = 800
height = 600
img = np.zeros((height,width,3), np.uint8)
pts = np.array([[100,50],[200,300],[700,200],[500,100],[400,150]], np.int32)
rect = (0, 0, width, height)

def rect_contains(rect, point) :
    if point[0] <rect[0] : 
        return False
    elif point[1] < rect[1] : 
        return False
    elif point[0] > rect[2] :
        return False
    elif point[1] > rect[3] : 
        return False
    return True

def draw_triangeles(rect, points, img) :
    subdiv = cv2.Subdiv2D()
    subdiv.initDelaunay(rect)

    for p in points:
        subdiv.insert((p[0], p[1]))

    triangles = subdiv.getTriangleList()

    for t in triangles:
        pt1 = (t[0], t[1])
        pt2 = (t[2], t[3])
        pt3 = (t[4], t[5])

        if rect_contains(rect, pt1) and rect_contains(rect, pt2) and rect_contains(rect, pt3) :
            cv2.line(img, pt1, pt2, (0,0,255), 2)
            cv2.line(img, pt2, pt3, (0,0,255), 2)
            cv2.line(img, pt3, pt1, (0,0,255), 2)

def draw_points(points, img):
    for p in points:
        cv2.circle(img, (p[0], p[1]), 2, (255,255,255), 2)

# Draw polygon    
cv2.fillPoly(img, [pts], (0, 255, 0))

# Draw result of triangulation
draw_triangeles(rect, pts, img)

# Draw vertices on top 
draw_points(pts, img)

#hull = cv2.convexHull(pts)
#cv2.polylines(img, [hull], True, (0, 255, 0))

cv2.imshow("image", img)
cv2.waitKey()
cv2.destroyAllWindows()

I think the standard algorithm is to first decompose your concave polygon into multiple convex polygons, then triangulate each separately. See stackoverflow.com/questions/694108/…, for example. — chepner
Thx for replying. It seems I have wrong understanding for what triangulation can be used for. My idea was exactly that, to decompose a concave polygon into several concave ones (triangles). — Matthias Güntert
You can triangulate any n-gon into n-2 triangles; for efficiency (or at least simplicity), most algorithms assume a convex polygon. (More precisely, triangulation algorithms are simply defined for arbitrary sets of points, whose convex hull implies a particular convex polygon.) — chepner

Tc001 Tc001 · Accepted Answer · 2020-01-02T21:58:23

triangles = subdiv.getTriangleList() on line 27 will generate 4 triangles, including the unwanted one.

Although not ideal, changing for t in triangles: to for t in triangles[:3]: on line 32 will draw every triangle except the last(unwanted) one.

Full code:

# -*- coding: utf-8 -*-
import numpy as np
import cv2

width = 800
height = 600
img = np.zeros((height,width,3), np.uint8)
pts = np.array([[100,50],[200,300],[700,200],[500,100],[400,150]], np.int32)
rect = (0, 0, width, height)

def rect_contains(rect, point) :
    if point[0] <rect[0] :
        return False
    elif point[1] < rect[1] :
        return False
    elif point[0] > rect[2] :
        return False
    elif point[1] > rect[3] :
        return False
    return True

def draw_triangeles(rect, points, img) :
    subdiv = cv2.Subdiv2D()
    subdiv.initDelaunay(rect)

    for p in points:
        subdiv.insert((p[0], p[1]))


    triangles = subdiv.getTriangleList()

    for t in triangles[:3]:
        pt1 = (t[0], t[1])
        pt2 = (t[2], t[3])
        pt3 = (t[4], t[5])

        if rect_contains(rect, pt1) and rect_contains(rect, pt2) and rect_contains(rect, pt3) :
            cv2.line(img, pt1, pt2, (0,0,255), 2)
            cv2.line(img, pt2, pt3, (0,0,255), 2)
            cv2.line(img, pt3, pt1, (0,0,255), 2)

def draw_points(points, img):
    for p in points:
        cv2.circle(img, (p[0], p[1]), 2, (255,255,255), 2)

# Draw polygon
cv2.fillPoly(img, [pts], (0, 255, 0))

# Draw result of triangulation
draw_triangeles(rect, pts, img)

# Draw vertices on top
draw_points(pts, img)

#hull = cv2.convexHull(pts)
#cv2.polylines(img, [hull], True, (0, 255, 0))

cv2.imshow("image", img)
cv2.waitKey()
cv2.destroyAllWindows()

Although this solves the problem, it is not ideal. This solution does not account for more triangles, and only solves the symptoms, not the root of the problem.

How to triangulate a concave polygon?

1 Answers