Blog: Interactive Voronoi

1_main.py

# https://pardhav-m.blogspot.com/2020/07/interactive-voronoi.html
# https://trinket.io/embed/python/17e4c5d950
# Interactive Voronoi
# Voronoi Points
import turtle
from Voronoi import Voronoi 

# seeds
g_seeds = []

# screen setup
g_screen = turtle.Screen()
g_wh = int(g_screen.window_height())
g_ww = int(1.5 * g_wh)
g_screen.setup(g_ww, g_wh)
g_screen.tracer(0)

# new turtle
def new_turtle():
  t = turtle.Turtle()
  t.ht()
  t.speed(0)
  return t

# turtle
vt = new_turtle()

# help
ht = new_turtle()
g_showing_help = None

# draw a border
def draw_border():
  t = new_turtle()
  t.pu()
  t.goto(-g_ww/2, -g_wh/2)
  t.pd()
  t.goto(g_ww/2, -g_wh/2)
  t.goto(g_ww/2, g_wh/2)
  t.goto(-g_ww/2, g_wh/2)
  t.goto(-g_ww/2, -g_wh/2)
  t.update()

# draw seeds
def draw_seeds(seeds):
  vt.pu()
  for seed in seeds:
    vt.goto(seed)
    vt.dot(3)

# draw voronoi
def draw_voronoi():
  if len(g_seeds) == 0:
    vt.clear()
    vt.update()
    return
  # get voronoi edges
  voronoi = Voronoi(g_seeds)
  voronoi.process()
  voronoi_edges = voronoi.get_output()
  # clear turtle to redraw
  vt.clear()
  # draw seeds
  draw_seeds(g_seeds)
  # draw edges
  for edge in voronoi_edges:
    (x1, y1, x2, y2) = edge
    vt.pu()
    vt.goto(x1, y1)
    vt.pd()
    vt.goto(x2, y2)
  # update screen
  vt.update()

# show voronoi
def show_voronoi():
  draw_voronoi()

# hide voronoi
def hide_voronoi():
  vt.clear()
  vt.update()

# show help
def show_help():
  hide_voronoi()
  global g_showing_help
  x, y = (-g_ww/2 + 20, g_wh/2 - 40)
  ht.pu()
  ht.goto(x, y)
  ht.write("Click to add points...", font=("Arial", 16, "normal"))
  ht.goto(x, y - 30)
  keys_font = ("Arial", 14, "normal")
  ht.write("Keys", font = keys_font)
  ht.goto(x + 20, y - 60)
  ht.write("u - undo", font = keys_font)
  ht.goto(x + 20, y - 90)
  ht.write("h - toggle help", font = keys_font)
  ht.update()
  g_showing_help = True

# hide help
def hide_help():
  global g_showing_help
  ht.clear()
  ht.update()
  g_showing_help = False
  show_voronoi()

# toggle help screen
def toggle_help():
  if g_showing_help:
    hide_help()
  else:
    show_help()

# undo - remove most recent point
def undo():
  if g_showing_help or len(g_seeds) == 0:
    return
  remove_event_handlers()
  g_seeds.pop()
  draw_voronoi()
  add_event_handlers()

# add point callback
def add_point(x, y):
  if (x, y) in g_seeds:
    return
  if g_showing_help:
    hide_help()
    if len(g_seeds) > 0:
      return
  remove_event_handlers()
  g_seeds.append((x, y))
  draw_voronoi()
  add_event_handlers()

# remove event handlers
def remove_event_handlers():
  g_screen.onkey(None, "h")
  g_screen.onkey(None, "u")
  g_screen.onscreenclick(None)

# add event handlers
def add_event_handlers():
  g_screen.onkey(toggle_help, "h")
  g_screen.onkey(undo, "u")
  g_screen.onscreenclick(add_point)

# setup
def setup():
  draw_border()
  show_help()
  add_event_handlers()
  g_screen.listen()

# main

setup()

2_main.py

# https://pardhav-m.blogspot.com/2020/07/interactive-voronoi.html
# https://trinket.io/embed/python/cd68b4b8d2
# Interactive Voronoi
# Voronoi Kaleidoscope
import turtle
import math
from Voronoi import Voronoi 

g_n_sectors = 6
g_added_points = []
g_seeds = []

# screen setup
g_screen = turtle.Screen()
g_wh = int(g_screen.window_height())
g_ww = int(1.5 * g_wh)
g_screen.setup(g_ww, g_wh)
g_screen.tracer(0)

# new turtle
def new_turtle():
  t = turtle.Turtle()
  t.ht()
  t.speed(0)
  return t

# turtle
vt = new_turtle()
# help
ht = new_turtle()
g_showing_help = None
# show sectors
st = new_turtle()
st.color('red')
g_showing_sectors = False

# draw a border
def draw_border():
  t = new_turtle()
  t.pu()
  t.goto(-g_ww/2, -g_wh/2)
  t.pd()
  t.goto(g_ww/2, -g_wh/2)
  t.goto(g_ww/2, g_wh/2)
  t.goto(-g_ww/2, g_wh/2)
  t.goto(-g_ww/2, -g_wh/2)
  t.update()

# draw seeds
def draw_seeds(seeds):
  vt.pu()
  for seed in seeds:
    vt.goto(seed)
    vt.dot(3)

