Blah blah blah.
We're all in this together
Blah blah blah.
Pt = namedtuple("Pt", "x, y")
zigzags = [
[Pt(10, 20), Pt(15, 21), Pt(20, 25)],
[Pt(20, 25), Pt(30, 15), Pt(27, 25), Pt(23, 21)],
]
zz_by_ends = {
Pt(10, 20): [
[Pt(10, 20), Pt(15, 21), Pt(20, 25)],
],
Pt(20, 25): [
[Pt(10, 20), Pt(15, 21), Pt(20, 25)],
[Pt(20, 25), Pt(30, 15), Pt(27, 25), Pt(23, 21)],
],
Pt(23, 21): [
[Pt(20, 25), Pt(30, 15), Pt(27, 25), Pt(23, 21)],
],
}
>>> d = {}
>>> d['hi'] = 'hello'
>>> d['bye'] = 'goodbye'
>>> d['hi']
'hello'
>>> d = {}
>>> d[17] = 23
>>> d[17]
23
>>> d[(1, 2)] = 'a point'
>>> d[(1, 2)]
'a point'
>>> d[(1.0, 2.0)]
'a point'
>>> d[Pt(10, 20)] = 'another point'
>>> d[Pt(10, 20)]
'another point'
zigzags = [
[Pt(10, 20), Pt(15, 21), Pt(20, 25)],
[Pt(20, 25), Pt(30, 15), Pt(27, 25), Pt(23, 21)],
[Pt(10, 20.00001), Pt(15, 40)], # !!! :(
...
]
>>> d[Pt(10, 20)] = "hey there"
>>> d[Pt(10, 20.00001)]
KeyError: Pt(10, 20.00001)
>>> Pt(10, 20) == Pt(10, 20.00001)
False
>>> 20 == 20.00001
False
>>> 0.1 + 0.2 == 0.3
False
class Pt(namedtuple("Pt", "x, y")):
def __eq__(self, other):
x1, y1 = self
x2, y2 = other
return (
math.isclose(x1, x2) and
math.isclose(y1, y2)
)
class Pt(namedtuple("Pt", "x, y")):
def __eq__(self, other):
x1, y1 = self
x2, y2 = other
return (
math.isclose(x1, x2) and
math.isclose(y1, y2)
)
def __hash__(self):
# ¯\_(ツ)_/¯
zz_by_ends = [
(Pt(10, 20), [..zigzags..] ),
(Pt(20, 25), [..zigzags..] ),
(Pt(23, 21), [..zigzags..] ),
]
def find_zigzags(p):
for pt, zigzags in zz_by_ends:
if p == pt: # fuzzy!
return zigzags
class PointDict:
def __init__(self):
# A list of (pt, value) tuples.
self.items = []
# pd[pt] ≡ pd.__getitem__(pt)
def __getitem__(self, pt):
for key, value in self.items:
if key == pt: # fuzzy!
return value
# Didn't find it: make a new list value and add
# it to the end.
value = []
self.items.append((pt, value))
return value
pd = PointDict()
pd[pt1].append(zz1)
print(pd[pt1])
def __getitem__(self, pt):
for key, value in self.items: # N/2 + N/2
if key == pt: # N/2
return value # 1
pd = PointDict() # Actually, slow linear search!
for zz in all_zigzags:
others = pd[zz[0]]
| Lists | |
|---|---|
| mylist.append(val) | O(1) |
| mylist[i] | O(1) |
| val in mylist | O(N) |
| for val in mylist: | O(N) |
| Dicts | |
|---|---|
| mydict[key] = val | O(1) |
| mydict[key] | O(1) |
| key in mydict | O(1) |
| for key in mydict: | O(N) |
| Sets | |
|---|---|
| myset.add(val) | O(1) |
| val in myset | O(1) |
| for val in myset: | O(N) |
class Pt(namedtuple("Pt", "x, y")):
def rounded(self):
return (round(self.x), round(self.y))
def __eq__(self, other):
return self.rounded() == other.rounded()
def __hash__(self):
return hash(self.rounded())
# BUT!
>>> Pt(11.4999999, 0) == Pt(11.5000001, 0)
False
# Because (11.0, 0) != (12.0, 0)
def rounded(pt, jitter):
return round(pt.x + jitter), round(pt.y + jitter)
def pt_equal(p1, p2):
return (
rounded(p1, 0) == rounded(p2, 0) or
rounded(p1, 0.5) == rounded(p2, 0.5)
)
>>> pt_equal(Pt(10.9999999, 0), Pt(11.0000001, 0))
True
>>> pt_equal(Pt(11.4999999, 0), Pt(11.5000001, 0))
True
class PointDict:
"""Like defaultdict(list), with fuzzy Pt's as keys."""
def __init__(self):
self.items = {} # pt -> value
self.rounds = {} # pt -> pt
def __getitem__(self, pt): # O(1)
val = self.items.get(pt)
if val is not None:
return val
for jitter in [0, 0.5]:
pt_rnd = rounded(pt, jitter)
pt0 = self.rounds.get(pt_rnd)
if pt0 is not None:
return self.items[pt0]
# Not found: make an empty list value
self.items[pt] = val = []
for jitter in [0, 0.5]:
pt_rnd = rounded(pt, jitter)
self.rounds[pt_rnd] = pt
return val
~2100 points
slow: 20 sec
fast: 0.4 sec!
def __init__(self):
self.items = []
def __getitem__(self, pt):
for key, value in self.items:
if key == pt:
return value
value = []
self.items.append((pt, value))
return value
O(1)
O(n)
def __init__(self):
self.items = []
def __getitem__(self, pt):
for key, value in self.items:
if key == pt:
return value
value = []
self.items.append((pt, value))
return value
def __init__(self):
self.items = {} # pt -> value
self.rounds = {} # pt -> pt
def __getitem__(self, pt):
val = self.items.get(pt)
if val is not None:
return val
for jitter in [0, 0.5]:
pt_rnd = rounded(pt, jitter)
pt0 = self.rounds.get(pt_rnd)
if pt0 is not None:
return self.items[pt0]
self.items[pt] = val = []
for jitter in [0, 0.5]:
pt_rnd = rounded(pt, jitter)
self.rounds[pt_rnd] = pt
return val
def __init__(self):
self.items = {} # pt -> value
self.rounds = {} # pt -> pt
def __getitem__(self, pt):
val = self.items.get(pt)
if val is not None:
return val
for jitter in [0, 0.5]:
pt_rnd = rounded(pt, jitter)
pt0 = self.rounds.get(pt_rnd)
if pt0 is not None:
return self.items[pt0]
self.items[pt] = val = []
for jitter in [0, 0.5]:
pt_rnd = rounded(pt, jitter)
self.rounds[pt_rnd] = pt
return val
class Defuzzer:
def defuzz(self, pt):
"""Return pt, or a previous equal point."""
>>> defuzz = Defuzzer().defuzz
>>> defuzz(Pt(1, 2))
Pt(1, 2)
>>> defuzz(Pt(3, 4))
Pt(3, 4)
>>> defuzz(Pt(1.01, 2))
Pt(1, 2)
def defuzz_path(path):
return [defuzz(pt) for pt in path]
def defuzz_paths(paths):
return [defuzz_path(path) for path in paths]
def combine_paths(paths):
paths = defuzz_paths(paths)
paths_by_ends = defaultdict(list)
for path in paths:
paths_by_ends[path[0]].append(path)
paths_by_ends[path[-1]].append(path)
for path in paths:
others = paths_by_ends[path[0]]
etc()
path = [Pt(0, 0), Pt(1, 1), Pt(10, 0)]
def path_length(path): ...
def canonicalize_path(path): ...
def offset_path(path, offset): ...
class Path:
def __init__(self, points):
self.points = points
def length(self): ...
def canonicalize(self): ...
def offset(self, offset): ...
if path[0] == path[-1]:
class Path:
...
@property
def closed(self):
return self.points[0] == self.points[-1]
if path.closed:
def paths_length(paths):
return sum(p.length() for p in paths)
def defuzz_paths(paths):
return [p.defuzz() for p in paths]
>>> from collections import namedtuple
>>> Pt = namedtuple("Pt", "x, y") # Like "class Pt:"
>>> p = Pt(10, 20)
>>> p
Pt(x=10, y=20)
>>> p.x
10
>>> x, y = p # Unpacking the tuple
>>> x
10
>>> p.x = 17
Traceback (most recent call last):
File "<console>", line 1, in <module>
AttributeError: can't set attribute
>>> import attr
>>> @attr.s
... class Pt(object):
... x = attr.ib()
... y = attr.ib()
...
>>> p = Pt(10, 20)
>>> p
Pt(x=10, y=20)
def segment_intersections(segments):
isects = defaultdict(list)
for seg1 in segments:
for seg2 in segments:
if seg1 is seg2:
continue
isect_pt = seg1.intersect(seg2)
if isect_pt is not None:
isects[isect_pt].extend([seg1, seg2])
return isects
File ".../poly_point_isect.py", line 576, in isect_segments_impl
sweep_line.handle(p, events_current)
File ".../poly_point_isect.py", line 384, in handle
self.handle_event(e)
File ".../poly_point_isect.py", line 408, in handle_event
self.remove(event)
File ".../poly_point_isect.py", line 346, in remove
assert(event.in_sweep == False)
AssertionError
def intersections():
for angle in [x/6 for x in range(60)]:
rotate_everything(angle)
try:
isects = isect_segments()
except AssertionError:
print(f"Failed at rotation {angle}")
continue
rotate_everything(-angle)
return isects
Failed at rotation 0.0
Failed at rotation 0.1666666666
Failed at rotation 0.3333333333
Failed at rotation 0.5
Failed at rotation 0.6666666666
Failed at rotation 0.8333333334
Failed at rotation 1.0
Failed at rotation 1.1666666667
1728 intersections
def all_pairs(seq):
"""Produce all pairs from seq, but not (a, a)"""
return itertools.combinations(seq, 2)
"""Strappiness for Zellij."""
import collections
import itertools
import random
from zellij.debug import should_debug
from zellij.drawing import Drawing, DrawingSequence
from zellij.euclid import Point, Segment
from zellij.intersection import segment_intersections
from zellij.path_tiler import join_paths, offset_path, path_segments, trim_path
class Xing:
def __init__(self, under=None, over=None):
self.under = under
self.over = over
self.over_piece = None
def __repr__(self):
return f"<Xing under={show_path(self.under)} over={show_path(self.over)}>"
class Strap:
def __init__(self, path, width, random_factor=0):
self.path = path
if random_factor:
width *= (1 + random.random() * random_factor)
self.sides = [offset_path(path, d) for d in [width/2, -width/2]]
def __repr__(self):
return f"<Strap path={self.path}>"
def path_pieces(path, segs_to_points):
"""Produce a new series of paths, split at intersection points.
Yields a series of pieces (paths). The pieces trace the same line as the
original path. The endpoints of the pieces are all intersection points
in `segs_to_points`, or the endpoints of the original path, if it isn't
circular. The pieces are in order along `path`, so consecutive pieces
end and begin at the same point. If `path` is closed, then the first piece
returned will begin at the first cut, not at the path's first point.
"""
# If path is circular, then the first piece we collect has to be added to
# the last piece, so save it for later.
collecting_head = (path[0] == path[-1])
head = None
piece = []
for pt in path:
if not piece:
piece.append(pt)
else:
seg = Segment(piece[-1], pt)
cuts = segs_to_points.get(seg)
if cuts is not None:
cuts = seg.sort_along(cuts)
for cut in cuts:
ptcut = Point(*cut)
piece.append(ptcut)
if collecting_head:
head = piece
collecting_head = False
else:
yield piece
piece = [ptcut]
piece.append(pt)
if head:
piece = join_paths(piece, head)
yield piece
def pieces_under_over(path, segs_to_points, xings):
"""Produce all the pieces of the path, with a bool indicating if each leads to under
pieces = list(path_pieces(path, segs_to_points))
for i, piece in enumerate(pieces):
xing = xings.get(piece[-1])
if xing is None:
continue
if xing.under == path:
over = False
elif xing.over == path:
over = True
elif xing.under is not None:
over = True
else:
assert xing.over is not None
over = False
ou = [over, not over]
if i % 2:
ou = ou[::-1]
break
else:
ou = [True, False]
yield from zip(pieces, itertools.cycle(ou))
def strapify(paths, **strap_kwargs):
"""Turn paths intro straps."""
paths = [tuple(path) for path in paths]
segments = []
segs_to_paths = {}
for path in paths:
for segment in path_segments(path):
segments.append(segment)
segs_to_paths[segment] = path
points_to_segments = segment_intersections(segments)
isect_points = list(points_to_segments.keys())
segs_to_points = collections.defaultdict(list)
for pt, segs in points_to_segments.items():
for seg in segs:
segs_to_points[seg].append(pt)
points_to_paths = collections.defaultdict(list)
for isect, segs in points_to_segments.items():
for seg in segs:
points_to_paths[isect].append(segs_to_paths[seg])
print(f"{len(isect_points)} intersections")
if 0:
debug_output(dwgw=DWGW, paths=paths, segments=segments, isects=isect_points)
debug = should_debug("strapify")
if debug:
dbgdwgs = iter(DrawingSequence(name="debugs_", paths=paths))
paths_to_do = set(paths)
paths_done = set()
xings = {} # pt -> xing
straps = [] # new smaller paths, ending at unders.
path = None
while paths_to_do:
next_paths = set()
next_paths.add(paths_to_do.pop())
while next_paths:
previous_path = path
path = next_paths.pop()
if debug:
dwg = next(dbgdwgs)
dwg.draw_segments(segments, rgb=(0, 0, 0), width=1)
dwg.draw_paths(paths_done, rgb=(0, 0, 0), width=3)
dwg.draw_paths(next_paths, rgb=(.7, .7, 0), width=9)
if previous_path:
dwg.draw_path(previous_path, rgb=(1, 0, 0), width=10, dash=[30, 30])
dwg.draw_path(path, rgb=(1, 0, 0), width=15)
dwg.fill_points([path[0]], rgb=(1, 0, 0), radius=15*3/2)
dwg.fill_points([path[1]], rgb=(1, 0, 0), radius=15*2/2)
partial_over = [pt for pt, xing in xings.items() if xing.under is None]
partial_under = [pt for pt, xing in xings.items() if xing.over is None]
dwg.circle_points(partial_over, rgb=(.8, 0, 0), radius=21, width=9)
dwg.circle_points(partial_under, rgb=(0, 0, .8), radius=21, width=9)
done = [pt for pt, xing in xings.items() if xing.under is not None and x
dwg.circle_points(done, rgb=(0, .8, 0), radius=15, width=3)
prev_piece = None
last_cut = None
first_piece = True
for piece, over in pieces_under_over(path, segs_to_points, xings):
if first_piece and debug:
dwg.cross_points([piece[0], piece[-1]], radius=20, rgb=(1, 0, 0), wi
dwg.finish()
if 0 and dwg.num > 10:
print()
import sys; sys.exit()
first_piece = False
cut = None
if over:
assert prev_piece is None
prev_piece = piece
if last_cut:
cut = last_cut
xing = xings.get(cut)
if xing is None:
xing = Xing(under=path)
xings[cut] = xing
else:
assert xing.under is None or xing.under == path
xing.under = path
last_cut = None
else:
if prev_piece:
cut = prev_piece[-1]
assert cut == piece[0]
strap = Strap(join_paths(prev_piece, piece), **strap_kwargs)
straps.append(strap)
xing = xings.get(cut)
if xing is None:
xing = Xing(over=path)
xings[cut] = xing
else:
assert xing.over is None or xing.over == path
xing.over = path
xing.over_piece = strap
else:
straps.append(Strap(piece, **strap_kwargs))
last_cut = piece[-1]
prev_piece = None
if cut:
for next_path in points_to_paths[cut]:
if next_path in paths_to_do:
paths_to_do.remove(next_path)
next_paths.add(next_path)
if prev_piece:
strap = Strap(prev_piece, **strap_kwargs)
straps.append(strap)
closed = (path[0] == path[-1])
if closed:
cut = prev_piece[-1]
xing = xings.get(cut)
if xing is None:
xing = Xing(over=path)
xings[cut] = xing
else:
xing.over = path
xing.over_piece = strap
paths_done.add(path)
if debug:
dwg.cross_points([piece[0], piece[-1]], radius=30, rotate=30, rgb=(0, 0,
dwg.finish()
if 0 and dwg.num > 10:
print()
import sys; sys.exit()
if 0:
bad = [pt for pt, xing in xings.items() if xing.over_piece is None]
debug_output(dwgw=DWGW, paths=paths, segments=segments, isects=bad)
if debug:
for strap in straps:
dwg = next(dbgdwgs)
dwg.draw_segments(segments, rgb=(0, 0, 0), width=1)
dwg.draw_path(strap.path, rgb=(1, 0, 0), width=3)
for s in strap.sides:
dwg.draw_path(s, rgb=(0, 0, 1), width=1)
dwg.finish()
for strap in straps:
for end in [0, -1]:
xing = xings.get(strap.path[end])
if xing is not None:
trimmers = xing.over_piece.sides
strap.sides = [trim_path(s, end, trimmers) for s in strap.sides]
return straps
def debug_output(dwgw=None, paths=None, segments=None, isects=None):
dwg = Drawing(paths=paths, name="debug.png")
dwg.draw_segments(segments, rgb=(0, 0, 0), width=1)
dup_segments = []
segments.sort()
for s1, s2 in zip(segments, segments[1:]):
if s1 == s2:
dup_segments.append(s1)
dwg.draw_segments(dup_segments, rgb=(1, 0, 0), width=7)
if dwgw is not None:
with dwg.style(rgb=(0, 0, 1), width=2, dash=[5, 5]):
dwg.rectangle(0, 0, dwgw, dwgw)
dwg.stroke()
if isects is not None:
dwg.circle_points(isects, radius=9, rgb=(0, .5, 0), width=3)
dwg.finish()
