359 lines
13 KiB
Python
359 lines
13 KiB
Python
# coding=utf-8
|
|
"""
|
|
Noyau geometrique du motif « Y fleche », sans dependance a inkex.
|
|
|
|
Le motif est un reseau triangulaire de « Y » identiques : trois bras a 0, 120
|
|
et 240 degres, chaque bras se terminant par un chevron dont les barbes sont
|
|
paralleles aux deux autres bras. La pointe de chaque fleche vient se loger dans
|
|
le « V » arriere du Y voisin, d'ou l'effet de chevrons imbriques.
|
|
|
|
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) : un angle positif tourne dans
|
|
le sens anti-horaire a l'ecran.
|
|
"""
|
|
|
|
import math
|
|
|
|
EPS = 1e-9
|
|
|
|
|
|
# --------------------------------------------------------------------------
|
|
# Outils generiques
|
|
# --------------------------------------------------------------------------
|
|
|
|
def rings_bbox(rings):
|
|
"""Boite englobante (xmin, ymin, xmax, ymax) d'un contour."""
|
|
xs = [p[0] for ring in rings for p in ring]
|
|
ys = [p[1] for ring in rings for p in ring]
|
|
return min(xs), min(ys), max(xs), max(ys)
|
|
|
|
|
|
def unit(angle_deg):
|
|
"""Vecteur unitaire d'angle donne, y vers le bas."""
|
|
a = math.radians(angle_deg)
|
|
return math.cos(a), -math.sin(a)
|
|
|
|
|
|
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 distance_point_segment(px, py, x1, y1, x2, y2):
|
|
"""Distance d'un point a un segment."""
|
|
dx, dy = x2 - x1, y2 - y1
|
|
length2 = dx * dx + dy * dy
|
|
if length2 < EPS:
|
|
return math.hypot(px - x1, py - y1)
|
|
t = max(0.0, min(1.0, ((px - x1) * dx + (py - y1) * dy) / length2))
|
|
return math.hypot(px - (x1 + t * dx), py - (y1 + t * dy))
|
|
|
|
|
|
def segment_intersection(p, q, a, b):
|
|
"""Parametre t sur [p, q] du point d'intersection avec [a, b], ou None.
|
|
|
|
Les segments paralleles (colineaires compris) sont ignores : un point de
|
|
contact isole ne change pas le cote interieur / exterieur d'un intervalle.
|
|
"""
|
|
rx, ry = q[0] - p[0], q[1] - p[1]
|
|
sx, sy = b[0] - a[0], b[1] - a[1]
|
|
denom = rx * sy - ry * sx
|
|
if abs(denom) < EPS:
|
|
return None
|
|
wx, wy = a[0] - p[0], a[1] - p[1]
|
|
t = (wx * sy - wy * sx) / denom
|
|
u = (wx * ry - wy * rx) / denom
|
|
if -EPS <= t <= 1 + EPS and -EPS <= u <= 1 + EPS:
|
|
return min(1.0, max(0.0, t))
|
|
return None
|
|
|
|
|
|
def segment_distance(p, q, a, b):
|
|
"""Distance minimale entre deux segments."""
|
|
if segment_intersection(p, q, a, b) is not None:
|
|
return 0.0
|
|
return min(distance_point_segment(p[0], p[1], a[0], a[1], b[0], b[1]),
|
|
distance_point_segment(q[0], q[1], a[0], a[1], b[0], b[1]),
|
|
distance_point_segment(a[0], a[1], p[0], p[1], q[0], q[1]),
|
|
distance_point_segment(b[0], b[1], p[0], p[1], q[0], q[1]))
|
|
|
|
|
|
# --------------------------------------------------------------------------
|
|
# Index spatial des aretes du contour
|
|
# --------------------------------------------------------------------------
|
|
|
|
class EdgeIndex:
|
|
"""Grille de hachage des aretes d'un contour.
|
|
|
|
Evite de comparer chaque segment du motif a toutes les aretes du contour :
|
|
un contour aplati peut compter des milliers d'aretes et le motif des
|
|
dizaines de milliers de segments.
|
|
"""
|
|
|
|
def __init__(self, rings, cells=64):
|
|
self.edges = []
|
|
for ring in rings:
|
|
n = len(ring)
|
|
for k in range(n):
|
|
a, b = ring[k], ring[(k + 1) % n]
|
|
if a != b:
|
|
self.edges.append((a, b))
|
|
|
|
xmin, ymin, xmax, ymax = rings_bbox(rings)
|
|
self.cell = max(xmax - xmin, ymax - ymin, EPS) / cells
|
|
self.grid = {}
|
|
self.rows = {}
|
|
for idx, (a, b) in enumerate(self.edges):
|
|
c0, r0 = self._cell(min(a[0], b[0]), min(a[1], b[1]))
|
|
c1, r1 = self._cell(max(a[0], b[0]), max(a[1], b[1]))
|
|
for r in range(r0, r1 + 1):
|
|
self.rows.setdefault(r, []).append(idx)
|
|
for c in range(c0, c1 + 1):
|
|
self.grid.setdefault((c, r), []).append(idx)
|
|
|
|
def _cell(self, x, y):
|
|
return int(math.floor(x / self.cell)), int(math.floor(y / self.cell))
|
|
|
|
def edges_near(self, xmin, ymin, xmax, ymax):
|
|
"""Indices des aretes dont une cellule touche la boite donnee."""
|
|
c0, r0 = self._cell(xmin, ymin)
|
|
c1, r1 = self._cell(xmax, ymax)
|
|
found = set()
|
|
for r in range(r0, r1 + 1):
|
|
for c in range(c0, c1 + 1):
|
|
found.update(self.grid.get((c, r), ()))
|
|
return found
|
|
|
|
def contains(self, x, y):
|
|
"""Point dans le contour, regle pair-impair (rayon vers +x)."""
|
|
inside = False
|
|
for idx in self.rows.get(self._cell(x, y)[1], ()):
|
|
(x1, y1), (x2, y2) = self.edges[idx]
|
|
if (y1 > y) != (y2 > y):
|
|
xcross = x1 + (y - y1) * (x2 - x1) / (y2 - y1)
|
|
if xcross > x:
|
|
inside = not inside
|
|
return inside
|
|
|
|
def crossings(self, p, q):
|
|
"""Parametres t des intersections de [p, q] avec le contour."""
|
|
ts = []
|
|
box = (min(p[0], q[0]), min(p[1], q[1]), max(p[0], q[0]), max(p[1], q[1]))
|
|
for idx in self.edges_near(*box):
|
|
a, b = self.edges[idx]
|
|
t = segment_intersection(p, q, a, b)
|
|
if t is not None:
|
|
ts.append(t)
|
|
return ts
|
|
|
|
def segment_clearance(self, p, q, limit):
|
|
"""Distance de [p, q] au contour, plafonnee a `limit`."""
|
|
box = (min(p[0], q[0]) - limit, min(p[1], q[1]) - limit,
|
|
max(p[0], q[0]) + limit, max(p[1], q[1]) + limit)
|
|
best = limit
|
|
for idx in self.edges_near(*box):
|
|
a, b = self.edges[idx]
|
|
best = min(best, segment_distance(p, q, a, b))
|
|
if best <= 0.0:
|
|
break
|
|
return best
|
|
|
|
|
|
# --------------------------------------------------------------------------
|
|
# Motif
|
|
# --------------------------------------------------------------------------
|
|
|
|
def motif_polylines(cx, cy, arm, barb, angle=0.0):
|
|
"""Polylignes d'un Y fleche centre en (cx, cy).
|
|
|
|
Ordre pense pour la decoupe laser (peu de deplacements a vide) :
|
|
chevron 1, tige 1-centre-2, chevron 2, tige centre-0, chevron 0.
|
|
Sans barbes (barb <= 0), seules les tiges sont renvoyees.
|
|
"""
|
|
tips, chevrons = [], []
|
|
for k in range(3):
|
|
a = angle + 120.0 * k
|
|
ux, uy = unit(a)
|
|
tip = (cx + arm * ux, cy + arm * uy)
|
|
tips.append(tip)
|
|
if barb > 0:
|
|
b1x, b1y = unit(a + 120.0)
|
|
b2x, b2y = unit(a - 120.0)
|
|
chevrons.append([(tip[0] + barb * b1x, tip[1] + barb * b1y), tip,
|
|
(tip[0] + barb * b2x, tip[1] + barb * b2y)])
|
|
center = (cx, cy)
|
|
stem_a = [tips[1], center, tips[2]]
|
|
stem_b = [center, tips[0]]
|
|
if not chevrons:
|
|
return [stem_a, stem_b]
|
|
return [chevrons[1], stem_a, chevrons[2], stem_b, chevrons[0]]
|
|
|
|
|
|
def lattice_centers(bbox, period, angle, reach, origin=(0.0, 0.0)):
|
|
"""Centres du reseau triangulaire couvrant `bbox` elargie de `reach`.
|
|
|
|
Renvoie une liste de (i, j, x, y) en ordre « serpentin » : ligne par
|
|
ligne (j), en alternant le sens de parcours (i) pour limiter les
|
|
deplacements a vide d'une decoupeuse qui suit l'ordre du document.
|
|
"""
|
|
xmin, ymin, xmax, ymax = bbox
|
|
xmin, ymin, xmax, ymax = xmin - reach, ymin - reach, xmax + reach, ymax + reach
|
|
a1x, a1y = unit(angle)
|
|
a2x, a2y = unit(angle + 60.0)
|
|
a1x, a1y, a2x, a2y = a1x * period, a1y * period, a2x * period, a2y * period
|
|
det = a1x * a2y - a2x * a1y
|
|
ox, oy = origin
|
|
|
|
def to_lattice(x, y):
|
|
dx, dy = x - ox, y - oy
|
|
return (dx * a2y - a2x * dy) / det, (a1x * dy - a1y * dx) / det
|
|
|
|
corners = [to_lattice(x, y) for x in (xmin, xmax) for y in (ymin, ymax)]
|
|
i0 = int(math.floor(min(c[0] for c in corners))) - 1
|
|
i1 = int(math.ceil(max(c[0] for c in corners))) + 1
|
|
j0 = int(math.floor(min(c[1] for c in corners))) - 1
|
|
j1 = int(math.ceil(max(c[1] for c in corners))) + 1
|
|
|
|
centers = []
|
|
for row, j in enumerate(range(j0, j1 + 1)):
|
|
columns = range(i0, i1 + 1) if row % 2 == 0 else range(i1, i0 - 1, -1)
|
|
for i in columns:
|
|
x = ox + i * a1x + j * a2x
|
|
y = oy + i * a1y + j * a2y
|
|
if xmin <= x <= xmax and ymin <= y <= ymax:
|
|
centers.append((i, j, x, y))
|
|
return centers
|
|
|
|
|
|
# --------------------------------------------------------------------------
|
|
# Decoupe au contour
|
|
# --------------------------------------------------------------------------
|
|
|
|
def clip_polyline(polyline, index):
|
|
"""Morceaux d'une polyligne situes a l'interieur du contour."""
|
|
pieces, current = [], None
|
|
for k in range(len(polyline) - 1):
|
|
p, q = polyline[k], polyline[k + 1]
|
|
ts = sorted(set([0.0, 1.0] + index.crossings(p, q)))
|
|
for t0, t1 in zip(ts, ts[1:]):
|
|
if t1 - t0 < EPS:
|
|
continue
|
|
tm = (t0 + t1) / 2.0
|
|
mid = (p[0] + tm * (q[0] - p[0]), p[1] + tm * (q[1] - p[1]))
|
|
if not index.contains(*mid):
|
|
if current:
|
|
pieces.append(current)
|
|
current = None
|
|
continue
|
|
a = (p[0] + t0 * (q[0] - p[0]), p[1] + t0 * (q[1] - p[1]))
|
|
b = (p[0] + t1 * (q[0] - p[0]), p[1] + t1 * (q[1] - p[1]))
|
|
if current and math.hypot(current[-1][0] - a[0], current[-1][1] - a[1]) < 1e-7:
|
|
current.append(b)
|
|
else:
|
|
if current:
|
|
pieces.append(current)
|
|
current = [a, b]
|
|
if current:
|
|
pieces.append(current)
|
|
return [piece for piece in pieces if polyline_length(piece) > 1e-6]
|
|
|
|
|
|
def polyline_length(polyline):
|
|
"""Longueur d'une polyligne."""
|
|
return sum(math.hypot(polyline[k + 1][0] - polyline[k][0],
|
|
polyline[k + 1][1] - polyline[k][1])
|
|
for k in range(len(polyline) - 1))
|
|
|
|
|
|
def motif_fits(polylines, index, clearance):
|
|
"""Motif entierement interieur, a au moins `clearance` du contour."""
|
|
for polyline in polylines:
|
|
for point in polyline:
|
|
if not index.contains(*point):
|
|
return False
|
|
for k in range(len(polyline) - 1):
|
|
p, q = polyline[k], polyline[k + 1]
|
|
if clearance > 0:
|
|
if index.segment_clearance(p, q, clearance) < clearance:
|
|
return False
|
|
elif index.crossings(p, q):
|
|
return False
|
|
return True
|
|
|
|
|
|
# --------------------------------------------------------------------------
|
|
# Remplissage
|
|
# --------------------------------------------------------------------------
|
|
|
|
def fill_pattern(rings, period, arm_ratio=0.83, barb_ratio=0.33, angle=0.0,
|
|
mode="clip", clearance=0.0, origin=(0.0, 0.0)):
|
|
"""Remplit un contour avec le motif « Y fleche ».
|
|
|
|
- period : distance entre deux centres voisins du reseau ;
|
|
- arm_ratio, barb_ratio : longueur des bras et des barbes en fraction
|
|
de la periode ;
|
|
- mode : « clip » decoupe les motifs au contour, « whole » ne garde que
|
|
les motifs entiers situes a au moins `clearance` du contour ;
|
|
- origin : point d'ancrage du reseau (garder la meme origine pour que
|
|
plusieurs formes voisines partagent un motif continu).
|
|
|
|
Renvoie une liste de motifs, chacun etant une liste de polylignes,
|
|
en ordre serpentin.
|
|
"""
|
|
if period <= 0 or not rings:
|
|
return []
|
|
arm = arm_ratio * period
|
|
barb = max(0.0, barb_ratio * period)
|
|
reach = arm + barb
|
|
index = EdgeIndex(rings)
|
|
motifs = []
|
|
for _i, _j, x, y in lattice_centers(rings_bbox(rings), period, angle, reach, origin):
|
|
polylines = motif_polylines(x, y, arm, barb, angle)
|
|
if mode == "whole":
|
|
if motif_fits(polylines, index, clearance):
|
|
motifs.append(polylines)
|
|
continue
|
|
kept = []
|
|
for polyline in polylines:
|
|
kept.extend(clip_polyline(polyline, index))
|
|
if kept:
|
|
motifs.append(kept)
|
|
return motifs
|
|
|
|
|
|
def polylines_to_d(polylines, precision=4):
|
|
"""Donnees `d` d'un chemin SVG (une sous-polyligne par M ... L ...)."""
|
|
fmt = "{:." + str(precision) + "f},{:." + str(precision) + "f}"
|
|
parts = []
|
|
for polyline in polylines:
|
|
points = [fmt.format(x, y) for x, y in polyline]
|
|
parts.append("M " + " L ".join(points))
|
|
return " ".join(parts)
|