# draw voronoi
def draw_voronoi():
  if len(g_seeds) == 0:
    vt.clear()
    vt.update()
    return
  # get voronoi edges
  voronoi = Voronoi(g_seeds)
  voronoi.process()
  voronoi_edges = voronoi.get_output()
  # clear turtle to redraw
  vt.clear()
  # draw seeds
  draw_seeds(g_seeds)
  # draw edges
  for edge in voronoi_edges:
    (x1, y1, x2, y2) = edge
    vt.pu()
    vt.goto(x1, y1)
    vt.pd()
    vt.goto(x2, y2)
  # update screen
  vt.update()

# generate seeds from raw points and draw
def generate_seeds_and_draw():
  global g_seeds
  g_seeds = []
  sector_angle = 2 * math.pi / g_n_sectors
  for point in g_added_points:
    x, y = point
    # normalize point to first sector
    point_angle = math.atan2(y, x)
    point_angle_norm = math.atan2(y, x) % sector_angle
    n_rotate_angle = point_angle_norm - point_angle
    nx = x * math.cos(n_rotate_angle) - y * math.sin(n_rotate_angle)
    ny = x * math.sin(n_rotate_angle) + y * math.cos(n_rotate_angle)
    # rotate normalized point in all sectors
    for i in range(g_n_sectors):
      rotate_angle = sector_angle * i
      rx = nx * math.cos(rotate_angle) - ny * math.sin(rotate_angle)
      ry = nx * math.sin(rotate_angle) + ny * math.cos(rotate_angle)
      g_seeds.append((rx, ry))
  # draw voronoi
  draw_voronoi()

# show voronoi
def show_voronoi():
  draw_voronoi()

# hide voronoi
def hide_voronoi():
  vt.clear()
  vt.update()

# show help
def show_help():
  hide_voronoi()
  hide_sectors()
  global g_showing_help
  x, y = (-g_ww/2 + 20, g_wh/2 - 40)
  ht.pu()
  ht.goto(x, y)
  ht.write("Click to add points...", font=("Arial", 16, "normal"))
  ht.goto(x, y - 30)
  keys_font = ("Arial", 14, "normal")
  ht.write("Keys", font = keys_font)
  ht.goto(x + 20, y - 60)
  ht.write("u - undo", font = keys_font)
  ht.goto(x + 20, y - 90)
  ht.write("↑ - inc sectors", font = keys_font)
  ht.goto(x + 20, y - 120)
  ht.write("↓ - dec sectors", font = keys_font)
  ht.goto(x + 20, y - 150)
  ht.write("s - show / hide sectors", font = keys_font)
  ht.goto(x + 20, y - 180)
  ht.write("h - toggle help", font = keys_font)
  ht.update()
  g_showing_help = True

# hide help
def hide_help():
  global g_showing_help
  ht.clear()
  ht.update()
  g_showing_help = False
  show_voronoi()

# toggle help screen
def toggle_help():
  if g_showing_help:
    hide_help()
  else:
    show_help()

# undo - remove most recent point
def undo():
  if g_showing_help or len(g_added_points) == 0:
    return
  remove_event_handlers()
  g_added_points.pop()
  generate_seeds_and_draw()
  add_event_handlers()

# inc sectors
def inc_sectors():
  global g_n_sectors
  if g_showing_help:
    return
  remove_event_handlers()
  g_n_sectors += 1
  generate_seeds_and_draw()
  if g_showing_sectors:
    show_sectors()
  add_event_handlers()

# dec sectors
def dec_sectors():
  global g_n_sectors
  if g_showing_help or g_n_sectors == 1:
    return
  remove_event_handlers()
  g_n_sectors -= 1
  generate_seeds_and_draw()
  if g_showing_sectors:
    show_sectors()
  add_event_handlers()

# show sectors
def show_sectors():
  st.clear()
  global g_showing_sectors
  sector_angle = 2 * math.pi / g_n_sectors
  for i in range(g_n_sectors):
    st.seth(math.degrees(sector_angle * i))
    st.fd(g_ww)
    st.bk(g_ww)
  st.update()
  g_showing_sectors = True

# hide sectors
def hide_sectors():
  global g_showing_sectors
  st.clear()
  st.update()
  g_showing_sectors = False

# toggle showing sectors
def toggle_sectors():
  if g_showing_help:
    return
  if g_showing_sectors:
    hide_sectors()
  else:
    show_sectors()

# add point callback
def add_point(x, y):
  if g_showing_help:
    hide_help()
    if len(g_added_points) > 0:
      return
  if (x, y) in g_added_points:
    return
  remove_event_handlers()
  g_added_points.append((x, y))
  generate_seeds_and_draw()
  add_event_handlers()

# remove event handlers
def remove_event_handlers():
  g_screen.onkey(None, "h")
  g_screen.onkey(None, "u")
  g_screen.onkey(None, "Up")
  g_screen.onkey(None, "Down")
  g_screen.onkey(None, "s")
  g_screen.onscreenclick(None)

# add event handlers
def add_event_handlers():
  g_screen.onkey(toggle_help, "h")
  g_screen.onkey(undo, "u")
  g_screen.onkey(inc_sectors, "Up")
  g_screen.onkey(dec_sectors, "Down")
  g_screen.onkey(toggle_sectors, "s")
  g_screen.onscreenclick(add_point)

