A tool for visualising Delaunay triangulation. Upload an image (line 139) and choose some points by clicking on it. "Triangulate" button builds Delaunay triangulation on the selected points. "Restart" button clears the canvas.

Triangulation.py

import pygame
import math
pygame.init()


def cos(edge, point):
    pe1 = [edge[0][0] - point[0], edge[0][1] - point[1]]
    pe2 = [edge[1][0] - point[0], edge[1][1] - point[1]]
    return round((pe1[0] * pe2[0] + pe1[1] * pe2[1])/math.dist(edge[0], point)/math.dist(edge[1], point), 14)


def sin(edge, point):
    pe1 = [edge[0][0] - point[0], edge[0][1] - point[1]]
    pe2 = [edge[1][0] - point[0], edge[1][1] - point[1]]
    return round(abs(pe1[1] * pe2[0] - pe1[0] * pe2[1])/math.dist(edge[0], point)/math.dist(edge[1], point), 14)


def delaunay_correct(edge, p1, p2):
    sin1 = sin(edge, p1)
    cos1 = cos(edge, p1)
    sin2 = sin(edge, p2)
    cos2 = cos(edge, p2)
    return sin1 * cos2 + sin2 * cos1 >= 0


def cross_product(vector1, vector2):
    x1, y1 = vector1[1][0] - vector1[0][0], vector1[1][1] - vector1[0][1]
    x2, y2 = vector2[1][0] - vector2[0][0], vector2[1][1] - vector2[0][1]
    return x1 * y2 - x2 * y1


def sweep_line(points):
    if len(points) < 3:
        return {}
    points = list(set(points))
    points.sort()
    triangulation = {}
    convex_hull = {}
    p0, p1, p2 = points[0], points[1], points[2]
    convex_hull[p1] = [p0]
    triangulation[(p0, p1)] = []
    prev = p1
    s = 2
    while s < len(points) and (p1[1] - p0[1]) * (points[s][0] - p0[0]) == (points[s][1] - p0[1]) * (p1[0] - p0[0]):
        triangulation[(prev, points[s])] = []
        convex_hull[prev].append(points[s])
        convex_hull[points[s]] = [prev]
        prev = points[s]
        s += 1
    if s == 2:
        triangulation[(p0, p1)] = [p2]
        triangulation[(p0, p2)] = [p1]
        triangulation[(p1, p2)] = [p0]
        if cross_product((p2, p0), (p1, p0)) > 0:
            convex_hull[p0] = [p1, p2]
            convex_hull[p1] = [p2, p0]
            convex_hull[p2] = [p0, p1]
        else:
            convex_hull[p0] = [p2, p1]
            convex_hull[p1] = [p0, p2]
            convex_hull[p2] = [p1, p0]
        s += 1
    else:
        convex_hull[p0] = [points[s-1], p1]
        convex_hull[points[s-1]].append(p0)
        if s < len(points):
            if cross_product((points[s], p0), (points[s], p1)) < 0:
                for key, val in convex_hull.items():
                    convex_hull[key] = val[::-1]
                convex_hull[points[s]] = [p0, points[s-1]]
                convex_hull[p0][1] = points[s]
                convex_hull[points[s-1]][0] = points[s]
            else:
                convex_hull[points[s]] = [points[s-1], p0]
                convex_hull[p0][0] = points[s]
                convex_hull[points[s-1]][1] = points[s]
            edge1, edge2 = (p0, points[s]), (points[s-1], points[s])
            triangulation[edge1] = [p1]
            triangulation[edge2] = [points[s-2]]
            for j in range(1, s - 1):
                triangulation[(points[j], points[s])] = [points[j-1], points[j+1]]
            for k in range(1, s):
                triangulation[(points[k-1], points[k])].append(points[s])
        s += 1    
    
    
    for i in range(s, len(points)):
        point = points[i]
        visible_points = [points[i-1]]
        last = points[i-1]
        right = convex_hull[last][1]
        while right != point and cross_product((last, point), (right, point)) < 0:
            visible_points.append(right)
            last, right = right, convex_hull[right][1]
        last = points[i-1]
        left = convex_hull[last][0]
        while left != point and cross_product((last, point), (left, point)) > 0:
            visible_points = [left] + visible_points[::]
            last, left = left, convex_hull[left][0]
        for elem in visible_points[1:-1]:
            convex_hull.pop(elem)
        convex_hull[visible_points[0]][1] = point
        convex_hull[visible_points[-1]][0] = point
        convex_hull[point] = [visible_points[0], visible_points[-1]]
        edge1, edge2 = tuple(sorted([visible_points[0], point])), tuple(sorted([visible_points[-1], point]))
        triangulation[edge1] = [visible_points[1]]
        triangulation[edge2] = [visible_points[-2]]
        for j in range(1, len(visible_points) - 1):
            triangulation[tuple(sorted([visible_points[j], point]))] = [visible_points[j-1], visible_points[j+1]]
        for k in range(1, len(visible_points)):
            edge = tuple(sorted([visible_points[k-1], visible_points[k]]))
            triangulation[edge].append(point)
            edges = [[edge, point]]
            while len(edges) > 0:
                cur = edges.pop(0)
                cur_edge = cur[0]
                if len(triangulation[cur_edge]) == 2 and not delaunay_correct(cur_edge, triangulation[cur_edge][0], triangulation[cur_edge][1]):
                    e1, e2, p1 = cur_edge[0], cur_edge[1], cur[1]
                    if triangulation[cur_edge][0] == p1:
                        p2 = triangulation[cur_edge][1]
                    else:
                        p2 = triangulation[cur_edge][0]
                    triangulation[tuple(sorted([p1, p2]))] = [e1, e2]
                    triangulation.pop(cur_edge)
                    triangulation[tuple(sorted([e1, p2]))].remove(e2)
                    triangulation[tuple(sorted([e1, p2]))].append(p1)
                    triangulation[tuple(sorted([e1, p1]))].remove(e2)
                    triangulation[tuple(sorted([e1, p1]))].append(p2)
                    triangulation[tuple(sorted([e2, p1]))].remove(e1)
                    triangulation[tuple(sorted([e2, p1]))].append(p2)
                    triangulation[tuple(sorted([e2, p2]))].remove(e1)
                    triangulation[tuple(sorted([e2, p2]))].append(p1)
                    edges.append([tuple(sorted([e1, p2])), p1])
                    edges.append([tuple(sorted([e2, p2])), p1])
    return triangulation


