CODEWITHSUNDEEP
pythonopencvgeometrytriangulation
Thijser
Thijser

Reputation: 2633

How do I triangulate a polygon with holes without extra points

I am trying to triangulate a number of polygons such that the triangles do not add extra points. For the sake of keeping the question short I will be using 2 circles in each other, in reality these will be opencv contours, however the translation between the two is quite complex and the circles also show the problem.

So I have the following code (based on the example) in order to first get the circles and then triangulate them with the triangle project

import matplotlib.pyplot as plt
import numpy as np

import triangle as tr


def circle(N, R):
    i = np.arange(N)
    theta = i * 2 * np.pi / N
    pts = np.stack([np.cos(theta), np.sin(theta)], axis=1) * R
    seg = np.stack([i, i + 1], axis=1) % N
    return pts, seg


pts0, seg0 = circle(30, 1.4)
pts1, seg1 = circle(16, 0.6)
pts = np.vstack([pts0, pts1])
seg = np.vstack([seg0, seg1 + seg0.shape[0]])
print(pts)
print(seg)
A = dict(vertices=pts, segments=seg, holes=[[0, 0]])
print(seg)
B = tr.triangulate(A) #note that the origin uses 'qpa0.05' here
tr.compare(plt, A, B)
plt.show()

Now this causes both the outer and inner circles to get triangulated like show here:

2 circles

...clearly ignoring the hole. However by setting the 'qpa0.05' flag we can cause the circle to use the hole as seen here:

enter image description here

However doing this causes the triangles to be split, adding many different triangles, increasing the qpa to a higher value does cause the number of triangles to be somewhat decreased, however they remain there.

Note that I want to be able to handle multiple holes in the same shape, and that shapes might end up being concave.

Anybody know how to get the triangulation to use the holes without adding extra triangles?

Upvotes: 2

Views: 1847

Answers (2)

Thijser
Thijser

Reputation: 2633

I figured it out the "qpa0.05" should have been a 'p', the p makes the code factor in holes and the a sets the maximum area for the triangles, this causes the extra points to be added.

B = tr.triangulate(A,'p')

Upvotes: 2

aerobiomat
aerobiomat

Reputation: 3437

You can connect the hole (or holes) to the exterior perimeter so that you get a single "degenerate polygon" defined by a single point sequence that connects all points without self-intersection.

You go in and out through the same segment. If you follow the outer perimeter clockwise, you need to follow the hole perimeter counterclockwise or vice-versa. Otherwise, it would self-intersect.

Upvotes: 1

Related Questions