# setup
def setup():
  global g_n_sectors
  draw_border()
  show_help()
  add_event_handlers()
  g_screen.listen()

# main

setup()

3_collage_helpers.py

import turtle

# Interactive Seed Class
class Seed(turtle.Turtle):
  def __init__(self, id = 0, x = 0, y = 0, bounding_box = None, callback = None):
    turtle.Turtle.__init__(self)
    self.id = id
    self.clicked = False
    self.dragging = False
    self.is_playing = None
    self.bounding_box = bounding_box
    self.callback = callback
    self.speed(0)
    self.pu()
    self.goto(x, y)
    # self.fd(10)
    # self.write("s" + str(self.id))
    # self.bk(10)
    # click/release/drag handlers
    self.onclick(self.onclick_handler)
    self.onrelease(self.onrelease_handler)
    self.ondrag(self.ondrag_handler)
    self.update()

  # handle click
  def onclick_handler(self, x, y):
    if not self.isvisible():
      return
    self.clicked = True

  # handle release
  def onrelease_handler(self, x, y):
    self.clicked = False

  # handle drag
  def ondrag_handler(self, x, y):
    if not self.clicked or self.dragging:
      return
    gap = 6
    (bb_minx, bb_miny, bb_maxx, bb_maxy) = self.bounding_box
    if not (x >= bb_minx + gap and x <= bb_maxx - gap and y >= bb_miny + gap and y <= bb_maxy - gap):
      self.clicked = False      
      return
    self.dragging = True
    self.clear()
    self.goto(x, y)
    # self.fd(10)
    # self.write("s" + str(self.id))
    # self.bk(10)
    if self.callback:
      self.callback(self.id)
    self.update()
    self.dragging = False

# get centroid of polygon
# Source: https://bell0bytes.eu/centroid-convex/
def get_polygon_centroid(polygon):
  centroidX = 0
  centroidY = 0
  det = 0
  temDet = 0
  j = 0
  nVertices = len(polygon)
  for i in range(nVertices):
    if (i + 1 == nVertices):
      j = 0
    else:
      j = i + 1
    x1, y1 = polygon[i]
    x2, y2 = polygon[j]
    tempDet = x1 * y2 - x2 * y1
    det += tempDet
    centroidX += (x1 + x2) * tempDet
    centroidY += (y1 + y2) * tempDet  

  centroidX = centroidX / (3 * det)
  centroidY = centroidY / (3 * det)
  return (centroidX, centroidY)

3_main.py

# https://pardhav-m.blogspot.com/2020/07/interactive-voronoi.html
# https://trinket.io/embed/python/9d4b8e86a0
# Interactive Voronoi
# Voronoi Collage
import turtle
import random
import time
import math
from Voronoi import Voronoi
from voronoi_helpers import get_voronoi_polygons
from slider import Slider
from collage_helpers import Seed, get_polygon_centroid

# global vars
g_n_seeds = 3
g_gap = 0.05
g_edit = 1

# seeds
g_seeds = []
g_seed_coords = []

# screen setup
g_screen = turtle.Screen()
g_wh = int(g_screen.window_height())
g_ww = int(1.5 * g_wh)
g_screen_radius = g_wh / 2
g_screen.setup(g_ww, g_wh)
g_screen.tracer(0)

# new turtle
def new_turtle():
  t = turtle.Turtle()
  t.ht()
  t.speed(0)
  return t

# voronoi turtle
vt = new_turtle()

g_bb_minx = int(-g_ww / 2.5)
g_bb_maxx = int(g_ww / 2.5)
g_bb_miny = int((-g_wh / 3) - (g_wh/10))
g_bb_maxy = int((g_wh / 3) - (g_wh/10))

g_bounding_box = (g_bb_minx, g_bb_miny, g_bb_maxx, g_bb_maxy)

# draw bounding box
def draw_bounding_box():
  t = new_turtle()
  t.pu()
  t.goto(g_bb_minx, g_bb_miny)
  t.pd()
  t.goto(g_bb_maxx, g_bb_miny)
  t.goto(g_bb_maxx, g_bb_maxy)
  t.goto(g_bb_minx, g_bb_maxy)
  t.goto(g_bb_minx, g_bb_miny)
  t.update()

# draw a border
def draw_border():
  t = new_turtle()
  t.pu()
  t.goto(-g_ww/2, -g_wh/2)
  t.pd()
  t.goto(g_ww/2, -g_wh/2)
  t.goto(g_ww/2, g_wh/2)
  t.goto(-g_ww/2, g_wh/2)
  t.goto(-g_ww/2, -g_wh/2)
  t.update()

# handle slider updates
def handle_slider_update(id, value):
  if id == 0:
    update_n_seeds(value)
  elif id == 1:
    update_gap(value)
  elif id == 2:
    update_edit(value)

# resize polygon based on gap
def resize_polygon(polygon):
  cx, cy = get_polygon_centroid(polygon)
  output = []
  for v in polygon:
    x, y = v
    x1 = x + (g_gap * (cx - x))
    y1 = y + (g_gap * (cy - y))
    output.append((x1, y1))
  return output

