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