412 lines
13 KiB
Python
412 lines
13 KiB
Python
# coding=utf-8
|
|
"""
|
|
Operations booleennes sur des polygones, en Python pur (sans inkex).
|
|
|
|
Sert a ne garder que l'encre reellement visible des cranes : une decoupeuse
|
|
laser grave tout trait present dans le fichier, meme cache sous un autre
|
|
objet. Il faut donc calculer la geometrie visible (difference, intersection,
|
|
union) au lieu de laisser les cranes du dessus masquer ceux du dessous.
|
|
|
|
Principe (balayage de Bentley-Ottmann, a la maniere de PolyBool de Sean
|
|
Connelly) : tous les cotes des polygones sont balayes de gauche a droite ;
|
|
chaque croisement coupe les cotes concernes ; chaque morceau connait alors,
|
|
pour chaque ensemble d'entree, le nombre d'enroulement juste au-dessus et
|
|
juste au-dessous de lui. Un predicat dit si un point est dans le resultat
|
|
selon son appartenance a chaque ensemble ; on garde les morceaux qui
|
|
separent un cote « dedans » d'un cote « dehors », puis on les enchaine en
|
|
anneaux fermes.
|
|
|
|
Conventions :
|
|
- un anneau est une liste de points (x, y), ferme implicitement ;
|
|
- un ensemble est (anneaux, regle), regle valant "evenodd" ou "nonzero" ;
|
|
- le resultat est une liste d'anneaux a remplir en regle pair-impair.
|
|
"""
|
|
|
|
import heapq
|
|
|
|
# Tous les points (sommets d'entree et croisements) sont cales sur une
|
|
# grille de pas GRID : deux points sont confondus s'ils sont egaux, et
|
|
# l'ordre de balayage est une simple comparaison de nombres. EPS sert aux
|
|
# produits vectoriels (alignements), EPS_T a la position le long d'un
|
|
# segment.
|
|
GRID = 1e-6
|
|
EPS = 1e-10
|
|
EPS_T = 1e-9
|
|
# Un croisement plus proche que SNAP d'une extremite est rabattu sur elle :
|
|
# sans cela, deux croisements presque confondus creent des segments de
|
|
# quelques millioniemes que les tests d'alignement jugent mal.
|
|
SNAP = 1e-5
|
|
|
|
|
|
def snap(p):
|
|
return (round(p[0] / GRID) * GRID, round(p[1] / GRID) * GRID)
|
|
|
|
|
|
def _compare(a, b):
|
|
"""Ordre de balayage : x croissant, puis y croissant."""
|
|
if a == b:
|
|
return 0
|
|
return -1 if a < b else 1
|
|
|
|
|
|
def _same(a, b):
|
|
return a == b
|
|
|
|
|
|
def _near(a, b):
|
|
return abs(a[0] - b[0]) < SNAP and abs(a[1] - b[1]) < SNAP
|
|
|
|
|
|
def _above_or_on(pt, left, right):
|
|
return ((right[0] - left[0]) * (pt[1] - left[1])
|
|
- (right[1] - left[1]) * (pt[0] - left[0])) >= -EPS
|
|
|
|
|
|
def _collinear(a, b, c):
|
|
return abs((a[0] - b[0]) * (b[1] - c[1]) - (b[0] - c[0]) * (a[1] - b[1])) < EPS
|
|
|
|
|
|
def _between(p, left, right):
|
|
"""p (aligne sur left-right) est-il strictement entre les deux ?"""
|
|
dpx, dpy = p[0] - left[0], p[1] - left[1]
|
|
drx, dry = right[0] - left[0], right[1] - left[1]
|
|
dot = dpx * drx + dpy * dry
|
|
if dot < EPS:
|
|
return False
|
|
return dot - (drx * drx + dry * dry) <= -EPS
|
|
|
|
|
|
def _along(v):
|
|
"""Position d'un parametre sur un segment : -2 avant, -1 au debut,
|
|
0 dedans, 1 a la fin, 2 apres."""
|
|
if v <= -EPS_T:
|
|
return -2
|
|
if v < EPS_T:
|
|
return -1
|
|
if v - 1 <= -EPS_T:
|
|
return 0
|
|
if v - 1 < EPS_T:
|
|
return 1
|
|
return 2
|
|
|
|
|
|
def _lines_intersect(a0, a1, b0, b1):
|
|
adx, ady = a1[0] - a0[0], a1[1] - a0[1]
|
|
bdx, bdy = b1[0] - b0[0], b1[1] - b0[1]
|
|
axb = adx * bdy - ady * bdx
|
|
if abs(axb) < EPS:
|
|
return None
|
|
dx, dy = a0[0] - b0[0], a0[1] - b0[1]
|
|
a = (bdx * dy - bdy * dx) / axb
|
|
b = (adx * dy - ady * dx) / axb
|
|
return _along(a), _along(b), snap((a0[0] + a * adx, a0[1] + a * ady))
|
|
|
|
|
|
class _Segment(object):
|
|
__slots__ = ("start", "end", "delta", "below", "above")
|
|
|
|
def __init__(self, start, end, delta):
|
|
self.start, self.end, self.delta = start, end, delta
|
|
self.below = self.above = None
|
|
|
|
|
|
class _Event(object):
|
|
__slots__ = ("is_start", "pt", "seg", "other", "entry")
|
|
|
|
def __init__(self, is_start, pt, seg):
|
|
self.is_start, self.pt, self.seg = is_start, pt, seg
|
|
self.other = None
|
|
self.entry = None
|
|
|
|
|
|
class _Tie(object):
|
|
"""Departage de deux evenements au meme point (cle figee a l'insertion)."""
|
|
__slots__ = ("is_start", "p1", "p2")
|
|
|
|
def __init__(self, ev):
|
|
self.is_start, self.p1, self.p2 = ev.is_start, ev.pt, ev.other.pt
|
|
|
|
def compare(self, other):
|
|
if self.p2 == other.p2:
|
|
return 0
|
|
if self.is_start != other.is_start:
|
|
# A meme point, les fins passent avant les debuts.
|
|
return 1 if self.is_start else -1
|
|
if other.is_start:
|
|
return 1 if _above_or_on(self.p2, other.p1, other.p2) else -1
|
|
return 1 if _above_or_on(self.p2, other.p2, other.p1) else -1
|
|
|
|
def __lt__(self, other):
|
|
return self.compare(other) < 0
|
|
|
|
def __eq__(self, other):
|
|
return self.compare(other) == 0
|
|
|
|
|
|
def _status_compare(ev1, ev2):
|
|
a1, a2 = ev1.seg.start, ev1.seg.end
|
|
b1, b2 = ev2.seg.start, ev2.seg.end
|
|
if _collinear(a1, b1, b2):
|
|
if _collinear(a2, b1, b2):
|
|
return 1
|
|
return 1 if _above_or_on(a2, b1, b2) else -1
|
|
return 1 if _above_or_on(a1, b1, b2) else -1
|
|
|
|
|
|
class _Sweep(object):
|
|
|
|
def __init__(self, count):
|
|
self.count = count
|
|
self.heap = []
|
|
self.serial = 0
|
|
self.status = []
|
|
|
|
# -- file des evenements (tas, suppressions paresseuses) ---------------
|
|
|
|
def push(self, ev):
|
|
self.serial += 1
|
|
ev.entry = self.serial
|
|
# Le point d'abord (comparaison rapide), le departage ensuite.
|
|
heapq.heappush(self.heap, (ev.pt, _Tie(ev), self.serial, ev))
|
|
|
|
def head(self):
|
|
heap = self.heap
|
|
while heap and heap[0][3].entry != heap[0][2]:
|
|
heapq.heappop(heap)
|
|
return heap[0][3] if heap else None
|
|
|
|
def add_segment(self, seg):
|
|
start = _Event(True, seg.start, seg)
|
|
end = _Event(False, seg.end, seg)
|
|
start.other, end.other = end, start
|
|
self.push(start)
|
|
self.push(end)
|
|
return start
|
|
|
|
def update_end(self, ev, pt):
|
|
ev.other.entry = None
|
|
ev.seg.end = pt
|
|
ev.other.pt = pt
|
|
self.push(ev.other)
|
|
|
|
def divide(self, ev, pt):
|
|
# La coupe doit tomber strictement entre les extremites, dans l'ordre
|
|
# du balayage, sinon elle retournerait un morceau.
|
|
if not (ev.seg.start < pt < ev.seg.end):
|
|
return None
|
|
piece = _Segment(pt, ev.seg.end, list(ev.seg.delta))
|
|
self.update_end(ev, pt)
|
|
return self.add_segment(piece)
|
|
|
|
def add_ring(self, ring, index):
|
|
ring = [snap(p) for p in ring]
|
|
n = len(ring)
|
|
for i in range(n):
|
|
p1, p2 = ring[i - 1], ring[i]
|
|
forward = _compare(p1, p2)
|
|
if forward == 0:
|
|
continue
|
|
delta = [0] * self.count
|
|
# Le sens d'origine du cote donne le signe de l'enroulement.
|
|
delta[index] = 1 if forward < 0 else -1
|
|
if forward < 0:
|
|
self.add_segment(_Segment(p1, p2, delta))
|
|
else:
|
|
self.add_segment(_Segment(p2, p1, delta))
|
|
|
|
# -- croisements --------------------------------------------------------
|
|
|
|
def check(self, ev1, ev2):
|
|
"""Coupe ev1 et ev2 a leur croisement ; renvoie ev2 s'ils sont confondus."""
|
|
a1, a2 = ev1.seg.start, ev1.seg.end
|
|
b1, b2 = ev2.seg.start, ev2.seg.end
|
|
cross = _lines_intersect(a1, a2, b1, b2)
|
|
if cross is None:
|
|
# Paralleles : seul le cas aligne et chevauchant compte.
|
|
if not _collinear(a1, a2, b1):
|
|
return None
|
|
if _same(a1, b2) or _same(a2, b1):
|
|
return None
|
|
a1_b1, a2_b2 = _same(a1, b1), _same(a2, b2)
|
|
if a1_b1 and a2_b2:
|
|
return ev2
|
|
a1_between = not a1_b1 and _between(a1, b1, b2)
|
|
a2_between = not a2_b2 and _between(a2, b1, b2)
|
|
if a1_b1:
|
|
if a2_between:
|
|
self.divide(ev2, a2)
|
|
else:
|
|
self.divide(ev1, b2)
|
|
return ev2
|
|
if a1_between:
|
|
if not a2_b2:
|
|
if a2_between:
|
|
self.divide(ev2, a2)
|
|
else:
|
|
self.divide(ev1, b2)
|
|
self.divide(ev2, a1)
|
|
return None
|
|
along_a, along_b, pt = cross
|
|
# Croisement confondu avec un sommet : on le rabat sur ce sommet.
|
|
if along_a == 0:
|
|
if _near(pt, a1):
|
|
along_a = -1
|
|
elif _near(pt, a2):
|
|
along_a = 1
|
|
if along_b == 0:
|
|
if _near(pt, b1):
|
|
along_b, pt = -1, b1
|
|
elif _near(pt, b2):
|
|
along_b, pt = 1, b2
|
|
if along_a == -1:
|
|
pt = a1
|
|
elif along_a == 1:
|
|
pt = a2
|
|
if along_a == 0:
|
|
if along_b == -1:
|
|
self.divide(ev1, b1)
|
|
elif along_b == 0:
|
|
self.divide(ev1, pt)
|
|
elif along_b == 1:
|
|
self.divide(ev1, b2)
|
|
if along_b == 0:
|
|
if along_a == -1:
|
|
self.divide(ev2, a1)
|
|
elif along_a == 0:
|
|
self.divide(ev2, pt)
|
|
elif along_a == 1:
|
|
self.divide(ev2, a2)
|
|
return None
|
|
|
|
# -- balayage -----------------------------------------------------------
|
|
|
|
def run(self):
|
|
status = self.status
|
|
result = []
|
|
zero = [0] * self.count
|
|
while True:
|
|
ev = self.head()
|
|
if ev is None:
|
|
break
|
|
if ev.is_start:
|
|
index = len(status)
|
|
for i, here in enumerate(status):
|
|
if _status_compare(ev, here) > 0:
|
|
index = i
|
|
break
|
|
above = status[index - 1] if index > 0 else None
|
|
below = status[index] if index < len(status) else None
|
|
same = self.check(ev, above) if above is not None else None
|
|
if same is None and below is not None:
|
|
same = self.check(ev, below)
|
|
if same is not None:
|
|
# Cotes confondus : un seul morceau, enroulements cumules.
|
|
# `same` est deja dans le statut : son enroulement au-dessus
|
|
# change aussi.
|
|
for k, d in enumerate(ev.seg.delta):
|
|
same.seg.delta[k] += d
|
|
if same.seg.above is not None:
|
|
same.seg.above[k] += d
|
|
ev.entry = None
|
|
ev.other.entry = None
|
|
if self.head() is not ev:
|
|
continue
|
|
base = below.seg.above if below is not None else zero
|
|
ev.seg.below = list(base)
|
|
ev.seg.above = [b + d for b, d in zip(base, ev.seg.delta)]
|
|
status.insert(index, ev)
|
|
ev.entry = None
|
|
else:
|
|
start = ev.other
|
|
i = status.index(start)
|
|
if 0 < i < len(status) - 1:
|
|
self.check(status[i - 1], status[i + 1])
|
|
del status[i]
|
|
result.append(ev.seg)
|
|
ev.entry = None
|
|
return result
|
|
|
|
|
|
def _inside(winding, rule):
|
|
return (winding % 2 == 1) if rule == "evenodd" else (winding != 0)
|
|
|
|
|
|
def _chain(segments):
|
|
"""Morceaux de frontiere -> anneaux fermes."""
|
|
def key(p):
|
|
return (round(p[0] * 1e6), round(p[1] * 1e6))
|
|
|
|
ends = {}
|
|
for i, seg in enumerate(segments):
|
|
ends.setdefault(key(seg.start), []).append(i)
|
|
ends.setdefault(key(seg.end), []).append(i)
|
|
used = [False] * len(segments)
|
|
rings = []
|
|
for i, seg in enumerate(segments):
|
|
if used[i]:
|
|
continue
|
|
used[i] = True
|
|
ring = [seg.start]
|
|
first = key(seg.start)
|
|
point = seg.end
|
|
while key(point) != first:
|
|
ring.append(point)
|
|
nxt = None
|
|
for j in ends.get(key(point), ()):
|
|
if not used[j]:
|
|
nxt = j
|
|
break
|
|
if nxt is None:
|
|
ring = None
|
|
break
|
|
used[nxt] = True
|
|
other = segments[nxt]
|
|
point = other.end if key(other.start) == key(point) else other.start
|
|
if ring and len(ring) >= 3:
|
|
rings.append(_drop_collinear(ring))
|
|
return [ring for ring in rings if len(ring) >= 3]
|
|
|
|
|
|
def _drop_collinear(ring):
|
|
result = []
|
|
n = len(ring)
|
|
for i in range(n):
|
|
a, b, c = ring[i - 1], ring[i], ring[(i + 1) % n]
|
|
if not _collinear(a, b, c):
|
|
result.append(b)
|
|
return result
|
|
|
|
|
|
def boolean(sets, predicate):
|
|
"""Combinaison booleenne de plusieurs ensembles de polygones.
|
|
|
|
`sets` : liste de (anneaux, regle) ; `predicate` recoit un tuple de
|
|
booleens (le point est-il dans chaque ensemble ?) et dit s'il est dans le
|
|
resultat. Renvoie des anneaux a remplir en regle pair-impair.
|
|
"""
|
|
rules = [rule for _rings, rule in sets]
|
|
sweep = _Sweep(len(sets))
|
|
for index, (rings, _rule) in enumerate(sets):
|
|
for ring in rings:
|
|
if len(ring) >= 3:
|
|
sweep.add_ring(ring, index)
|
|
kept = []
|
|
for seg in sweep.run():
|
|
below = predicate(tuple(_inside(w, r) for w, r in zip(seg.below, rules)))
|
|
above = predicate(tuple(_inside(w, r) for w, r in zip(seg.above, rules)))
|
|
if below != above:
|
|
kept.append(seg)
|
|
return _chain(kept)
|
|
|
|
|
|
def union(rings, rule="nonzero"):
|
|
return boolean([(rings, rule)], lambda inside: inside[0])
|
|
|
|
|
|
def intersection(a, b, rule_a="evenodd", rule_b="evenodd"):
|
|
return boolean([(a, rule_a), (b, rule_b)], lambda inside: inside[0] and inside[1])
|
|
|
|
|
|
def difference(a, b, rule_a="evenodd", rule_b="evenodd"):
|
|
return boolean([(a, rule_a), (b, rule_b)], lambda inside: inside[0] and not inside[1])
|