# draw polygon
def draw_polygon(polygon):
  new_polygon = resize_polygon(polygon)
  for i, v in enumerate(new_polygon):
    if i == 0:
      vt.pu()
    vt.goto(v)
    if i == 0:
      vt.pd()
  vt.goto(new_polygon[0])

# draw voronoi
def draw_voronoi():
  voronoi = Voronoi(g_seed_coords)
  voronoi.process()
  voronoi_edges = voronoi.get_output()
  # clear turtle to redraw
  vt.clear()
  # get polygons
  polygons = get_voronoi_polygons(g_seed_coords, voronoi_edges, g_bounding_box)
  # draw polygons
  for polygon in polygons:
    draw_polygon(polygon)
  vt.update()

# seed move handler
def handle_seed_move(id):
  update_seed_coords()

# create a random seed
def create_random_seed(i):
  mh = int(g_wh * 0.8)
  gap = 6
  bb_width = g_bb_maxx - g_bb_minx - 2*gap
  bb_height = g_bb_maxy - g_bb_miny - 2*gap
  x = random.randrange(0, bb_width) - (bb_width / 2)
  y = random.randrange(0, bb_height) - (bb_height / 2) - (g_wh/10)
  seed = Seed(i, x, y, g_bounding_box, handle_seed_move)
  seed.shape('seed')
  if g_edit == 0:
    seed.ht()
  seed.update()
  g_seeds.append(seed)

# create initial seeds
def create_initial_seeds():
  global g_seeds
  # create seed shape
  s = g_screen_radius * 0.025
  g_screen.register_shape("seed", ((-s, -s), (s, -s), (s, s), (-s, s)))
  # create initial seeds
  for i in range(g_n_seeds):
    create_random_seed(i)
  update_seed_coords()

# update seed coordinates (after drag)
def update_seed_coords():
  global g_seed_coords
  g_seed_coords = []
  for seed in g_seeds:
    g_seed_coords.append(seed.pos())
  draw_voronoi()

# seeds slider update
def update_n_seeds(n):
  global g_n_seeds
  if n == g_n_seeds:
    return
  diff = n - g_n_seeds
  if diff > 0:
    for i in range(diff):
      create_random_seed(g_n_seeds)
      g_n_seeds += 1
  else:
    for i in range(abs(diff)):
      g_n_seeds -= 1
      seed = g_seeds.pop()
      seed.clear()
      seed.ht()
      del seed
  update_seed_coords()

# update gap
def update_gap(value):
  global g_gap
  g_gap = value
  draw_voronoi()

# update edit
def update_edit(value):
  global g_edit
  g_edit = value
  for seed in g_seeds:
    if g_edit == 1:
      seed.st()
    else:
      seed.ht()
    seed.update()

# create sliders
def create_sliders():
  x = -g_ww/2 + 20
  y = g_wh/2 - 20
  slider_length = g_screen_radius * 0.6
  # create sliders
  Slider(0, x, y, slider_length, 2, 10, 1, g_n_seeds, 'seeds', handle_slider_update)
  Slider(1, x, y - 30, slider_length, 0, 0.2, 0.01, g_gap, 'gap', handle_slider_update)
  Slider(2, x, y - 60, g_screen_radius * 0.15, 0, 1, 1, g_edit, 'edit', handle_slider_update)

# setup
def setup():
  draw_border()
  draw_bounding_box()
  create_sliders()
  create_initial_seeds()

# main

setup()

4_DataType.py

# Source: https://github.com/jansonh/Voronoi

from min_heapq import heappush, heappop

class Point:
   x = 0.0
   y = 0.0
   
   def __init__(self, x, y):
       self.x = x
       self.y = y

class Event:
    x = 0.0
    p = None
    a = None
    valid = True
    
    def __init__(self, x, p, a):
        self.x = x
        self.p = p
        self.a = a
        self.valid = True

class Arc:
    p = None
    pprev = None
    pnext = None
    e = None
    s0 = None
    s1 = None
    
    def __init__(self, p, a=None, b=None):
        self.p = p
        self.pprev = a
        self.pnext = b
        self.e = None
        self.s0 = None
        self.s1 = None

class Segment:
    start = None
    end = None
    done = False
    
    def __init__(self, p):
        self.start = p
        self.end = None
        self.done = False

    def finish(self, p):
        if self.done: return
        self.end = p
        self.done = True        

class PriorityQueue:
    def __init__(self):
        self.pq = []
        self.entry_finder = {}
        self.counter = 0 #itertools.count()

    def push(self, item):
        # check for duplicate
        if item in self.entry_finder: return
        count = self.counter
        self.counter += 1
        # use x-coordinate as a primary key (heapq in python is min-heap)
        entry = [item.x, count, item]
        self.entry_finder[item] = entry
        heappush(self.pq, entry)

    def remove_entry(self, item):
        entry = self.entry_finder.pop(item)
        entry[-1] = 'Removed'

    def pop(self):
        while self.pq:
            priority, count, item = heappop(self.pq)
            if item is not 'Removed':
                del self.entry_finder[item]
                return item
        raise KeyError('pop from an empty priority queue')

    def top(self):
        while self.pq:
            priority, count, item = heappop(self.pq)
            if item is not 'Removed':
                del self.entry_finder[item]
                self.push(item)
                return item
        raise KeyError('top from an empty priority queue')

    def empty(self):
        return not self.pq

