如何三角剖分凹多边形？
如何三角剖分凹多边形？
提问于 2020-01-02 21:07:47
我刚刚开始进行图形编程，并尝试使用opencv的Subdiv2D类对凹多边形进行三角剖分，该类实现了Delaunay算法。
下面的代码生成以下输出，其中红线标记生成的三角形。到目前一切尚好。然而，该算法还计算了多边形凹面部分的三角形。
我在这里做错了什么，我怎样才能防止这种行为？我没有找到可以传递给Subdiv2D函数的任何形式的约束。
我能想到的一种方法是计算每个三角形的质心，然后测试它是否在多边形内。但是..。这个阿尔法真的是这样吗？
# -*- 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()回答 1
Stack Overflow用户
发布于 2020-01-02 21:58:23
行27上的triangles = subdiv.getTriangleList()将生成4个三角形，包括不需要的三角形。
虽然不太理想，但将第32行的for t in triangles:更改为for t in triangles[:3]:将绘制除最后一个(不想要的)三角形之外的每个三角形。
完整代码：
# -*- 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()这虽然解决了问题，但并不理想。这个解决方案不考虑更多的三角形，只解决症状，而不是问题的根源。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/59570029
复制相关文章
相似问题
腾讯云开发者
