Skip to content

Instantly share code, notes, and snippets.

@AsyaMatveeva
AsyaMatveeva / Triangulation.py
Last active June 20, 2023 14:21
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.
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)
@AsyaMatveeva
AsyaMatveeva / Sweep line Delaunay triangulation algorithm
Last active June 20, 2023 14:57
Sweep line Delaunay triangulation algorithm.
import math
import random
from turtle import *
#returns the cosine of an angle at which an edge is visible from a given point
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)
import math
import random
from turtle import *
#returns the cosine of an angle at which an edge is visible from a given point
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)
@AsyaMatveeva
AsyaMatveeva / Linear_5_coloring.py
Created September 4, 2022 10:47
Linear algorithm for coloring a planar graph in 5 colors.
G = {0:{1:[3, 5], 3:[4, 1], 4:[5, 3], 5:[1, 4]},
1:{0:[2, 5], 2:[6, 0], 5:[1, 4], 6:[5, 2]},
2:{1:[3, 6], 3:[7, 1], 6:[1, 7], 7:[6, 3]},
3:{0:[4, 2], 2:[0, 7], 4:[7, 0], 7:[2, 4]},
4:{0:[3, 5], 3:[7, 0], 5:[0, 6], 6:[5, 7], 7:[6, 3]},
5:{0:[4, 1], 1:[0, 6], 4:[6, 0], 6:[1, 4]},
6:{1:[2, 5], 2:[7, 1], 4:[5, 7], 5:[1, 4], 7:[4, 2]},
7:{2:[6, 3], 3:[2, 4], 4:[3, 6], 6:[4, 2]}
}
@AsyaMatveeva
AsyaMatveeva / 6_coloring.py
Created September 4, 2022 10:46
Recursive algorithm for coloring a planar graph in 6 colors.
G = {0:[1, 2, 3, 4],
1:[0, 2, 4, 5],
2:[0, 1, 3, 5],
3:[0, 2, 4, 5, 6],
4:[0, 1, 3, 5, 6],
5:[1, 2, 3, 4, 6],
6:[3, 4, 5]
}
deg_5 = [] #список вершин со степенями не больше пяти
for key, val in G.items():
@AsyaMatveeva
AsyaMatveeva / Naive_5_coloring.py
Created September 4, 2022 10:45
Naive algorithm for coloring a planar graph in 5 colors.
G = {0:[1, 2, 3, 4, 5, 6],
1:[2, 0, 6],
2:[1, 0, 3],
3:[2, 0, 4],
4:[3, 0, 5],
5:[4, 0, 6],
6:[1, 0, 5]
}
deg_5 = [] #список вершин со степенями не больше пяти
for key, val in G.items():