4_line_clip.py

# Source: https://github.com/scivision/lineclipping-python-fortran/blob/master/pylineclip/__init__.py

'''
 The MIT License (MIT)
 Copyright (c) 2014 Michael Hirsch
 reference: http://en.wikipedia.org/wiki/Cohen%E2%80%93Sutherland_algorithm
 * The best way to Numba JIT this would probably be in the function calling this,
   to include the loop itself inside the jit decoration.
'''

def cohensutherland(xmin, ymax, xmax, ymin, x1, y1, x2, y2):
    """Clips a line to a rectangular area.
    This implements the Cohen-Sutherland line clipping algorithm.  xmin,
    ymax, xmax and ymin denote the clipping area, into which the line
    defined by x1, y1 (start point) and x2, y2 (end point) will be
    clipped.
    If the line does not intersect with the rectangular clipping area,
    four None values will be returned as tuple. Otherwise a tuple of the
    clipped line points will be returned in the form (cx1, cy1, cx2, cy2).
    """
    INSIDE, LEFT, RIGHT, LOWER, UPPER = 0, 1, 2, 4, 8

    def _getclip(xa, ya):
        # if dbglvl>1: print('point: '),; print(xa,ya)
        p = INSIDE  # default is inside

        # consider x
        if xa < xmin:
            p |= LEFT
        elif xa > xmax:
            p |= RIGHT

        # consider y
        if ya < ymin:
            p |= LOWER  # bitwise OR
        elif ya > ymax:
            p |= UPPER  # bitwise OR
        return p

    # check for trivially outside lines
    k1 = _getclip(x1, y1)
    k2 = _getclip(x2, y2)

    # %% examine non-trivially outside points
    # bitwise OR |
    while (k1 | k2) != 0:  # if both points are inside box (0000) , ACCEPT trivial whole line in box

        # if line trivially outside window, REJECT
        if (k1 & k2) != 0:  # bitwise AND &
            # if dbglvl>1: print('  REJECT trivially outside box')
            # return nan, nan, nan, nan
            return None, None, None, None

        # non-trivial case, at least one point outside window
        # this is not a bitwise or, it's the word "or"
        opt = k1 or k2  # take first non-zero point, short circuit logic
        if opt & UPPER:  # these are bitwise ANDS
            x = x1 + (x2 - x1) * (ymax - y1) / (y2 - y1)
            y = ymax
        elif opt & LOWER:
            x = x1 + (x2 - x1) * (ymin - y1) / (y2 - y1)
            y = ymin
        elif opt & RIGHT:
            y = y1 + (y2 - y1) * (xmax - x1) / (x2 - x1)
            x = xmax
        elif opt & LEFT:
            y = y1 + (y2 - y1) * (xmin - x1) / (x2 - x1)
            x = xmin
        else:
            raise RuntimeError('Undefined clipping state')

        if opt == k1:
            x1, y1 = x, y
            k1 = _getclip(x1, y1)
        elif opt == k2:
            x2, y2 = x, y
            k2 = _getclip(x2, y2)

    return x1, y1, x2, y2

4_min_heapq.py

# Source: https://github.com/python/cpython/tree/3.8/Lib/heapq.py

def heappush(heap, item):
    """Push item onto heap, maintaining the heap invariant."""
    heap.append(item)
    _siftdown(heap, 0, len(heap)-1)

def heappop(heap):
    """Pop the smallest item off the heap, maintaining the heap invariant."""
    lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        _siftup(heap, 0)
        return returnitem
    return lastelt

def _siftdown(heap, startpos, pos):
    newitem = heap[pos]
    # Follow the path to the root, moving parents down until finding a place
    # newitem fits.
    while pos > startpos:
        parentpos = (pos - 1) >> 1
        parent = heap[parentpos]
        if newitem < parent:
            heap[pos] = parent
            pos = parentpos
            continue
        break
    heap[pos] = newitem

def _siftup(heap, pos):
    endpos = len(heap)
    startpos = pos
    newitem = heap[pos]
    # Bubble up the smaller child until hitting a leaf.
    childpos = 2*pos + 1    # leftmost child position
    while childpos < endpos:
        # Set childpos to index of smaller child.
        rightpos = childpos + 1
        if rightpos < endpos and not heap[childpos] < heap[rightpos]:
            childpos = rightpos
        # Move the smaller child up.
        heap[pos] = heap[childpos]
        pos = childpos
        childpos = 2*pos + 1
    # The leaf at pos is empty now.  Put newitem there, and bubble it up
    # to its final resting place (by sifting its parents down).
    heap[pos] = newitem
    _siftdown(heap, startpos, pos)

4_slider.py

import turtle

# register square thumb shape
thumb_size = 7
screen = turtle.Screen()
screen.register_shape('thumb', ((-thumb_size, -thumb_size), (thumb_size, -thumb_size), (thumb_size, thumb_size), (-thumb_size, thumb_size)))

