AI-native design editor. Open-source Figma alternative.
import type { VectorNetwork, VectorSegment } from '@open-pencil/scene-graph'
import { cubicPoint } from '@open-pencil/scene-graph/geometry'
import type { Vector, Rect } from '@open-pencil/scene-graph/primitives'
export interface CubicPoints {
p0: Vector
cp1: Vector
cp2: Vector
p3: Vector
}
export interface NearestResult {
t: number
x: number
y: number
distance: number
}
export interface NetworkNearestResult extends NearestResult {
segmentIndex: number
}
// ---------------------------------------------------------------------------
// De Casteljau evaluation
// ---------------------------------------------------------------------------
// ---------------------------------------------------------------------------
// Curve splitting (De Casteljau subdivision)
// ---------------------------------------------------------------------------
/** Split a cubic bezier at parameter t, returning two sub-curves. */
export function splitCubicAt(
p0: Vector,
cp1: Vector,
cp2: Vector,
p3: Vector,
t: number
): { left: CubicPoints; right: CubicPoints } {
const mt = 1 - t
// Level 1
const m01x = mt * p0.x + t * cp1.x
const m01y = mt * p0.y + t * cp1.y
const m12x = mt * cp1.x + t * cp2.x
const m12y = mt * cp1.y + t * cp2.y
const m23x = mt * cp2.x + t * p3.x
const m23y = mt * cp2.y + t * p3.y
// Level 2
const m012x = mt * m01x + t * m12x
const m012y = mt * m01y + t * m12y
const m123x = mt * m12x + t * m23x
const m123y = mt * m12y + t * m23y
// Level 3 — the split point
const mx = mt * m012x + t * m123x
const my = mt * m012y + t * m123y
return {
left: {
p0: { x: p0.x, y: p0.y },
cp1: { x: m01x, y: m01y },
cp2: { x: m012x, y: m012y },
p3: { x: mx, y: my }
},
right: {
p0: { x: mx, y: my },
cp1: { x: m123x, y: m123y },
cp2: { x: m23x, y: m23y },
p3: { x: p3.x, y: p3.y }
}
}
}
// ---------------------------------------------------------------------------
// Segment ↔ absolute control points conversion
// ---------------------------------------------------------------------------
/** Convert a VectorSegment's relative tangents to absolute control points. */
export function segmentToAbsolute(network: VectorNetwork, segmentIndex: number): CubicPoints {
const seg = network.segments[segmentIndex]
const v0 = network.vertices[seg.start]
const v1 = network.vertices[seg.end]
return {
p0: { x: v0.x, y: v0.y },
cp1: { x: v0.x + seg.tangentStart.x, y: v0.y + seg.tangentStart.y },
cp2: { x: v1.x + seg.tangentEnd.x, y: v1.y + seg.tangentEnd.y },
p3: { x: v1.x, y: v1.y }
}
}
/** Check if a segment is a straight line (both tangents zero). */
export function isLineSegment(seg: VectorSegment): boolean {
return (
seg.tangentStart.x === 0 &&
seg.tangentStart.y === 0 &&
seg.tangentEnd.x === 0 &&
seg.tangentEnd.y === 0
)
}
// ---------------------------------------------------------------------------
// Accurate bezier bounds via cubic extrema
// ---------------------------------------------------------------------------
/**
* Find parameter values where the cubic derivative is zero (extrema) in one axis.
* Given cubic coefficients for one axis: B(t) = (1-t)^3*p0 + 3(1-t)^2*t*p1 + 3(1-t)*t^2*p2 + t^3*p3
* Derivative: B'(t) = 3[(1-t)^2(p1-p0) + 2(1-t)t(p2-p1) + t^2(p3-p2)]
* Expanding: at^2 + bt + c = 0 where:
* a = -p0 + 3p1 - 3p2 + p3
* b = 2(p0 - 2p1 + p2)
* c = -p0 + p1
*/
export function cubicExtrema(p0: number, p1: number, p2: number, p3: number): number[] {
const a = -p0 + 3 * p1 - 3 * p2 + p3
const b = 2 * (p0 - 2 * p1 + p2)
const c = -p0 + p1
const results: number[] = []
const EPS = 1e-12
if (Math.abs(a) < EPS) {
// Linear: bt + c = 0
if (Math.abs(b) > EPS) {
const t = -c / b
if (t > 0 && t < 1) results.push(t)
}
} else {
const disc = b * b - 4 * a * c
if (disc >= 0) {
const sq = Math.sqrt(disc)
const t1 = (-b + sq) / (2 * a)
const t2 = (-b - sq) / (2 * a)
if (t1 > 0 && t1 < 1) results.push(t1)
if (t2 > 0 && t2 < 1 && Math.abs(t2 - t1) > EPS) results.push(t2)
}
}
return results
}
/** Compute tight axis-aligned bounding box for a VectorNetwork. */
export function computeAccurateBounds(network: VectorNetwork): Rect {
const { vertices, segments } = network
if (vertices.length === 0) return { x: 0, y: 0, width: 0, height: 0 }
let minX = Infinity,
minY = Infinity,
maxX = -Infinity,
maxY = -Infinity
const update = (x: number, y: number) => {
if (x < minX) minX = x
if (y < minY) minY = y
if (x > maxX) maxX = x
if (y > maxY) maxY = y
}
// Include all vertex positions
for (const v of vertices) update(v.x, v.y)
// For each segment, find curve extrema
for (let i = 0; i < segments.length; i++) {
const { p0, cp1, cp2, p3 } = segmentToAbsolute(network, i)
// X extrema
for (const t of cubicExtrema(p0.x, cp1.x, cp2.x, p3.x)) {
const pt = cubicPoint(p0, cp1, cp2, p3, t)
update(pt.x, pt.y)
}
// Y extrema
for (const t of cubicExtrema(p0.y, cp1.y, cp2.y, p3.y)) {
const pt = cubicPoint(p0, cp1, cp2, p3, t)
update(pt.x, pt.y)
}
}
return { x: minX, y: minY, width: maxX - minX, height: maxY - minY }
}
// ---------------------------------------------------------------------------
// Nearest point on cubic bezier
// ---------------------------------------------------------------------------
/**
* Find the nearest point on a cubic bezier to a given point (px, py).
* Uses coarse sampling + iterative refinement.
*/
export function nearestPointOnCubic(
px: number,
py: number,
p0: Vector,
cp1: Vector,
cp2: Vector,
p3: Vector,
coarseSamples: number = 64
): NearestResult {
let bestT = 0
let bestDist = Infinity
// Coarse sampling
for (let i = 0; i <= coarseSamples; i++) {
const t = i / coarseSamples
const pt = cubicPoint(p0, cp1, cp2, p3, t)
const dx = pt.x - px
const dy = pt.y - py
const d = dx * dx + dy * dy
if (d < bestDist) {
bestDist = d
bestT = t
}
}
// Refinement — bisect around best sample, 5 iterations
let lo = Math.max(0, bestT - 1 / coarseSamples)
let hi = Math.min(1, bestT + 1 / coarseSamples)
for (let iter = 0; iter < 5; iter++) {
const step = (hi - lo) / 4
let localBestT = lo
let localBestDist = Infinity
for (let i = 0; i <= 4; i++) {
const t = lo + step * i
const pt = cubicPoint(p0, cp1, cp2, p3, t)
const dx = pt.x - px
const dy = pt.y - py
const d = dx * dx + dy * dy
if (d < localBestDist) {
localBestDist = d
localBestT = t
}
}
bestT = localBestT
bestDist = localBestDist
lo = Math.max(0, bestT - step)
hi = Math.min(1, bestT + step)
}
const pt = cubicPoint(p0, cp1, cp2, p3, bestT)
return { t: bestT, x: pt.x, y: pt.y, distance: Math.sqrt(bestDist) }
}
/** Find nearest point on a straight line segment. */
function nearestPointOnLine(px: number, py: number, p0: Vector, p1: Vector): NearestResult {
const dx = p1.x - p0.x
const dy = p1.y - p0.y
const lenSq = dx * dx + dy * dy
let t: number
if (lenSq < 1e-12) {
t = 0
} else {
t = Math.max(0, Math.min(1, ((px - p0.x) * dx + (py - p0.y) * dy) / lenSq))
}
const x = p0.x + t * dx
const y = p0.y + t * dy
const ddx = x - px
const ddy = y - py
return { t, x, y, distance: Math.hypot(ddx, ddy) }
}
/** Find nearest point across all segments in a VectorNetwork. */
export function nearestPointOnNetwork(
px: number,
py: number,
network: VectorNetwork,
threshold: number
): NetworkNearestResult | null {
let best: NetworkNearestResult | null = null
for (let i = 0; i < network.segments.length; i++) {
const seg = network.segments[i]
let result: NearestResult
if (isLineSegment(seg)) {
const v0 = network.vertices[seg.start]
const v1 = network.vertices[seg.end]
result = nearestPointOnLine(px, py, v0, v1)
} else {
const { p0, cp1, cp2, p3 } = segmentToAbsolute(network, i)
result = nearestPointOnCubic(px, py, p0, cp1, cp2, p3)
}
if (result.distance <= threshold && (!best || result.distance < best.distance)) {
best = { ...result, segmentIndex: i }
}
}
return best
}
// ---------------------------------------------------------------------------
// Split segment within a VectorNetwork
// ---------------------------------------------------------------------------
/**
* Split a segment in a VectorNetwork at parameter t, inserting a new vertex.
* Returns a new VectorNetwork with updated vertices, segments, and regions.
*/