Files

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])