Last active
April 11, 2022 10:37
-
-
Save PardhavMaradani/7a0eada1b7ca86553c8542ea5b832ebd to your computer and use it in GitHub Desktop.
Blog: Interactive Voronoi
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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() |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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() |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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() |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment