From bc2821adb11a30244fc4663f4fafb756877d9508 Mon Sep 17 00:00:00 2001 From: Yasutake Yohei <61961825+yasutakeyohei@users.noreply.github.com> Date: Wed, 7 Oct 2026 23:09:40 +0900 Subject: bluebey-studio: public/ の外へ移動し非公開化 MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- public/bluebey-studio/src/trace.js | 410 ------------------------------------- 1 file changed, 410 deletions(-) delete mode 100644 public/bluebey-studio/src/trace.js (limited to 'public/bluebey-studio/src/trace.js') diff --git a/public/bluebey-studio/src/trace.js b/public/bluebey-studio/src/trace.js deleted file mode 100644 index 9b61d6d..0000000 --- a/public/bluebey-studio/src/trace.js +++ /dev/null @@ -1,410 +0,0 @@ -/** - * Zero-dependency marching-squares contour tracer. - * - * Runs unchanged in the browser and in Node: the module has no imports at all, - * never touches the DOM and never writes to the console. - * - * Coordinate system - * ----------------- - * Pixel (x, y) is the unit square whose top-left corner sits at (x, y), so the - * centre of pixel (x, y) is at (x + 0.5, y + 0.5) and y grows downwards - * (row 0 is the top row of the input). - * - * Contours - * -------- - * Every returned contour is a *closed* polyline of sub-pixel points; the first - * point is not repeated at the end. Contours are oriented so that the inside of - * the shape (the region where the sample is at or above the threshold) lies to - * the left of the direction of travel. See `contourArea` for the sign this - * implies. - */ - -const EDGE_TOP = 0; -const EDGE_RIGHT = 1; -const EDGE_BOTTOM = 2; -const EDGE_LEFT = 3; - -/** - * Directed segments emitted by each unambiguous marching-squares case. - * - * The case index is built from the cell corners as - * `tl | tr << 1 | br << 2 | bl << 3`. Entries are flat `[from, to, from, to]` - * pairs of edge ids; the direction keeps the inside region on the left. - */ -const CELL_SEGMENTS = [ - null, // 0 - nothing inside - [EDGE_LEFT, EDGE_TOP, -1, -1], // 1 - top-left only - [EDGE_TOP, EDGE_RIGHT, -1, -1], // 2 - top-right only - [EDGE_LEFT, EDGE_RIGHT, -1, -1], // 3 - top row - [EDGE_RIGHT, EDGE_BOTTOM, -1, -1], // 4 - bottom-right only - null, // 5 - saddle (top-left + bottom-right) - [EDGE_TOP, EDGE_BOTTOM, -1, -1], // 6 - right column - [EDGE_LEFT, EDGE_BOTTOM, -1, -1], // 7 - everything but bottom-left - [EDGE_BOTTOM, EDGE_LEFT, -1, -1], // 8 - bottom-left only - [EDGE_BOTTOM, EDGE_TOP, -1, -1], // 9 - left column - null, // 10 - saddle (top-right + bottom-left) - [EDGE_BOTTOM, EDGE_RIGHT, -1, -1], // 11 - everything but bottom-right - [EDGE_RIGHT, EDGE_LEFT, -1, -1], // 12 - bottom row - [EDGE_RIGHT, EDGE_TOP, -1, -1], // 13 - everything but top-right - [EDGE_TOP, EDGE_LEFT, -1, -1], // 14 - everything but top-left - null, // 15 - everything inside -]; - -// Case 5 (top-left + bottom-right inside). When the centre of the cell is -// inside, the two inside corners are joined through the middle and the two -// outside corners are separated; otherwise the inside corners are separated. -const SADDLE_5_CONNECTED = [EDGE_LEFT, EDGE_BOTTOM, EDGE_RIGHT, EDGE_TOP]; -const SADDLE_5_SPLIT = [EDGE_LEFT, EDGE_TOP, EDGE_RIGHT, EDGE_BOTTOM]; - -// Case 10 (top-right + bottom-left inside): the mirror image of case 5. -const SADDLE_10_CONNECTED = [EDGE_TOP, EDGE_LEFT, EDGE_BOTTOM, EDGE_RIGHT]; -const SADDLE_10_SPLIT = [EDGE_TOP, EDGE_RIGHT, EDGE_BOTTOM, EDGE_LEFT]; - -const DUPLICATE_EPS = 1e-9; - -/** - * Signed area of a closed polyline, via the shoelace formula. The polyline is - * implicitly closed (the last point is joined back to the first), so an open - * ring is fine. - * - * Sign convention: this is the plain shoelace sum `Σ (x_i·y_{i+1} − x_{i+1}·y_i) / 2` - * evaluated in the tracer's y-down pixel coordinates. A ring that runs - * clockwise *as seen on screen* is therefore positive, and a counter-clockwise - * one is negative. Because `traceAlphaContours` keeps the inside on the left, - * the outer boundary of a filled region comes out negative and a hole in it - * comes out positive. - * - * @param {Array<{x: number, y: number}>} points - * @returns {number} signed area in square pixels - */ -export function contourArea(points) { - const n = points.length; - if (!points || n < 3) return 0; - let sum = 0; - for (let i = 0; i < n; i++) { - const a = points[i]; - const b = i + 1 === n ? points[0] : points[i + 1]; - sum += a.x * b.y - b.x * a.y; - } - return sum / 2; -} - -/** - * Build an SVG path `d` attribute with one closed subpath per contour. - * - * `mapPoint(x, y)` returns the `[X, Y]` pair written to the output, which is - * what makes it possible to flip the y axis or apply a scale without touching - * the tracer. Coordinates are rounded to `decimals` places. - * - * @param {Array>} contours - * @param {(x: number, y: number) => [number, number]} mapPoint - * @param {number} [decimals] - * @returns {string} - */ -export function contoursToPathData(contours, mapPoint, decimals = 2) { - const places = Math.max(0, Math.floor(decimals)); - const factor = Math.pow(10, places); - const parts = []; - for (let c = 0; c < contours.length; c++) { - const points = contours[c]; - if (!points || points.length < 2) continue; - for (let i = 0; i < points.length; i++) { - const mapped = mapPoint(points[i].x, points[i].y); - // Rounding before formatting keeps `-0.00` out of the output. - const rx = Math.round(mapped[0] * factor) / factor; - const ry = Math.round(mapped[1] * factor) / factor; - parts.push((i === 0 ? 'M' : 'L') + rx.toFixed(places) + ' ' + ry.toFixed(places)); - } - parts.push('Z'); - } - return parts.join(' '); -} - -// --- closed-ring simplification helpers ------------------------------------ - -/** Drop points that repeat their predecessor (including across the wrap). */ -function removeConsecutiveDuplicates(points) { - const out = []; - for (let i = 0; i < points.length; i++) { - const p = points[i]; - const last = out[out.length - 1]; - if (last && Math.abs(last.x - p.x) <= DUPLICATE_EPS && Math.abs(last.y - p.y) <= DUPLICATE_EPS) { - continue; - } - out.push(p); - } - while (out.length > 1) { - const first = out[0]; - const last = out[out.length - 1]; - if (Math.abs(first.x - last.x) <= DUPLICATE_EPS && Math.abs(first.y - last.y) <= DUPLICATE_EPS) { - out.pop(); - } else { - break; - } - } - return out; -} - -/** Drop points that sit on the straight segment between their two neighbours. */ -function removeCollinear(points) { - let list = points; - let changed = true; - while (changed && list.length > 3) { - changed = false; - const n = list.length; - const out = []; - for (let i = 0; i < n; i++) { - const a = list[i === 0 ? n - 1 : i - 1]; - const b = list[i]; - const c = list[i + 1 === n ? 0 : i + 1]; - const abx = b.x - a.x; - const aby = b.y - a.y; - const bcx = c.x - b.x; - const bcy = c.y - b.y; - const cross = abx * bcy - aby * bcx; - // |cross| / (|ab| * |bc|) is sin(turn angle); a small value means a - // straight-through point, which carries no shape information. - const scale = Math.sqrt((abx * abx + aby * aby) * (bcx * bcx + bcy * bcy)); - const straight = scale <= DUPLICATE_EPS || Math.abs(cross) <= 1e-9 * scale; - if (straight && abx * bcx + aby * bcy >= 0) { - changed = true; - } else { - out.push(b); - } - } - list = out; - } - return list; -} - -/** - * Iterative Douglas–Peucker for an *open* polyline. The two end points are - * always kept; the recursion uses an explicit stack so long contours cannot - * overflow the call stack. - */ -function douglasPeucker(points, tolerance) { - const n = points.length; - if (n <= 2) return points.slice(); - const keep = new Uint8Array(n); - keep[0] = 1; - keep[n - 1] = 1; - const stack = [0, n - 1]; - while (stack.length > 0) { - const i1 = stack.pop(); - const i0 = stack.pop(); - if (i1 <= i0 + 1) continue; - const a = points[i0]; - const b = points[i1]; - const dx = b.x - a.x; - const dy = b.y - a.y; - const len = Math.sqrt(dx * dx + dy * dy); - let maxDistance = -1; - let maxIndex = -1; - if (len <= DUPLICATE_EPS) { - // Degenerate segment: fall back to the distance from the anchor point. - for (let i = i0 + 1; i < i1; i++) { - const px = points[i].x - a.x; - const py = points[i].y - a.y; - const d = Math.sqrt(px * px + py * py); - if (d > maxDistance) { - maxDistance = d; - maxIndex = i; - } - } - } else { - for (let i = i0 + 1; i < i1; i++) { - const p = points[i]; - const d = Math.abs(dy * (p.x - a.x) - dx * (p.y - a.y)) / len; - if (d > maxDistance) { - maxDistance = d; - maxIndex = i; - } - } - } - if (maxDistance > tolerance && maxIndex > i0) { - keep[maxIndex] = 1; - stack.push(i0, maxIndex, maxIndex, i1); - } - } - const out = []; - for (let i = 0; i < n; i++) { - if (keep[i]) out.push(points[i]); - } - return out; -} - -/** - * Simplify a closed ring, wrap-around segment included. - * - * The ring is cut at the point farthest from `points[0]`, which gives two open - * polylines that together cover every segment of the loop exactly once; each - * half is then simplified with Douglas–Peucker and the halves are stitched - * back together (without duplicating the shared anchors). - */ -function simplifyClosedRing(points, tolerance) { - const n = points.length; - if (n <= 3) return points.slice(); - let far = 0; - let farDistance = -1; - const first = points[0]; - for (let i = 1; i < n; i++) { - const dx = points[i].x - first.x; - const dy = points[i].y - first.y; - const d = dx * dx + dy * dy; - if (d > farDistance) { - farDistance = d; - far = i; - } - } - // A ring whose points all coincide carries no shape; leave it to minArea. - if (far <= 0 || farDistance <= DUPLICATE_EPS) return points.slice(); - - const head = douglasPeucker(points.slice(0, far + 1), tolerance); - const tail = douglasPeucker(points.slice(far).concat([first]), tolerance); - - // `head` ends and `tail` starts on the same anchor, and both end on - // `points[0]`; drop the duplicated join so every point appears once. - return head.slice(0, -1).concat(tail.slice(0, -1)); -} - -/** - * Trace the iso-contour of a scalar field at `options.threshold`. - * - * @param {ArrayLike} alpha width*height samples, row-major, row 0 on top - * @param {number} width - * @param {number} height - * @param {object} [options] - * @param {number} [options.threshold=0.5] inside when `alpha/255 >= threshold` - * @param {number} [options.simplifyTolerance=0.35] Douglas-Peucker tolerance, px - * @param {number} [options.minArea=2] drop rings smaller than this, px² - * @returns {Array>} - */ -export function traceAlphaContours(alpha, width, height, options = {}) { - const threshold = options.threshold ?? 0.5; - const tolerance = options.simplifyTolerance ?? 0.35; - const minArea = options.minArea ?? 2; - - const w = Math.floor(width); - const h = Math.floor(height); - if (!alpha || w < 1 || h < 1 || alpha.length < w * h) return []; - if (w < 2 && h < 2) return []; - - // Work on a signed field, padded with a 1px outside border: `s >= 0` is - // inside. The padding guarantees every crossing is strictly interior, so the - // marching always yields closed rings and never touches the array edges. - // The border holds the same value a fully transparent pixel maps to, which - // makes shapes that run off the image close exactly on the image edge. - const pw = w + 2; - const ph = h + 2; - const s = new Float32Array(pw * ph); - s.fill(-threshold); - for (let y = 0; y < h; y++) { - const src = y * w; - const dst = (y + 1) * pw + 1; - for (let x = 0; x < w; x++) s[dst + x] = alpha[src + x] / 255 - threshold; - } - const sample = (x, y) => s[y * pw + x]; - - // Crossing points, keyed by the grid edge they sit on. Both cells sharing an - // edge call these with the same sample pair in the same order (top→bottom, - // left→right), so the coordinates come out bit-identical and can be matched - // by key alone. - const points = new Map(); - function crossing(key, a, b, x0, y0, dx, dy) { - let p = points.get(key); - if (p === undefined) { - const t = a / (a - b); - p = { x: x0 + dx * t, y: y0 + dy * t }; - points.set(key, p); - } - return p; - } - // Horizontal edge of the padded grid at row `py`, spanning columns px..px+1. - const hKey = (px, py) => `h:${px}:${py}`; - const hPoint = (px, py) => crossing(hKey(px, py), sample(px, py), sample(px + 1, py), px - 0.5, py - 0.5, 1, 0); - // Vertical edge of the padded grid at column `px`, spanning rows py..py+1. - const vKey = (px, py) => `v:${px}:${py}`; - const vPoint = (px, py) => crossing(vKey(px, py), sample(px, py), sample(px, py + 1), px - 0.5, py - 0.5, 0, 1); - - const edgeKey = [ - (px, py) => hKey(px, py), // EDGE_TOP - (px, py) => vKey(px + 1, py), // EDGE_RIGHT - (px, py) => hKey(px, py + 1), // EDGE_BOTTOM - (px, py) => vKey(px, py), // EDGE_LEFT - ]; - const edgePoint = [ - (px, py) => hPoint(px, py), // EDGE_TOP - (px, py) => vPoint(px + 1, py), // EDGE_RIGHT - (px, py) => hPoint(px, py + 1), // EDGE_BOTTOM - (px, py) => vPoint(px, py), // EDGE_LEFT - ]; - - // Directed segments: `from` -> `to`, inside region on the left of travel. - const fromKeys = []; - const toKeys = []; - const fromPoints = []; - - for (let py = 0; py < ph - 1; py++) { - for (let px = 0; px < pw - 1; px++) { - const tl = sample(px, py); - const tr = sample(px + 1, py); - const br = sample(px + 1, py + 1); - const bl = sample(px, py + 1); - const inside = (v) => (v >= 0 ? 1 : 0); - const code = inside(tl) | (inside(tr) << 1) | (inside(br) << 2) | (inside(bl) << 3); - let segments = CELL_SEGMENTS[code]; - if (code === 5) { - // With the cell centre inside, the two inside corners join through the - // middle; otherwise each is cut off on its own. - segments = (tl + tr + br + bl) / 4 >= 0 ? SADDLE_5_CONNECTED : SADDLE_5_SPLIT; - } else if (code === 10) { - segments = (tl + tr + br + bl) / 4 >= 0 ? SADDLE_10_CONNECTED : SADDLE_10_SPLIT; - } - if (!segments) continue; - for (let i = 0; i < segments.length; i += 2) { - const a = segments[i]; - const b = segments[i + 1]; - if (a < 0 || b < 0) continue; // padding of the single-segment cases - fromKeys.push(edgeKey[a](px, py)); - fromPoints.push(edgePoint[a](px, py)); - toKeys.push(edgeKey[b](px, py)); - edgePoint[b](px, py); // make sure the shared crossing exists - } - } - } - - // Every crossing has exactly one incoming and one outgoing segment, so the - // segments can be walked into closed rings without any ambiguity. - const outgoing = new Map(); - for (let i = 0; i < fromKeys.length; i++) outgoing.set(fromKeys[i], i); - - const segmentCount = fromKeys.length; - const used = new Uint8Array(segmentCount); - const contours = []; - - for (let start = 0; start < segmentCount; start++) { - if (used[start]) continue; - const ring = []; - let current = start; - for (let guard = 0; guard <= segmentCount; guard++) { - used[current] = 1; - ring.push(fromPoints[current]); - const next = outgoing.get(toKeys[current]); - if (next === undefined || next === start) break; - if (used[next]) break; - current = next; - } - if (ring.length >= 3) contours.push(ring); - } - - const result = []; - for (let i = 0; i < contours.length; i++) { - let ring = removeConsecutiveDuplicates(contours[i]); - ring = simplifyClosedRing(ring, tolerance); - ring = removeCollinear(ring); - if (ring.length < 3) continue; - if (Math.abs(contourArea(ring)) < minArea) continue; - result.push(ring); - } - return result; -} \ No newline at end of file -- cgit v1.3.1