1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

import cv2
import numpy as np
import random
# 检查一个点是否在矩形内
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_point(img, p, color ) :
    cv2.circle( img, p, 2, color, 2)
# 绘制 delaunay 三角剖分
def draw_delaunay(img, subdiv, delaunay_color ) :
    triangleList = subdiv.getTriangleList()
    size = img.shape
    r = (0, 0, size[1], size[0])
    for t in triangleList :
        pt1 = (int(t[0]), int(t[1]))
        pt2 = (int(t[2]), int(t[3]))
        pt3 = (int(t[4]), int(t[5]))
        if rect_contains(r, pt1) and rect_contains(r, pt2) and rect_contains(r, pt3) :
            cv2.line(img, pt1, pt2, delaunay_color, 1)
            cv2.line(img, pt2, pt3, delaunay_color, 1)
            cv2.line(img, pt3, pt1, delaunay_color, 1)
# 绘制 voronoi 图
def draw_voronoi(img, subdiv) :
    ( facets, centers) = subdiv.getVoronoiFacetList([])
    for i in range(0,len(facets)) :
        ifacet_arr = facets[i]
        center = centers[i].astype('int32')
        ifacet = np.array(ifacet_arr)
        color = (random.randint(0, 255), random.randint(0, 255), random.randint(0, 255))
        cv2.fillConvexPoly(img, ifacet.astype('int32'), color)
        ifacets = np.array([ifacet])
        cv2.polylines(img, ifacets.astype('int32'), True, (0, 0, 0), 1)
        cv2.circle(img, (center[0], center[1]), 3, (0, 0, 0), 1)
if __name__ == '__main__':
    win_delaunay = "Delaunay Triangulation"
    win_voronoi = "Voronoi Diagram"
    # 当绘制三角形剖分时打开动画画板
    animate = True
    # 定义绘制颜色
    delaunay_color = (255,255,255)
    points_color = (0, 0, 255)
    img = np.zeros([500,500,3],dtype=np.uint8)
    img_orig = img.copy()
    # 创建用于Subdiv2D 的矩形
    size = img.shape
    rect = (0, 0, size[1], size[0])
    # 创建Subdiv2D 实例
    subdiv = cv2.Subdiv2D(rect)
    points = []
    points.append((100, 100))
    points.append((100, 200))
    points.append((200, 100))
    points.append((200, 200))
    points.append((200, 300))
    points.append((400, 400))
    points.append((300, 400))
    # 将点依次插入subdiv中
    for p in points :
        subdiv.insert(p)
        # 展示动画画板
        if animate :
            img_copy = img_orig.copy()
            draw_delaunay(img_copy, subdiv, (255, 255, 255))
            cv2.imshow(win_delaunay, img_copy)
            cv2.waitKey(400)
    # 绘制delaunay 三角剖分
    draw_delaunay( img, subdiv, (255, 255, 255) )
    for p in points :
        draw_point(img, p, (0,0,255))
    # 为Voronoi 图分配空间
    img_voronoi = np.zeros(img.shape, dtype = img.dtype)
    # 绘制 Voronoi 图
    draw_voronoi(img_voronoi,subdiv)
    cv2.imshow(win_delaunay,img)
    cv2.imshow(win_voronoi,img_voronoi)
    cv2.waitKey(0)