261 lines
8.1 KiB
Python
261 lines
8.1 KiB
Python
import pygame as pg
|
|
from math import sqrt, atan2, cos, sin, pi
|
|
import random
|
|
from dataclasses import dataclass
|
|
from collections import Counter
|
|
from itertools import pairwise
|
|
|
|
class Mover:
|
|
|
|
def __init__(self, point: pg.Vector2, bounds: pg.Rect, max_v: float = 500.0):
|
|
self.bounds = bounds
|
|
self.point = point
|
|
self.velocity = pg.Vector2(cos(random.random() * 2 * pi), sin(random.random() * 2 * pi)) * max_v
|
|
|
|
def move(self, dt):
|
|
self.point += dt * self.velocity
|
|
if self.point.x > self.bounds.right:
|
|
self.point.x = self.bounds.left + (self.point.x - self.bounds.right)
|
|
if self.point.x < self.bounds.left:
|
|
self.point.x = (self.bounds.right) - (self.bounds.left - self.point.x)
|
|
if self.point.y > self.bounds.bottom:
|
|
self.point.y = (self.bounds.top) - (self.bounds.bottom - self.point.y)
|
|
if self.point.y < self.bounds.top:
|
|
self.point.y = self.bounds.bottom + (self.point.y - self.bounds.top)
|
|
|
|
class ColorPoint(pg.Vector2):
|
|
|
|
def __init__(self, color: tuple[int,int,int], x: float, y: float):
|
|
self.color = color
|
|
super().__init__(x,y)
|
|
|
|
def __hash__(self):
|
|
return hash((self.x, self.y))
|
|
|
|
@dataclass
|
|
class Edge:
|
|
a: ColorPoint
|
|
b: ColorPoint
|
|
|
|
def __hash__(self):
|
|
return hash(frozenset((self.a, self.b)))
|
|
|
|
def __eq__(self, other: 'Edge') -> bool:
|
|
return (self.a == other.a and self.b == other.b) or (self.a == other.b and self.b == other.a)
|
|
|
|
@dataclass
|
|
class Circle:
|
|
center: ColorPoint
|
|
radius: float
|
|
|
|
def point_within(self, point: ColorPoint) -> bool:
|
|
return (self.center - point).length() <= self.radius + 1e-6
|
|
|
|
def draw(self, screen):
|
|
pg.draw.circle(
|
|
screen,
|
|
(255,0,0),
|
|
self.center,
|
|
self.radius,
|
|
width=1
|
|
)
|
|
pg.draw.circle(
|
|
screen,
|
|
(255,0,0),
|
|
self.center,
|
|
2
|
|
)
|
|
|
|
@dataclass
|
|
class Triangle:
|
|
a: ColorPoint
|
|
b: ColorPoint
|
|
c: ColorPoint
|
|
|
|
@property
|
|
def edges(self) -> tuple[Edge, Edge, Edge]:
|
|
return (Edge(self.a, self.b), Edge(self.b, self.c), Edge(self.c, self.a))
|
|
|
|
@property
|
|
def vertices(self) -> tuple[ColorPoint, ColorPoint, ColorPoint]:
|
|
return (self.a, self.b, self.c)
|
|
|
|
@property
|
|
def circumcircle(self) -> Circle | None:
|
|
ax, ay = self.a.x, self.a.y
|
|
bx, by = self.b.x, self.b.y
|
|
cx, cy = self.c.x, self.c.y
|
|
|
|
D = 2 * (ax * (by - cy) + bx * (cy - ay) + cx * (ay - by))
|
|
|
|
if abs(D) < 1e-10:
|
|
return None
|
|
|
|
ux = ((ax**2 + ay**2) * (by - cy) + (bx**2 + by**2) * (cy - ay) + (cx**2 + cy**2) * (ay - by)) / D
|
|
uy = ((ax**2 + ay**2) * (cx - bx) + (bx**2 + by**2) * (ax - cx) + (cx**2 + cy**2) * (bx - ax)) / D
|
|
|
|
radius = sqrt((ax - ux)**2 + (ay - uy)**2)
|
|
|
|
return Circle(pg.Vector2(ux, uy), radius)
|
|
|
|
def draw(self, screen: pg.Surface) -> None:
|
|
pg.draw.lines(
|
|
screen,
|
|
(0,255,255),
|
|
True,
|
|
(self.a,self.b,self.c)
|
|
)
|
|
|
|
def opposite_point(self, edge: Edge) -> ColorPoint:
|
|
if Edge(self.a, self.b) == edge: return self.c
|
|
if Edge(self.a, self.c) == edge: return self.b
|
|
if Edge(self.b, self.c) == edge: return self.a
|
|
|
|
def __hash__(self) -> int:
|
|
h = 0
|
|
for edge in self.edges: h += hash(edge)
|
|
return h
|
|
|
|
class Cell:
|
|
def __init__(self, seed: ColorPoint, hull: set[Edge], triangulation: set[Triangle], bounds: pg.Rect):
|
|
self.seed: ColorPoint = seed
|
|
self.points: list[ColorPoint] = []
|
|
for t in triangulation:
|
|
if seed in t.vertices:
|
|
self.points.append(t.circumcircle.center)
|
|
for edge in t.edges:
|
|
if seed in (edge.a, edge.b) and edge in hull:
|
|
e = edge.b - edge.a
|
|
n = pg.Vector2(e.y, -e.x)
|
|
if n.dot((edge.a + edge.b) / 2 - t.opposite_point(edge)) < 0:
|
|
n = -n
|
|
self.points.append(t.circumcircle.center + n * 1000)
|
|
|
|
self.points = sorted(self.points, key=lambda p: atan2(p.y - seed.y, p.x - seed.x))
|
|
self._clip(bounds)
|
|
|
|
@property
|
|
def edges(self) -> list[Edge]:
|
|
edges = []
|
|
for a,b in pairwise(self.points):
|
|
edges.append(Edge(a,b))
|
|
edges.append(Edge(self.points[-1], self.points[0]))
|
|
return edges
|
|
|
|
|
|
|
|
def _clip(self, bounds: pg.Rect):
|
|
def _clip_axis(points, boundary, axis, is_max):
|
|
output = []
|
|
if not points:
|
|
return output
|
|
for i in range(len(points)):
|
|
a = points[i]
|
|
b = points[(i + 1) % len(points)]
|
|
a_val = getattr(a, axis)
|
|
b_val = getattr(b, axis)
|
|
a_inside = a_val <= boundary if is_max else a_val >= boundary
|
|
b_inside = b_val <= boundary if is_max else b_val >= boundary
|
|
|
|
if a_inside:
|
|
output.append(a)
|
|
if a_inside != b_inside:
|
|
t = (boundary - a_val) / (b_val - a_val)
|
|
output.append(a + t * (b - a))
|
|
return output
|
|
points = self.points
|
|
points = _clip_axis(points, bounds.left, 'x', False)
|
|
points = _clip_axis(points, bounds.right, 'x', True)
|
|
points = _clip_axis(points, bounds.top, 'y', False)
|
|
points = _clip_axis(points, bounds.bottom, 'y', True)
|
|
self.points = points
|
|
|
|
def draw(self, screen: pg.Surface, draw_point = True):
|
|
if len(self.points) < 3: return
|
|
pg.draw.polygon(
|
|
screen,
|
|
color=self.seed.color,
|
|
points=self.points
|
|
)
|
|
if draw_point:
|
|
pg.draw.circle(
|
|
screen,
|
|
color=(-self.seed.color[0] + 255, -self.seed.color[1] + 255, -self.seed.color[2] + 255),
|
|
center=self.seed,
|
|
radius=4
|
|
)
|
|
|
|
|
|
def main():
|
|
N = 70
|
|
dimensions = (1920,1080)
|
|
pg.init()
|
|
clock = pg.time.Clock()
|
|
screen = pg.display.set_mode(dimensions)
|
|
|
|
points = []
|
|
movers = []
|
|
mover_bounds = screen.get_rect().scale_by(1.5,1.5)
|
|
mover_bounds.center = screen.get_rect().center
|
|
for _ in range(N):
|
|
p = ColorPoint(
|
|
(random.randint(0,255),random.randint(0,255),random.randint(0,255)),
|
|
random.randint(0, dimensions[0]),
|
|
random.randint(0, dimensions[1])
|
|
)
|
|
points.append(p)
|
|
movers.append(Mover(p, mover_bounds, max_v=50))
|
|
|
|
|
|
while True:
|
|
|
|
super_triangle = Triangle(
|
|
ColorPoint((0,0,0),-100000, -100000),
|
|
ColorPoint((0,0,0),-100000, 100000),
|
|
ColorPoint((0,0,0),100000, 0)
|
|
)
|
|
triangles = {super_triangle}
|
|
|
|
|
|
for p in points:
|
|
bad = set()
|
|
counter = Counter()
|
|
for t in triangles:
|
|
c = t.circumcircle
|
|
if c is None or c.point_within(p):
|
|
bad.add(t)
|
|
for edge in t.edges: counter[edge] += 1
|
|
triangles = triangles.difference(bad)
|
|
for edge, count in counter.items():
|
|
if count == 1: triangles.add(Triangle(p, edge.a, edge.b))
|
|
|
|
bad = set()
|
|
for t in triangles:
|
|
for v in t.vertices:
|
|
if v in super_triangle.vertices: bad.add(t)
|
|
|
|
triangles = triangles.difference(bad)
|
|
|
|
edge_counter = Counter()
|
|
|
|
for t in triangles:
|
|
for edge in t.edges: edge_counter[edge] += 1
|
|
|
|
hull = {edge for edge, count in edge_counter.items() if count == 1}
|
|
|
|
voronoi: list[Cell] = []
|
|
|
|
for p in points:
|
|
voronoi.append(Cell(p, hull, triangles, screen.get_rect()))
|
|
|
|
dt = clock.tick() / 1000
|
|
screen.fill((0,0,0))
|
|
for mover in movers: mover.move(dt)
|
|
for v in voronoi: v.draw(screen, False)
|
|
pg.display.flip()
|
|
for event in pg.event.get():
|
|
if event.type == pg.QUIT: exit()
|
|
|
|
|
|
if __name__ == "__main__":
|
|
main() |