pygame.init()
image = pygame.image.load(r'image.jpg') #choose an image from the file where this program is stored
screen = pygame.display.set_mode(image.get_size())
im_x, im_y = image.get_size()[0], image.get_size()[1]
font = pygame.font.SysFont('arial', (im_x + im_y) // 25)
objects = []
points = []
triangulation = {}


class Button():
    def __init__(self, x, y, width, height, buttonText='Button', onclickFunction=None, onePress=False):
        self.x = x
        self.y = y
        self.width = width
        self.height = height
        self.onclickFunction = onclickFunction
        self.onePress = onePress
        self.alreadyPressed = False

        self.fillColors = {
            'normal': '#ffffff',
            'hover': '#666666',
            'pressed': '#333333',
        }
        
        self.buttonSurface = pygame.Surface((self.width, self.height))
        self.buttonRect = pygame.Rect(self.x, self.y, self.width, self.height)
        self.buttonSurf = font.render(buttonText, True, (20, 20, 20))
        objects.append(self)


    def process(self):
        mousePos = pygame.mouse.get_pos()
        self.buttonSurface.fill(self.fillColors['normal'])
        if self.buttonRect.collidepoint(mousePos):
            self.buttonSurface.fill(self.fillColors['hover'])
            if pygame.mouse.get_pressed(num_buttons=3)[0]:
                self.buttonSurface.fill(self.fillColors['pressed'])
                if self.onePress:
                    self.onclickFunction()
                elif not self.alreadyPressed:
                    self.onclickFunction()
                    self.alreadyPressed = True
            else:
                self.alreadyPressed = False
        self.buttonSurface.blit(self.buttonSurf, 
                                [self.buttonRect.width/2 - self.buttonSurf.get_rect().width/2, 
                                 self.buttonRect.height/2 - self.buttonSurf.get_rect().height/2])
        screen.blit(self.buttonSurface, self.buttonRect)    


def triangulate():
    global triangulation
    triangulation = sweep_line(points)


def delete():
    global points
    global triangulation
    points = []
    triangulation = {}


button_build = Button(im_x * 0.05, im_y * 0.85, im_x // 3, im_y // 8, 'Triangulate', triangulate)
button_del = Button(im_x * 0.65, im_y * 0.85, im_x // 3, im_y // 8, 'Restart', delete)
running = True
while running:
    screen.fill((255, 255, 255))
    screen.blit(image, (0, 0))
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            running = False
        elif event.type == pygame.MOUSEBUTTONDOWN and not button_build.buttonRect.collidepoint(pygame.mouse.get_pos()):
            points.append(pygame.mouse.get_pos())
    for i in range(len(points)):
        pygame.draw.circle(screen, (0, 0, 0), points[i], 3)
    for object in objects:
        object.process()
    for key in triangulation.keys():
        pygame.draw.line(screen, (0, 0, 0), key[0], key[1], 2)
    pygame.display.flip()
pygame.quit()