9b93ca627b
Taux de remplissage en pourcentage, trajet de la tête en serpentin (plus proche voisin), hachures croisées, interface fr/en, tests et README. Co-Authored-By: Claude Sonnet 5.5 <noreply@anthropic.com>
326 lines
13 KiB
Python
326 lines
13 KiB
Python
# coding=utf-8
|
|
"""
|
|
Noyau de calcul de l'extension « Hatch Fill », sans dependance a inkex.
|
|
|
|
Remplit des contours avec des hachures paralleles et classe les traits dans
|
|
l'ordre ou une tete de laser les parcourt : la fin d'un trait est toujours
|
|
proche du debut du suivant (trajet en serpentin, aller-retour d'un trait au
|
|
suivant), ce qui limite les deplacements a vide.
|
|
|
|
Testable avec pytest seul et reutilisable hors Inkscape (scripts, schema
|
|
des parametres).
|
|
|
|
Conventions :
|
|
- un contour (`rings`) est une liste d'anneaux, chaque anneau etant une liste
|
|
de points (x, y) fermee implicitement ; les trous suivent la regle pair-impair ;
|
|
- une polyligne est une liste de points (x, y) ;
|
|
- l'axe y est oriente vers le bas (repere SVG) ; les angles sont en degres,
|
|
positifs dans le sens anti-horaire a l'ecran (comme dans Inkscape) ;
|
|
- le « repere des hachures » est le repere ou les traits sont horizontaux :
|
|
x suit le trait, y est perpendiculaire (ligne k a y = (k + phase) * pas).
|
|
"""
|
|
|
|
import math
|
|
from bisect import bisect_left
|
|
|
|
# Garde-fou : au-dela, le SVG produit devient inutilisable (et le calcul long).
|
|
MAX_LINES = 50000
|
|
|
|
|
|
class TooManyLines(ValueError):
|
|
"""Le motif demande plus de traits que MAX_LINES."""
|
|
|
|
|
|
def parse_color(value, default=("#b3b3b3", 1.0)):
|
|
"""Couleur Inkscape (entier RGBA decimal ou 0x..., ou #rrggbb[aa]).
|
|
|
|
Renvoie (couleur CSS #rrggbb, opacite entre 0 et 1). Le parametre
|
|
« color » d'Inkscape arrive sous forme d'entier RGBA ; on le decode
|
|
nous-memes pour ne pas dependre de l'API couleur d'inkex, qui a change
|
|
entre les versions 1.x.
|
|
"""
|
|
text = str(value).strip()
|
|
try:
|
|
if text.startswith("#"):
|
|
digits = text[1:]
|
|
if len(digits) == 3:
|
|
digits = "".join(c * 2 for c in digits)
|
|
if len(digits) == 6:
|
|
digits += "ff"
|
|
if len(digits) != 8:
|
|
return default
|
|
number = int(digits, 16)
|
|
else:
|
|
number = int(text, 0)
|
|
except ValueError:
|
|
return default
|
|
number &= 0xFFFFFFFF
|
|
red, green, blue = (number >> 24) & 255, (number >> 16) & 255, (number >> 8) & 255
|
|
alpha = (number & 255) / 255.0
|
|
return "#{:02x}{:02x}{:02x}".format(red, green, blue), round(alpha, 4)
|
|
|
|
|
|
def polylines_to_d(polylines, precision=4):
|
|
"""Donnees `d` d'un chemin SVG : une polyligne par sous-chemin."""
|
|
fmt = "{:.%df},{:.%df}" % (precision, precision)
|
|
parts = []
|
|
for polyline in polylines:
|
|
if len(polyline) < 2:
|
|
continue
|
|
parts.append("M " + fmt.format(*polyline[0]))
|
|
parts.extend("L " + fmt.format(*point) for point in polyline[1:])
|
|
return " ".join(parts)
|
|
|
|
|
|
# --------------------------------------------------------------------------
|
|
# Courbes -> anneaux
|
|
# --------------------------------------------------------------------------
|
|
|
|
def flatten_cubic_subpaths(subpaths, tolerance):
|
|
"""Aplatit des sous-chemins de Beziers cubiques en anneaux de points.
|
|
|
|
`subpaths` suit la forme du « superpath » d'inkex : un sous-chemin est une
|
|
liste de noeuds [controle_entrant, point, controle_sortant]. Les segments
|
|
droits ont leurs controles confondus avec les points. `tolerance` est
|
|
l'ecart maximal admis entre la courbe et la polyligne (meme unite que les
|
|
points). Les sous-chemins de moins de trois points sont ignores.
|
|
"""
|
|
rings = []
|
|
for nodes in subpaths:
|
|
ring = []
|
|
for i in range(len(nodes) - 1):
|
|
p0, p1 = nodes[i][1], nodes[i][2]
|
|
p2, p3 = nodes[i + 1][0], nodes[i + 1][1]
|
|
ring.append(tuple(p0))
|
|
# Ecart d'une Bezier a sa corde <= 3/4 * (derivee seconde max) / n^2
|
|
second = max(math.hypot(p0[0] - 2 * p1[0] + p2[0], p0[1] - 2 * p1[1] + p2[1]),
|
|
math.hypot(p1[0] - 2 * p2[0] + p3[0], p1[1] - 2 * p2[1] + p3[1]))
|
|
steps = min(500, max(1, int(math.ceil(math.sqrt(0.75 * second / tolerance)))))
|
|
# Controles sur la corde : segment droit, inutile de le decouper.
|
|
chord = math.hypot(p3[0] - p0[0], p3[1] - p0[1])
|
|
if chord > 0 and max(
|
|
abs((p3[0] - p0[0]) * (q[1] - p0[1]) - (p3[1] - p0[1]) * (q[0] - p0[0]))
|
|
for q in (p1, p2)) / chord <= tolerance:
|
|
steps = 1
|
|
for s in range(1, steps):
|
|
t = s / steps
|
|
mt = 1 - t
|
|
ring.append((
|
|
mt ** 3 * p0[0] + 3 * mt * mt * t * p1[0] + 3 * mt * t * t * p2[0] + t ** 3 * p3[0],
|
|
mt ** 3 * p0[1] + 3 * mt * mt * t * p1[1] + 3 * mt * t * t * p2[1] + t ** 3 * p3[1]))
|
|
if nodes:
|
|
ring.append(tuple(nodes[-1][1]))
|
|
if len(ring) > 1 and ring[0] == ring[-1]:
|
|
ring.pop()
|
|
if len(ring) >= 3:
|
|
rings.append(ring)
|
|
return rings
|
|
|
|
|
|
# --------------------------------------------------------------------------
|
|
# Hachures
|
|
# --------------------------------------------------------------------------
|
|
|
|
def spacing_from_density(density, line_width, cross=False):
|
|
"""Pas entre deux traits pour que `density` % de la zone soit noircie.
|
|
|
|
Un trait de largeur w tous les p couvre w / p de la surface : 100 %
|
|
correspond donc a des traits jointifs (p = w). En croise, il y a deux fois
|
|
plus de traits : le pas double pour garder la meme couverture.
|
|
"""
|
|
if not 0 < density <= 100:
|
|
raise ValueError("density must be in ]0, 100]")
|
|
if line_width <= 0:
|
|
raise ValueError("line_width must be positive")
|
|
return line_width * 100.0 / density * (2 if cross else 1)
|
|
|
|
|
|
def _frame_axes(angle):
|
|
"""Vecteurs unitaires (u le long des traits, v perpendiculaire)."""
|
|
a = math.radians(angle)
|
|
return (math.cos(a), -math.sin(a)), (math.sin(a), math.cos(a))
|
|
|
|
|
|
def to_frame(point, angle):
|
|
"""Point du document -> repere des hachures."""
|
|
u, v = _frame_axes(angle)
|
|
return point[0] * u[0] + point[1] * u[1], point[0] * v[0] + point[1] * v[1]
|
|
|
|
|
|
def from_frame(point, angle):
|
|
"""Point du repere des hachures -> document."""
|
|
u, v = _frame_axes(angle)
|
|
return point[0] * u[0] + point[1] * v[0], point[0] * u[1] + point[1] * v[1]
|
|
|
|
|
|
def scan_lines(rings, spacing, phase=0.0):
|
|
"""Intersections des traits horizontaux avec le contour (pair-impair).
|
|
|
|
La ligne k est a y = (k + phase) * spacing. Renvoie {k: [(x0, x1), ...]}
|
|
avec x0 < x1, les segments de chaque ligne etant tries. Une arete couvre
|
|
[ymin, ymax[ : un sommet exactement sur un trait n'est compte qu'une fois.
|
|
"""
|
|
crossings = {}
|
|
for ring in rings:
|
|
count = len(ring)
|
|
for i in range(count):
|
|
(x0, y0), (x1, y1) = ring[i], ring[(i + 1) % count]
|
|
if y0 == y1:
|
|
continue
|
|
if y0 > y1:
|
|
x0, y0, x1, y1 = x1, y1, x0, y0
|
|
first = int(math.ceil(y0 / spacing - phase))
|
|
last = int(math.ceil(y1 / spacing - phase)) - 1
|
|
slope = (x1 - x0) / (y1 - y0)
|
|
for k in range(first, last + 1):
|
|
crossings.setdefault(k, []).append(x0 + ((k + phase) * spacing - y0) * slope)
|
|
lines = {}
|
|
for k, xs in crossings.items():
|
|
xs.sort()
|
|
segments = [(xs[j], xs[j + 1]) for j in range(0, len(xs) - 1, 2)
|
|
if xs[j + 1] - xs[j] > 1e-9]
|
|
if segments:
|
|
lines[k] = segments
|
|
return lines
|
|
|
|
|
|
def order_lines(lines, spacing, phase=0.0, start=None):
|
|
"""Ordonne et oriente les segments pour minimiser les deplacements a vide.
|
|
|
|
Algorithme glouton du plus proche voisin sur les extremites : apres un
|
|
trait, on part de l'extremite non visitee la plus proche de l'endroit ou
|
|
la tete s'est arretee. Les extremites sont rangees par ligne et triees,
|
|
donc la recherche ne regarde que les lignes voisines (de plus en plus
|
|
loin) et s'arrete des que la ligne suivante ne peut plus faire mieux.
|
|
Sur une forme convexe, cela donne le serpentin attendu : on monte sur un
|
|
trait, on redescend sur le suivant, sans jamais revenir au point de depart.
|
|
|
|
`start` est la position initiale de la tete (repere des hachures) ; sans
|
|
elle, on commence par la premiere extremite de la premiere ligne.
|
|
Renvoie [(k, x_debut, x_fin), ...].
|
|
"""
|
|
segments = []
|
|
ends = {}
|
|
for k in sorted(lines):
|
|
for x0, x1 in lines[k]:
|
|
index = len(segments)
|
|
segments.append((k, x0, x1))
|
|
ends.setdefault(k, []).extend([(x0, index), (x1, index)])
|
|
if not segments:
|
|
return []
|
|
for entries in ends.values():
|
|
entries.sort()
|
|
k_min, k_max = min(ends), max(ends)
|
|
|
|
def nearest(x, y):
|
|
k_here = int(round(y / spacing - phase))
|
|
span = max(abs(k_here - k_min), abs(k_here - k_max))
|
|
best = None
|
|
for d in range(span + 1):
|
|
if best is not None and (d - 1) * spacing > best[0]:
|
|
break
|
|
for k in {k_here - d, k_here + d}:
|
|
entries = ends.get(k)
|
|
if not entries:
|
|
continue
|
|
dy = (k + phase) * spacing - y
|
|
at = bisect_left(entries, (x, -1))
|
|
for j in (at - 1, at):
|
|
if 0 <= j < len(entries):
|
|
dist = math.hypot(entries[j][0] - x, dy)
|
|
if best is None or dist < best[0]:
|
|
best = (dist, k, entries[j][0], entries[j][1])
|
|
return best
|
|
|
|
if start is None:
|
|
k0 = k_min
|
|
x0 = ends[k0][0][0]
|
|
found = (0.0, k0, x0, ends[k0][0][1])
|
|
else:
|
|
found = nearest(*start)
|
|
|
|
ordered = []
|
|
while found is not None:
|
|
_dist, k, x, index = found
|
|
_k, a, b = segments[index]
|
|
for end in (a, b):
|
|
entries = ends[k]
|
|
del entries[bisect_left(entries, (end, index))]
|
|
if not ends[k]:
|
|
del ends[k]
|
|
far = b if x == a else a
|
|
ordered.append((k, x, far))
|
|
if not ends:
|
|
break
|
|
k_min, k_max = min(ends), max(ends)
|
|
found = nearest(far, (k + phase) * spacing)
|
|
return ordered
|
|
|
|
|
|
def _phase(ymin, ymax, spacing, anchor):
|
|
"""Decalage des lignes (en fraction de pas).
|
|
|
|
« shape » : un trait au centre de chaque tranche de la forme (marges
|
|
egales en haut et en bas) ; « origin » : les lignes sont alignees sur l'origine du
|
|
document, donc continues d'une forme a l'autre.
|
|
"""
|
|
if anchor == "origin":
|
|
return 0.0
|
|
# Un trait au centre de chaque tranche d'un pas de haut : la couverture
|
|
# reste celle demandee et les marges haut / bas sont egales.
|
|
count = max(1, int(round((ymax - ymin) / spacing)))
|
|
first = ymin + ((ymax - ymin) - (count - 1) * spacing) / 2.0
|
|
return (first / spacing) % 1.0
|
|
|
|
|
|
def hatch_pass(rings, spacing, angle, anchor="shape", start=None):
|
|
"""Un jeu de hachures parallele a `angle`, deja classe dans l'ordre laser.
|
|
|
|
Renvoie une liste de polylignes [(p_debut, p_fin), ...]. Leve TooManyLines
|
|
si le pas est trop petit pour la forme.
|
|
"""
|
|
frame = [[to_frame(p, angle) for p in ring] for ring in rings if len(ring) >= 3]
|
|
if not frame:
|
|
return []
|
|
ys = [p[1] for ring in frame for p in ring]
|
|
ymin, ymax = min(ys), max(ys)
|
|
if (ymax - ymin) / spacing > MAX_LINES:
|
|
raise TooManyLines(int((ymax - ymin) / spacing))
|
|
phase = _phase(ymin, ymax, spacing, anchor)
|
|
lines = scan_lines(frame, spacing, phase)
|
|
if sum(len(segments) for segments in lines.values()) > MAX_LINES:
|
|
raise TooManyLines(sum(len(segments) for segments in lines.values()))
|
|
ordered = order_lines(lines, spacing, phase,
|
|
None if start is None else to_frame(start, angle))
|
|
result = []
|
|
for k, xa, xb in ordered:
|
|
y = (k + phase) * spacing
|
|
result.append([from_frame((xa, y), angle), from_frame((xb, y), angle)])
|
|
return result
|
|
|
|
|
|
def hatch(rings, spacing, angle=45.0, cross=False, anchor="shape"):
|
|
"""Hachures d'un contour, classees dans l'ordre de parcours du laser.
|
|
|
|
`cross` ajoute un second jeu perpendiculaire, parcouru apres le premier en
|
|
partant de la ou la tete s'est arretee. `anchor` : « shape » ou « origin »
|
|
(voir _phase).
|
|
"""
|
|
polylines = hatch_pass(rings, spacing, angle, anchor)
|
|
if cross:
|
|
start = polylines[-1][-1] if polylines else None
|
|
polylines += hatch_pass(rings, spacing, angle + 90.0, anchor, start)
|
|
return polylines
|
|
|
|
|
|
def travel_length(polylines):
|
|
"""Longueur des deplacements a vide : de la fin d'un trait au debut du suivant."""
|
|
return sum(math.hypot(b[0][0] - a[-1][0], b[0][1] - a[-1][1])
|
|
for a, b in zip(polylines, polylines[1:]))
|
|
|
|
|
|
def cutting_length(polylines):
|
|
"""Longueur totale des traits (laser allume)."""
|
|
return sum(math.hypot(q[0] - p[0], q[1] - p[1])
|
|
for polyline in polylines for p, q in zip(polyline, polyline[1:]))
|