# Slider Class
class Slider(turtle.Turtle):
  def __init__(self, id, x, y, length, min, max, step, initial_value, label, callback):
    turtle.Turtle.__init__(self)
    self.shape('thumb')
    self.speed(0)
    self.id = id
    self.x = x
    self.y = y
    self.length = length
    self.min = min
    self.step = step
    self.label = label
    self.callback = callback
    self.clicked = False
    self.dragging = False
    self.steps = (max - min) / step
    # draw slider line
    self.pu()
    self.goto(x, y)
    self.pd()
    self.fd(length)
    # turtle to write label text and value
    self.lt = turtle.Turtle()
    self.lt.speed(0)
    self.lt.pu()
    self.lt.goto(self.pos())
    self.lt.fd(20)
    self.lt.right(90)
    self.lt.fd(thumb_size/2)
    self.lt.ht()
    # move thumb to initial position
    self.bk(length)
    initial_length = length * ((initial_value - min) / (max - min))
    self.fd(initial_length)
    self.value = initial_value
    # update label
    self.update_label()
    # register mouse handlers
    self.onclick(self.onclick_handler)
    self.onrelease(self.onrelease_handler)
    self.ondrag(self.ondrag_handler)

  # write label text and value    
  def update_label(self):
    self.lt.clear()
    self.lt.write(self.label + ' = ' + str(self.value), font=("Arial", 10, "normal"))
    self.update()
  
  # get value based on slider position
  def get_value(self, x):
    unit_value = (x - self.x) / self.length
    v1 = unit_value * self.steps * self.step
    v1 = int(v1 / self.step) * self.step
    return self.min + v1

  # onclick handler
  def onclick_handler(self, x, y):
    self.clicked = True

  # onrelease handler
  def onrelease_handler(self, x, y):
    self.clicked = False

  # ondrag handler
  def ondrag_handler(self, x, y):
    if not self.clicked:
      return
    if self.dragging:
      return
    # stop drag if mouse moves away in y direction
    if abs(y - self.y) > 20:
      self.clicked = False
      self.dragging = False
      self.callback(self.id, self.value)
      return
    self.dragging = True
    # limit drag within the slider
    if x < self.x:
      x = self.x
    if x > self.x + self.length:
      x = self.x + self.length
    # move thumb to new position
    self.goto(x, self.y)
    new_value = self.get_value(x)
    # call the callback function if value changes
    if new_value != self.value:
      self.value = new_value
      self.update_label()
      self.callback(self.id, self.value)
    self.update()
    self.dragging = False

4_Voronoi.py

# Source: https://github.com/jansonh/Voronoi

import math

from DataType import Point, Event, Arc, Segment, PriorityQueue

# Source: (C++) http://www.cs.hmc.edu/~mbrubeck/voronoi.html

