501 lines
21 KiB
Python
501 lines
21 KiB
Python
# coding=utf-8
|
|
"""
|
|
Noyau de calcul de l'extension « Wavy Ribbon Pattern Fill », sans dependance a inkex.
|
|
|
|
Testable avec pytest seul et reutilisable hors Inkscape (scripts, schema
|
|
des parametres).
|
|
|
|
Le motif : un fond de traits verticaux au pas `spacing`, sur lequel sont poses
|
|
des rubans en S. Un ruban compte `lines` traits ; chaque trait est le meme
|
|
profil en S (arc, droite, arc) translate de (1 pas, `stagger` pas). Un ruban se
|
|
decale lateralement de `shift` pas : ses extremites retombent donc sur les
|
|
traits du fond, qu'il masque seulement sur la hauteur de son ondulation. Les
|
|
rubans sont ranges en quinconce, une rangee sur deux etant le miroir de l'autre.
|
|
|
|
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 longueurs du motif (`shift`, `height`, `radius`, `stagger`, `columns`,
|
|
`rows`) sont exprimees en nombre de pas (`spacing`).
|
|
"""
|
|
|
|
import math
|
|
from bisect import bisect_right
|
|
|
|
|
|
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)
|
|
|
|
|
|
def rotate_points(points, angle, center=(0.0, 0.0)):
|
|
"""Rotation de `angle` degres autour de `center` (sens horaire a l'ecran,
|
|
comme rotate() en SVG)."""
|
|
a = math.radians(angle)
|
|
cos_a, sin_a = math.cos(a), math.sin(a)
|
|
cx, cy = center
|
|
return [(cx + (x - cx) * cos_a - (y - cy) * sin_a,
|
|
cy + (x - cx) * sin_a + (y - cy) * cos_a) for x, y in points]
|
|
|
|
|
|
def rings_bounds(rings):
|
|
"""Boite englobante (xmin, ymin, xmax, ymax), None si aucun point."""
|
|
xs = [x for ring in rings for x, _y in ring]
|
|
ys = [y for ring in rings for _x, y in ring]
|
|
if not xs:
|
|
return None
|
|
return min(xs), min(ys), max(xs), max(ys)
|
|
|
|
|
|
def wave_profile(shift, height, radius, tolerance):
|
|
"""Profil en S d'un trait : arc, droite, arc.
|
|
|
|
Points (x, v) de (0, 0) a (shift, height), v compte vers le haut ; la
|
|
tangente est verticale aux deux bouts. x et v sont croissants : le profil
|
|
est une fonction v(x), ce dont depend le calcul des traits masques. Le
|
|
rayon est donc borne a height / 2 (au-dela la courbe reviendrait en arriere).
|
|
"""
|
|
radius = max(0.0, min(radius, height / 2.0))
|
|
if radius < tolerance:
|
|
return [(0.0, 0.0), (shift, height)]
|
|
a, b = shift - 2.0 * radius, height
|
|
distance = math.hypot(a, b)
|
|
# Angle de la partie droite avec la verticale : tangente interieure commune
|
|
# aux deux cercles de rayon `radius` centres en (radius, 0) et
|
|
# (shift - radius, height).
|
|
alpha = math.atan2(a, b) + math.asin(min(1.0, 2.0 * radius / distance))
|
|
step = 2.0 * math.acos(max(-1.0, 1.0 - tolerance / radius))
|
|
steps = max(2, int(math.ceil(alpha / step)))
|
|
points = []
|
|
for k in range(steps + 1):
|
|
theta = alpha * k / steps
|
|
points.append((radius - radius * math.cos(theta), radius * math.sin(theta)))
|
|
for k in range(steps, -1, -1):
|
|
theta = alpha * k / steps
|
|
point = (shift - radius + radius * math.cos(theta),
|
|
height - radius * math.sin(theta))
|
|
# Sans partie droite, les deux arcs se rejoignent au meme point.
|
|
if math.hypot(point[0] - points[-1][0], point[1] - points[-1][1]) > tolerance * 1e-3:
|
|
points.append(point)
|
|
points[0] = (0.0, 0.0)
|
|
points[-1] = (shift, height)
|
|
return points
|
|
|
|
|
|
class EdgeIndex(object):
|
|
"""Aretes d'un contour rangees par bandes horizontales, pour decouper des
|
|
polylignes sans tester chaque arete."""
|
|
|
|
def __init__(self, rings):
|
|
self.edges = []
|
|
for ring in rings:
|
|
for k in range(len(ring)):
|
|
(x1, y1), (x2, y2) = ring[k - 1], ring[k]
|
|
if x1 != x2 or y1 != y2:
|
|
self.edges.append((x1, y1, x2, y2))
|
|
ys = [e[1] for e in self.edges] + [e[3] for e in self.edges]
|
|
self.ymin = min(ys) if ys else 0.0
|
|
self.ymax = max(ys) if ys else 0.0
|
|
count = max(1, min(1024, len(self.edges) // 2))
|
|
self.band = (self.ymax - self.ymin) / count or 1.0
|
|
self.bands = [[] for _ in range(count)]
|
|
for index, (_x1, y1, _x2, y2) in enumerate(self.edges):
|
|
for band in range(self._band(min(y1, y2)), self._band(max(y1, y2)) + 1):
|
|
self.bands[band].append(index)
|
|
|
|
def _band(self, y):
|
|
return max(0, min(len(self.bands) - 1, int((y - self.ymin) / self.band)))
|
|
|
|
def inside(self, x, y):
|
|
"""Regle pair-impair."""
|
|
if y < self.ymin or y > self.ymax:
|
|
return False
|
|
inside = False
|
|
for index in self.bands[self._band(y)]:
|
|
x1, y1, x2, y2 = self.edges[index]
|
|
if (y1 > y) != (y2 > y) and x < x1 + (y - y1) * (x2 - x1) / (y2 - y1):
|
|
inside = not inside
|
|
return inside
|
|
|
|
def crossings(self, p, q):
|
|
"""Positions (entre 0 et 1) ou le segment p-q coupe une arete."""
|
|
low, high = min(p[1], q[1]), max(p[1], q[1])
|
|
if high < self.ymin or low > self.ymax:
|
|
return []
|
|
first, last = self._band(low), self._band(high)
|
|
if first == last:
|
|
candidates = self.bands[first]
|
|
else:
|
|
candidates = set()
|
|
for band in range(first, last + 1):
|
|
candidates.update(self.bands[band])
|
|
rx, ry = q[0] - p[0], q[1] - p[1]
|
|
found = []
|
|
for index in candidates:
|
|
x1, y1, x2, y2 = self.edges[index]
|
|
ex, ey = x2 - x1, y2 - y1
|
|
denominator = rx * ey - ry * ex
|
|
if denominator == 0.0:
|
|
continue
|
|
t = ((x1 - p[0]) * ey - (y1 - p[1]) * ex) / denominator
|
|
u = ((x1 - p[0]) * ry - (y1 - p[1]) * rx) / denominator
|
|
if 0.0 <= t <= 1.0 and 0.0 <= u <= 1.0:
|
|
found.append(t)
|
|
return sorted(found)
|
|
|
|
def clip(self, polyline, keep_inside=True):
|
|
"""Morceaux de la polyligne situes dans le contour (ou hors de lui)."""
|
|
pieces, current, state = [], [], None
|
|
for k in range(len(polyline) - 1):
|
|
p, q = polyline[k], polyline[k + 1]
|
|
if p == q:
|
|
continue
|
|
cuts = self.crossings(p, q)
|
|
if not cuts and state is not None:
|
|
spans = [(0.0, 1.0, state)]
|
|
else:
|
|
# L'etat n'est reteste qu'aux croisements : le milieu de chaque
|
|
# troncon decide, ce qui absorbe les contacts sans traversee.
|
|
spans, bounds = [], [0.0] + cuts + [1.0]
|
|
for t0, t1 in zip(bounds, bounds[1:]):
|
|
if t1 - t0 > 1e-9:
|
|
tm = (t0 + t1) / 2.0
|
|
spans.append((t0, t1, self.inside(p[0] + tm * (q[0] - p[0]),
|
|
p[1] + tm * (q[1] - p[1]))))
|
|
for t0, t1, inside in spans:
|
|
state = inside
|
|
if inside != keep_inside:
|
|
if len(current) > 1:
|
|
pieces.append(current)
|
|
current = []
|
|
continue
|
|
start = p if t0 == 0.0 else (p[0] + t0 * (q[0] - p[0]), p[1] + t0 * (q[1] - p[1]))
|
|
end = q if t1 == 1.0 else (p[0] + t1 * (q[0] - p[0]), p[1] + t1 * (q[1] - p[1]))
|
|
if not current:
|
|
current = [start]
|
|
current.append(end)
|
|
if len(current) > 1:
|
|
pieces.append(current)
|
|
return pieces
|
|
|
|
|
|
def subtract_intervals(intervals, holes):
|
|
"""Intervalles (a, b) prives des intervalles `holes`."""
|
|
for low, high in holes:
|
|
kept = []
|
|
for a, b in intervals:
|
|
if high <= a or low >= b:
|
|
kept.append((a, b))
|
|
continue
|
|
if low > a:
|
|
kept.append((a, low))
|
|
if high < b:
|
|
kept.append((high, b))
|
|
intervals = kept
|
|
return intervals
|
|
|
|
|
|
def join_polylines(polylines, digits=9):
|
|
"""Soude les polylignes qui se suivent (deux extremites exactement au meme
|
|
point) et retire les points alignes : moins de sous-chemins, traces continus."""
|
|
def key(point):
|
|
return round(point[0], digits), round(point[1], digits)
|
|
|
|
lines = [list(polyline) for polyline in polylines]
|
|
owner = list(range(len(lines)))
|
|
ends = {}
|
|
for index, line in enumerate(lines):
|
|
ends.setdefault(key(line[0]), []).append(index)
|
|
ends.setdefault(key(line[-1]), []).append(index)
|
|
|
|
def find(index):
|
|
while owner[index] != index:
|
|
owner[index] = owner[owner[index]]
|
|
index = owner[index]
|
|
return index
|
|
|
|
for point, indexes in ends.items():
|
|
if len(indexes) != 2:
|
|
continue # bout libre, ou jonction a trois traits
|
|
a, b = find(indexes[0]), find(indexes[1])
|
|
if a == b:
|
|
continue
|
|
if key(lines[a][-1]) != point:
|
|
lines[a].reverse()
|
|
if key(lines[b][0]) != point:
|
|
lines[b].reverse()
|
|
lines[a].extend(lines[b][1:])
|
|
lines[b] = None
|
|
owner[b] = a
|
|
|
|
joined = []
|
|
for line in lines:
|
|
if line is None:
|
|
continue
|
|
kept = [line[0]]
|
|
for k in range(1, len(line) - 1):
|
|
(ax, ay), (bx, by), (cx, cy) = kept[-1], line[k], line[k + 1]
|
|
cross = (bx - ax) * (cy - by) - (by - ay) * (cx - bx)
|
|
dot = (bx - ax) * (cx - bx) + (by - ay) * (cy - by)
|
|
if abs(cross) > 1e-12 * max(1.0, abs(dot)) or dot <= 0:
|
|
kept.append(line[k])
|
|
kept.append(line[-1])
|
|
joined.append(kept)
|
|
return joined
|
|
|
|
|
|
class RibbonPattern(object):
|
|
"""Geometrie du motif pour un jeu de parametres.
|
|
|
|
`spacing` est le pas des traits (unites du document) ; `lines` le nombre de
|
|
traits d'un ruban ; `shift` son decalage lateral ; `height` la hauteur du S
|
|
d'un trait ; `radius` le rayon de ses deux virages ; `stagger` le decalage
|
|
vertical d'un trait au suivant ; `columns` et `rows` les pas du quinconce.
|
|
Tout sauf `spacing` est en nombre de pas. `origin` cale la grille.
|
|
"""
|
|
|
|
def __init__(self, spacing, lines=5, shift=6, height=7.0, radius=2.8,
|
|
stagger=1.0, columns=8, rows=7.75, origin=(0.0, 0.0), tolerance=None):
|
|
if spacing <= 0 or height <= 0 or rows <= 0:
|
|
raise ValueError("spacing, height et rows doivent etre strictement positifs")
|
|
if int(lines) < 2 or int(shift) < 1 or int(columns) < 1:
|
|
raise ValueError("lines >= 2, shift >= 1 et columns >= 1")
|
|
if stagger < 0 or radius < 0:
|
|
# Un decalage negatif ferait se croiser les traits d'un meme ruban.
|
|
raise ValueError("stagger et radius doivent etre positifs ou nuls")
|
|
self.spacing = float(spacing)
|
|
self.lines = int(lines)
|
|
self.shift = int(shift)
|
|
self.columns = int(columns)
|
|
self.height = height * self.spacing
|
|
self.stagger = stagger * self.spacing
|
|
self.row_step = rows * self.spacing
|
|
self.origin = origin
|
|
self.span = self.shift + self.lines - 1 # largeur d'un ruban, en pas
|
|
self.region_height = self.height + (self.lines - 1) * self.stagger
|
|
self.tolerance = tolerance or self.spacing / 200.0
|
|
self.profile = wave_profile(self.shift * self.spacing, self.height,
|
|
radius * self.spacing, self.tolerance)
|
|
self._profile_x = [x for x, _v in self.profile]
|
|
|
|
def grid_x(self, index):
|
|
"""Abscisse du trait de fond numero `index`."""
|
|
return self.origin[0] + index * self.spacing
|
|
|
|
def _rise(self, x):
|
|
"""Hauteur v du profil a l'abscisse x (interpolation)."""
|
|
xs = self._profile_x
|
|
if x <= xs[0]:
|
|
return 0.0
|
|
if x >= xs[-1]:
|
|
return self.height
|
|
k = bisect_right(xs, x)
|
|
(x0, v0), (x1, v1) = self.profile[k - 1], self.profile[k]
|
|
return v0 + (v1 - v0) * (x - x0) / (x1 - x0)
|
|
|
|
def pieces(self, bounds):
|
|
"""Rubans dont l'ondulation touche `bounds` = (xmin, ymin, xmax, ymax).
|
|
|
|
Un ruban = (rangee, colonne, premier trait de fond, y haut, y bas,
|
|
miroir). Les rangees impaires sont en miroir et decalees de `columns`.
|
|
"""
|
|
xmin, ymin, xmax, ymax = bounds
|
|
ox, oy = self.origin
|
|
half = self.region_height / 2.0
|
|
period = 2 * self.columns
|
|
found = []
|
|
first_row = int(math.ceil((ymin - half - oy) / self.row_step))
|
|
last_row = int(math.floor((ymax + half - oy) / self.row_step))
|
|
for row in range(first_row, last_row + 1):
|
|
offset = self.columns if row % 2 else 0
|
|
top = oy + row * self.row_step - half
|
|
first = int(math.ceil(((xmin - ox) / self.spacing - self.span - offset) / period))
|
|
last = int(math.floor(((xmax - ox) / self.spacing - offset) / period))
|
|
for column in range(first, last + 1):
|
|
found.append((row, column, column * period + offset,
|
|
top, top + self.region_height, bool(row % 2)))
|
|
return found
|
|
|
|
def _x(self, piece, rel, dx=0.0):
|
|
"""Abscisse a `dx` du trait de rang `rel` dans le ruban (miroir gere).
|
|
Avec dx nul, c'est exactement grid_x : les bouts se soudent au fond."""
|
|
_row, _column, left, _top, _bottom, mirror = piece
|
|
if mirror:
|
|
return self.grid_x(left + self.span - rel) - dx
|
|
return self.grid_x(left + rel) + dx
|
|
|
|
def piece_curves(self, piece):
|
|
"""Les `lines` traits d'un ruban, du bas vers le haut.
|
|
|
|
Chaque trait est prolonge a la verticale jusqu'aux bords haut et bas
|
|
du ruban : sur cette hauteur le fond est masque (hidden_interval), le
|
|
ruban porte donc lui-meme ses traits et s'y soude au fond.
|
|
"""
|
|
top, bottom = piece[3], piece[4]
|
|
curves = []
|
|
for k in range(self.lines):
|
|
low = top + self.height + k * self.stagger
|
|
high = top + k * self.stagger
|
|
points = [(self._x(piece, k, x), low - v) for x, v in self.profile]
|
|
points[0] = (self._x(piece, k), low)
|
|
points[-1] = (self._x(piece, k + self.shift), high)
|
|
if low < bottom:
|
|
points.insert(0, (self._x(piece, k), bottom))
|
|
if high > top:
|
|
points.append((self._x(piece, k + self.shift), top))
|
|
curves.append(points)
|
|
return curves
|
|
|
|
def piece_region(self, piece, inset=0.0):
|
|
"""Polygone couvert par l'ondulation d'un ruban, resserre de `inset`
|
|
(elargi si negatif)."""
|
|
top, bottom = piece[3], piece[4]
|
|
dx = -inset if piece[5] else inset
|
|
# Rive du premier trait (montante), puis rive du dernier (descendante).
|
|
first = [(self._x(piece, 0, x) + dx, top + self.height - v) for x, v in self.profile]
|
|
last = [(self._x(piece, self.lines - 1, x) - dx, bottom - v) for x, v in self.profile]
|
|
top, bottom = top + inset, bottom - inset
|
|
ring = [(first[0][0], bottom)]
|
|
ring += [point for point in first if top < point[1] < bottom]
|
|
ring += [(first[-1][0], top), (last[-1][0], top)]
|
|
ring += [point for point in reversed(last) if top < point[1] < bottom]
|
|
ring.append((last[0][0], bottom))
|
|
return ring
|
|
|
|
def hidden_interval(self, piece, index):
|
|
"""Intervalle (y haut, y bas) ou le trait de fond `index` passe sous le
|
|
ruban, None s'il n'est pas masque."""
|
|
_row, _column, left, top, bottom, mirror = piece
|
|
rel = index - left
|
|
if mirror:
|
|
rel = self.span - rel
|
|
if rel < 0 or rel > self.span:
|
|
return None
|
|
last = self.lines - 1
|
|
# Masque entre le premier trait et le dernier du ruban, rives comprises
|
|
# la ou elles sont verticales (le ruban les trace lui-meme).
|
|
low = top if rel >= self.shift else top + self.height - self._rise(rel * self.spacing)
|
|
high = bottom if rel <= last else bottom - self._rise((rel - last) * self.spacing)
|
|
return (low, high) if high > low else None
|
|
|
|
def pieces_overlap(self):
|
|
"""Vrai si deux rubans peuvent se recouvrir avec ces reglages."""
|
|
return (self.region_height > 2 * self.row_step
|
|
or self.span > 2 * self.columns
|
|
or (self.region_height > self.row_step and self.span > self.columns))
|
|
|
|
def fill(self, rings):
|
|
"""Polylignes du motif decoupees par le contour `rings`."""
|
|
rings = [ring for ring in rings if len(ring) >= 3]
|
|
bounds = rings_bounds(rings)
|
|
if bounds is None:
|
|
return []
|
|
xmin, ymin, xmax, ymax = bounds
|
|
pieces = self.pieces(bounds)
|
|
index = EdgeIndex(rings)
|
|
polylines = []
|
|
|
|
# --- Traits de fond : hachures verticales, moins les parties masquees.
|
|
covering = {}
|
|
for piece in pieces:
|
|
for grid in range(piece[2], piece[2] + self.span + 1):
|
|
covering.setdefault(grid, []).append(piece)
|
|
crossings = {}
|
|
ox = self.origin[0]
|
|
for x1, y1, x2, y2 in index.edges:
|
|
low, high = (x1, x2) if x1 < x2 else (x2, x1)
|
|
for grid in range(int(math.floor((low - ox) / self.spacing)),
|
|
int(math.ceil((high - ox) / self.spacing)) + 1):
|
|
x = self.grid_x(grid)
|
|
if (x1 > x) != (x2 > x):
|
|
crossings.setdefault(grid, []).append(y1 + (x - x1) * (y2 - y1) / (x2 - x1))
|
|
for grid, ys in crossings.items():
|
|
ys.sort()
|
|
inside = [(a, b) for a, b in zip(ys[0::2], ys[1::2]) if b > a]
|
|
hidden = [h for h in (self.hidden_interval(piece, grid)
|
|
for piece in covering.get(grid, ())) if h]
|
|
x = self.grid_x(grid)
|
|
for a, b in subtract_intervals(inside, hidden):
|
|
if b - a > self.tolerance * 1e-3:
|
|
polylines.append([(x, a), (x, b)])
|
|
|
|
# --- Rubans : un ruban passe sous ceux des rangees suivantes.
|
|
overlap = self.pieces_overlap()
|
|
if overlap:
|
|
# Elargi d'un rien : un trait confondu avec la rive du ruban du
|
|
# dessus est masque, ce ruban le trace deja.
|
|
regions = [(piece, EdgeIndex([self.piece_region(piece, -self.tolerance * 1e-2)]))
|
|
for piece in pieces]
|
|
for piece in pieces:
|
|
left, right = sorted((self._x(piece, 0), self._x(piece, self.span)))
|
|
if right < xmin or left > xmax or piece[4] < ymin or piece[3] > ymax:
|
|
continue
|
|
curves = self.piece_curves(piece)
|
|
if overlap:
|
|
for other, region in regions:
|
|
if other[:2] <= piece[:2] or other[3] >= piece[4] or other[4] <= piece[3]:
|
|
continue
|
|
o_left, o_right = sorted((self._x(other, 0), self._x(other, self.span)))
|
|
if o_right <= left or o_left >= right:
|
|
continue
|
|
curves = [part for curve in curves
|
|
for part in region.clip(curve, keep_inside=False)]
|
|
for curve in curves:
|
|
polylines.extend(index.clip(curve))
|
|
|
|
return join_polylines(polylines)
|
|
|
|
|
|
def fill_polylines(rings, spacing, lines=5, shift=6, height=7.0, radius=2.8,
|
|
stagger=1.0, columns=8, rows=7.75, angle=0.0, origin=(0.0, 0.0)):
|
|
"""Motif de rubans ondules decoupe par `rings`.
|
|
|
|
`angle` (degres, sens horaire a l'ecran) tourne le motif autour de `origin`,
|
|
point ou passe un trait de fond et ou est centree une rangee de rubans.
|
|
"""
|
|
pattern = RibbonPattern(spacing, lines, shift, height, radius, stagger,
|
|
columns, rows, origin)
|
|
if not angle:
|
|
return pattern.fill(rings)
|
|
# On calcule dans le repere du motif (traits verticaux), puis on retourne.
|
|
local = [rotate_points(ring, -angle, origin) for ring in rings]
|
|
return [rotate_points(polyline, angle, origin) for polyline in pattern.fill(local)]
|