class Voronoi:
    def __init__(self, points):
        self.output = [] # list of line segment
        self.arc = None  # binary tree for parabola arcs

        self.points = PriorityQueue() # site events
        self.event = PriorityQueue() # circle events

        # bounding box
        self.x0 = -0.0
        self.x1 = -0.0
        self.y0 = 0.0
        self.y1 = 0.0

        # insert points to site event
        for pts in points:
            point = Point(pts[0], pts[1])
            self.points.push(point)
            # keep track of bounding box size
            if point.x < self.x0: self.x0 = point.x
            if point.y < self.y0: self.y0 = point.y
            if point.x > self.x1: self.x1 = point.x
            if point.y > self.y1: self.y1 = point.y

        # add margins to the bounding box
        dx = (self.x1 - self.x0 + 1) / 5.0
        dy = (self.y1 - self.y0 + 1) / 5.0
        self.x0 = self.x0 - dx
        self.x1 = self.x1 + dx
        self.y0 = self.y0 - dy
        self.y1 = self.y1 + dy

    def process(self):
        while not self.points.empty():
            if not self.event.empty() and (self.event.top().x <= self.points.top().x):
                self.process_event() # handle circle event
            else:
                self.process_point() # handle site event

        # after all points, process remaining circle events
        while not self.event.empty():
            self.process_event()

        self.finish_edges()

    def process_point(self):
        # get next event from site pq
        p = self.points.pop()
        # add new arc (parabola)
        self.arc_insert(p)

    def process_event(self):
        # get next event from circle pq
        e = self.event.pop()

        if e.valid:
            # start new edge
            s = Segment(e.p)
            self.output.append(s)

            # remove associated arc (parabola)
            a = e.a
            if a.pprev is not None:
                a.pprev.pnext = a.pnext
                a.pprev.s1 = s
            if a.pnext is not None:
                a.pnext.pprev = a.pprev
                a.pnext.s0 = s

            # finish the edges before and after a
            if a.s0 is not None: a.s0.finish(e.p)
            if a.s1 is not None: a.s1.finish(e.p)

            # recheck circle events on either side of p
            if a.pprev is not None: self.check_circle_event(a.pprev, e.x)
            if a.pnext is not None: self.check_circle_event(a.pnext, e.x)

    def arc_insert(self, p):
        if self.arc is None:
            self.arc = Arc(p)
        else:
            # find the current arcs at p.y
            i = self.arc
            while i is not None:
                flag, z = self.intersect(p, i)
                if flag:
                    # new parabola intersects arc i
                    flag, zz = self.intersect(p, i.pnext)
                    if (i.pnext is not None) and (not flag):
                        i.pnext.pprev = Arc(i.p, i, i.pnext)
                        i.pnext = i.pnext.pprev
                    else:
                        i.pnext = Arc(i.p, i)
                    i.pnext.s1 = i.s1

                    # add p between i and i.pnext
                    i.pnext.pprev = Arc(p, i, i.pnext)
                    i.pnext = i.pnext.pprev

                    i = i.pnext # now i points to the new arc

                    # add new half-edges connected to i's endpoints
                    seg = Segment(z)
                    self.output.append(seg)
                    i.pprev.s1 = i.s0 = seg

                    seg = Segment(z)
                    self.output.append(seg)
                    i.pnext.s0 = i.s1 = seg

                    # check for new circle events around the new arc
                    self.check_circle_event(i, p.x)
                    self.check_circle_event(i.pprev, p.x)
                    self.check_circle_event(i.pnext, p.x)

                    return
                        
                i = i.pnext

            # if p never intersects an arc, append it to the list
            i = self.arc
            while i.pnext is not None:
                i = i.pnext
            i.pnext = Arc(p, i)
            
            # insert new segment between p and i
            x = self.x0
            y = (i.pnext.p.y + i.p.y) / 2.0;
            start = Point(x, y)

            seg = Segment(start)
            i.s1 = i.pnext.s0 = seg
            self.output.append(seg)

    def check_circle_event(self, i, x0):
        # look for a new circle event for arc i
        if (i.e is not None) and (i.e.x  <> self.x0):
            i.e.valid = False
        i.e = None

        if (i.pprev is None) or (i.pnext is None): return

        flag, x, o = self.circle(i.pprev.p, i.p, i.pnext.p)
        if flag and (x > self.x0):
            i.e = Event(x, o, i)
            self.event.push(i.e)

    def circle(self, a, b, c):
        # check if bc is a "right turn" from ab
        if ((b.x - a.x)*(c.y - a.y) - (c.x - a.x)*(b.y - a.y)) > 0: return False, None, None

        # Joseph O'Rourke, Computational Geometry in C (2nd ed.) p.189
        A = b.x - a.x
        B = b.y - a.y
        C = c.x - a.x
        D = c.y - a.y
        E = A*(a.x + b.x) + B*(a.y + b.y)
        F = C*(a.x + c.x) + D*(a.y + c.y)
        G = 2*(A*(c.y - b.y) - B*(c.x - b.x))

        if (G == 0): return False, None, None # Points are co-linear

        # point o is the center of the circle
        ox = 1.0 * (D*E - B*F) / G
        oy = 1.0 * (A*F - C*E) / G

        # o.x plus radius equals max x coord
        x = ox + math.sqrt((a.x-ox)**2 + (a.y-oy)**2)
        o = Point(ox, oy)
           
        return True, x, o
        
    def intersect(self, p, i):
        # check whether a new parabola at point p intersect with arc i
        if (i is None): return False, None
        if (i.p.x == p.x): return False, None

        a = 0.0
        b = 0.0

        if i.pprev is not None:
            a = (self.intersection(i.pprev.p, i.p, 1.0*p.x)).y
        if i.pnext is not None:
            b = (self.intersection(i.p, i.pnext.p, 1.0*p.x)).y

        if (((i.pprev is None) or (a <= p.y)) and ((i.pnext is None) or (p.y <= b))):
            py = p.y
            px = 1.0 * ((i.p.x)**2 + (i.p.y-py)**2 - p.x**2) / (2*i.p.x - 2*p.x)
            res = Point(px, py)
            return True, res
        return False, None

    def intersection(self, p0, p1, l):
        # get the intersection of two parabolas
        p = p0
        if (p0.x == p1.x):
            py = (p0.y + p1.y) / 2.0
        elif (p1.x == l):
            py = p1.y
        elif (p0.x == l):
            py = p0.y
            p = p1
        else:
            # use quadratic formula
            z0 = 2.0 * (p0.x - l)
            z1 = 2.0 * (p1.x - l)

            a = 1.0/z0 - 1.0/z1;
            b = -2.0 * (p0.y/z0 - p1.y/z1)
            c = 1.0 * (p0.y**2 + p0.x**2 - l**2) / z0 - 1.0 * (p1.y**2 + p1.x**2 - l**2) / z1

            py = 1.0 * (-b-math.sqrt(b*b - 4*a*c)) / (2*a)
            
        px = 1.0 * (p.x**2 + (p.y-py)**2 - l**2) / (2*p.x-2*l)
        res = Point(px, py)
        return res

    def finish_edges(self):
        l = self.x1 + (self.x1 - self.x0) + (self.y1 - self.y0)
        i = self.arc
        while i.pnext is not None:
            if i.s1 is not None:
                p = self.intersection(i.p, i.pnext.p, l*2.0)
                i.s1.finish(p)
            i = i.pnext

    def get_output(self):
        res = []
        for o in self.output:
            p0 = o.start
            p1 = o.end
            if o.done:
              res.append((p0.x, p0.y, p1.x, p1.y))
        return res

4_voronoi_helpers.py

import math
from line_clip import cohensutherland
from DataType import Point

# check if point c is between points a and b
# Source: https://stackoverflow.com/questions/328107/how-can-you-determine-a-point-is-between-two-other-points-on-a-line-segment
def isBetween(a, b, c):
  eps = 0.01
  crossproduct = (c.y - a.y) * (b.x - a.x) - (c.x - a.x) * (b.y - a.y)
  # compare versus epsilon for floating point values, or != 0 if using integers
  if abs(crossproduct) > eps:
      return False
  dotproduct = (c.x - a.x) * (b.x - a.x) + (c.y - a.y)*(b.y - a.y)
  if dotproduct < 0:
      return False
  squaredlengthba = (b.x - a.x)*(b.x - a.x) + (b.y - a.y)*(b.y - a.y)
  if dotproduct > squaredlengthba:
      return False
  return True

# simplify polygon by removing multiple vertices on same line
def simplify_polygon(polygon):
  simplified_polygon = []
  end = len(polygon) - 1
  for i, v in enumerate(polygon):
    pi = i - 1 # previous index
    ni = i + 1 # next index
    if pi < 0:
      pi = end
    if ni > end:
      ni = 0
    pv = polygon[pi] # previous vertex
    nv = polygon[ni] # next vertex
    a = Point(pv[0], pv[1])
    b = Point(nv[0], nv[1])
    c = Point(v[0], v[1])
    if not isBetween(a, b, c):
      simplified_polygon.append(v)
  simplified_polygon.append(simplified_polygon[0])
  return simplified_polygon

def get_voronoi_polygons(seeds, edges, bounding_box):
  (minx, miny, maxx, maxy) = bounding_box
  polygons = []
  # 1. clip edges
  # save border vertices after clipping
  border_vertices = [None] * 4
  for i in range(4):
    border_vertices[i] = []
  # clip edges
  clipped_edges = []
  for edge in edges:
    (x1, y1, x2, y2) = edge
    (nx1, ny1, nx2, ny2) = cohensutherland(minx, maxy, maxx, miny, x1, y1, x2, y2)
    if nx1 == None:
      continue
    clipped_edges.append((nx1, ny1, nx2, ny2))
    # save edges on border for next step
    if ny1 == miny or ny1 == maxy:
      border_vertices[0 if ny1 == miny else 2].append(nx1)
    if ny2 == miny or ny2 == maxy:
      border_vertices[0 if ny2 == miny else 2].append(nx2)
    if nx1 == minx or nx1 == maxx:
      border_vertices[3 if nx1 == minx else 1].append(ny1)
    if nx2 == minx or nx2 == maxx:
      border_vertices[3 if nx2 == minx else 1].append(ny2)
  # 2. connect borders
  # bb 0, 2
  for i in range(0, 4, 2):
    y = miny if i == 0 else maxy
    x1 = minx
    for v in sorted(border_vertices[i]):
      clipped_edges.append((x1, y, v, y))
      x1 = v
    clipped_edges.append((x1, y, maxx, y))
  # bb 1, 3
  for i in range(1, 4, 2):
    x = minx if i == 3 else maxx
    y1 = miny
    for v in sorted(border_vertices[i]):
      clipped_edges.append((x, y1, x, v))
      y1 = v
    clipped_edges.append((x, y1, x, maxy))
  # 3. get polygons
  # edges array for each seed
  seed_edges = [None] * len(seeds)
  for i, seed in enumerate(seeds):
    seed_edges[i] = []
  # Find the seed (cell) that the edge belongs to
  for edge in clipped_edges:
    (x1, y1, x2, y2) = edge
    midx = (x1 + x2) / 2
    midy = (y1 + y2) / 2
    distances = []
    i = 0
    # calculate distance from edge to each seed
    for seed in seeds:
      sx, sy = seed
      distance = math.sqrt((sx-midx)*(sx-midx) + (sy-midy)*(sy-midy))
      distances.append((distance, i))    
      i += 1
    # sort the distances to get closest seeds (cells)
    sorted_distances = sorted(distances)
    _, si1 = sorted_distances[0]
    _, si2 = sorted_distances[1]
    # for border edges, we only need one cell, for all others, two
    only_one = False
    if x1 == x2 and (x1 == minx or x1 == maxx):
      only_one = True
    if y1 == y2 and (y1 == miny or y1 == maxy):
      only_one = True
    seed_edges[si1].append(edge)
    if not only_one:
      seed_edges[si2].append(edge)
  # 4. create polygons from edges
  polygons = []
  for i in range(len(seeds)):
    # get vertices
    vertices = []
    for edge in seed_edges[i]:
      (x1, y1, x2, y2) = edge
      v1 = (x1, y1)
      v2 = (x2, y2)
      if v1 not in vertices:
        vertices.append(v1)
      if v2 not in vertices:
        vertices.append(v2)
    # find approx center of polygon from vertices
    midx = 0
    midy = 0
    for v in vertices:
      x, y = v
      midx += x
      midy += y
    midx /= len(vertices)
    midy /= len(vertices)
    # calculate angle to approx center to sort vertices
    sorted_vertices =  []
    for v in vertices:
      x, y = v
      angle = math.atan2((y - midy), (x - midx))
      sorted_vertices.append((angle, v))
    # create polygon from sorted vertices
    polygon = []
    for e in sorted(sorted_vertices):
      _, v = e
      polygon.append(v)
    # 5. simplify polygons (remove multiple vertices on same line)
    polygons.append(simplify_polygon(polygon))
  # return polygons
  return polygons