29:null 2a:["$","title",null,{"children":"Nearest Point on an SVG Curve | Lao | Observable"}] 2f:T3d8c,chartWithNearestPoint = { // Create container const container = html`

`; // Controls container const controls = html`

Points:

`; container.appendChild(controls); // Chart dimensions and margins const margin = {top: 20, right: 90, bottom: 40, left: 40}; const containerWidth = width; const chartWidth = containerWidth - margin.left - margin.right; const chartHeight = 500 - margin.top - margin.bottom; // Create SVG const svg = d3.create("svg") .attr("width", chartWidth + margin.left + margin.right) .attr("height", chartHeight + margin.top + margin.bottom) .style("font-family", "Arial, sans-serif") .style("overflow", "visible"); const g = svg.append("g") .attr("transform", `translate(${margin.left},${margin.top})`); container.appendChild(svg.node()); // Create scales const xScale = d3.scaleLinear() .range([0, chartWidth]); const yScale = d3.scaleLinear() .domain([-1.2, 1.2]) .range([chartHeight, 0]); // Data generation const colors = [ "#4e79a7", "#f28e2c", "#e15759", "#76b7b2", "#59a14f", "#edc949", "#af7aa1", "#ff9da7" ]; const curves = [ {name: 'Natural', curve: d3.curveNatural}, {name: 'Basis', curve: d3.curveBasis}, {name: 'Bundle', curve: d3.curveBundle.beta(0.85)}, {name: 'Cardinal', curve: d3.curveCardinal}, {name: 'Catmull-Rom', curve: d3.curveCatmullRom}, {name: 'Monotone', curve: d3.curveMonotoneX}, {name: 'Linear', curve: d3.curveLinear}, {name: 'Step', curve: d3.curveStep} ]; // Exponential slider conversion functions const sliderToPoints = (sliderValue) => { return Math.round(3 * Math.pow(1000/3, sliderValue / 100)); }; const pointsToSlider = (points) => { return Math.round(100 * Math.log(points / 3) / Math.log(1000/3)); }; // Generate random walk data function generateRandomWalk(numPoints) { let data = []; let y = 0; for (let i = 0; i < numPoints; i++) { data.push({x: i, y: y}); y += (Math.random() - 0.5) * 2; } return data; } // Scale data to range [-1, 1] function scaleToRange(data) { const yValues = data.map(d => d.y); const min = Math.min(...yValues); const max = Math.max(...yValues); const range = max - min; if (range === 0) return data; return data.map(d => ({ x: d.x, y: 2 * (d.y - min) / range - 1 })); } // Full dataset (generated once, raw data without scaling) let fullDataset = curves.map((curveInfo, i) => { const rawData = generateRandomWalk(1000); return { name: curveInfo.name, data: rawData, curve: curveInfo.curve, color: colors[i] }; }); // Current display data let currentPointCount = 10; let chartData = []; let pathElements = []; let allSegments = []; // Cache segments to avoid recalculation // Update chart data based on point count function updateChartData() { chartData = fullDataset.map(series => { const filteredData = series.data.slice(0, currentPointCount); const scaledData = scaleToRange(filteredData); return { ...series, data: scaledData }; }); xScale.domain([0, currentPointCount - 1]); renderChart(); } // Create axes (no grid) function createAxes() { g.selectAll("*").remove(); g.append("g") .attr("class", "axis") .attr("transform", `translate(0,${chartHeight})`) .call(d3.axisBottom(xScale)) .selectAll("text") .style("font-size", "12px") .style("color", "#666"); g.append("g") .attr("class", "axis") .call(d3.axisLeft(yScale)) .selectAll("text") .style("font-size", "12px") .style("color", "#666"); g.selectAll(".axis path, .axis line") .style("fill", "none") .style("stroke", "#ddd") .style("shape-rendering", "crispEdges"); } // Render chart paths function renderChart() { createAxes(); const line = d3.line() .x(d => xScale(d.x)) .y(d => yScale(d.y)); pathElements = []; chartData.forEach((s, i) => { const pathElement = g.append("path") .datum(s.data) .attr("class", "chart-path") .attr("d", line.curve(s.curve)) .style("fill", "none") .style("stroke", s.color) .style("stroke-width", "2.5px"); pathElements.push({ path: pathElement, series: s, index: i }); }); // Add endpoint labels const endpoints = chartData.map((series, i) => { const lastPoint = series.data[series.data.length - 1]; return { name: series.name, y: lastPoint.y, color: series.color, x: xScale(lastPoint.x), dy: yScale(lastPoint.y) }; }); const optimizedLabels = optimizeLabels(endpoints, { space: 15, minY: 0, maxY: chartHeight, yScale: yScale }); // Draw labels const labelGroup = g.append("g").attr("class", "endpoint-labels"); optimizedLabels.forEach(label => { labelGroup.append("text") .attr("x", chartWidth + 10) .attr("y", label.dy) .attr("dy", "0.35em") .style("font-size", "12px") .style("fill", label.color) .style("font-weight", "bold") .text(label.name); }); // Add visualization elements g.append("circle") .attr("class", "range-circle") .style("fill", "none") .style("stroke-width", "0.5px") .style("display", "none"); g.append("circle") .attr("class", "nearest-point") .attr("r", 5) .style("stroke", "white") .style("stroke-width", "2px") .style("display", "none"); // Only update segments when paths change, not just point count updateSegments(); } // Parse SVG path to actual curve segments (not line segments) function updateSegments() { allSegments = []; pathElements.forEach((pathData, index) => { const pathString = pathData.path.attr("d"); const segments = parsePathToSegments(pathString, index); allSegments = allSegments.concat(segments); }); } // Parse SVG path to curve segments - keep actual curve types const parsePathToSegments = (pathString, seriesIndex) => { const segments = []; if (!pathString || typeof pathString !== 'string') return segments; const commands = pathString.match(/[MmLlHhVvCcSsQqTtAaZz][^MmLlHhVvCcSsQqTtAaZz]*/g); let currentPoint = {x: 0, y: 0}; if (!commands) return segments; commands.forEach(command => { const type = command[0]; const coords = command.slice(1).trim().split(/[\s,]+/).map(Number).filter(n => !isNaN(n)); try { switch (type.toUpperCase()) { case 'M': if (coords.length >= 2) { currentPoint = {x: coords[0], y: coords[1]}; } break; case 'L': if (coords.length >= 2) { const endPoint = {x: coords[0], y: coords[1]}; segments.push({ type: 'L', start: {...currentPoint}, end: endPoint, seriesIndex: seriesIndex, color: chartData[seriesIndex]?.color || '#000000' }); currentPoint = endPoint; } break; case 'C': if (coords.length >= 6) { const control1 = {x: coords[0], y: coords[1]}; const control2 = {x: coords[2], y: coords[3]}; const endC = {x: coords[4], y: coords[5]}; segments.push({ type: 'C', start: {...currentPoint}, control1: control1, control2: control2, end: endC, seriesIndex: seriesIndex, color: chartData[seriesIndex]?.color || '#000000' }); currentPoint = endC; } break; case 'Q': if (coords.length >= 4) { const control = {x: coords[0], y: coords[1]}; const endQ = {x: coords[2], y: coords[3]}; segments.push({ type: 'Q', start: {...currentPoint}, control1: control, end: endQ, seriesIndex: seriesIndex, color: chartData[seriesIndex]?.color || '#000000' }); currentPoint = endQ; } break; case 'H': if (coords.length >= 1) { const endPoint = {x: coords[0], y: currentPoint.y}; segments.push({ type: 'H', start: {...currentPoint}, end: endPoint, seriesIndex: seriesIndex, color: chartData[seriesIndex]?.color || '#000000' }); currentPoint = endPoint; } break; case 'V': if (coords.length >= 1) { const endPoint = {x: currentPoint.x, y: coords[0]}; segments.push({ type: 'V', start: {...currentPoint}, end: endPoint, seriesIndex: seriesIndex, color: chartData[seriesIndex]?.color || '#000000' }); currentPoint = endPoint; } break; } } catch (e) { console.warn('Error parsing path command:', command, e); } }); return segments; }; // Validate segment data const validateSegment = (segment) => { if (!segment || typeof segment !== 'object') return false; if (!segment.start || typeof segment.start.x !== 'number' || typeof segment.start.y !== 'number') return false; if (!segment.end || typeof segment.end.x !== 'number' || typeof segment.end.y !== 'number') return false; switch (segment.type) { case 'C': return segment.control1 && typeof segment.control1.x === 'number' && typeof segment.control1.y === 'number' && segment.control2 && typeof segment.control2.x === 'number' && typeof segment.control2.y === 'number'; case 'Q': return segment.control1 && typeof segment.control1.x === 'number' && typeof segment.control1.y === 'number'; case 'L': case 'H': case 'V': return true; default: return false; } }; // Distance functions const euclideanDistance = (x1, y1, x2, y2) => { return Math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2); }; // Use the proper nearestPoint functions for actual curve segments const findNearestPoint = (mouseX, mouseY) => { if (allSegments.length === 0) return null; let nearestResult = null; let globalMinDistance = Infinity; // Check all curve segments using the proper nearestPoint functions allSegments.forEach(segment => { if (!validateSegment(segment)) return; try { // Use the provided nearestPoint function const result = nearestPoint.find({x: mouseX, y: mouseY}, segment.type, segment); if (result && result.point && typeof result.distance === 'number' && result.distance < globalMinDistance) { globalMinDistance = result.distance; nearestResult = { point: result.point, distance: result.distance, color: segment.color, seriesIndex: segment.seriesIndex }; } } catch (e) { // Fallback to endpoint distance if nearestPoint fails const startDist = euclideanDistance(mouseX, mouseY, segment.start.x, segment.start.y); const endDist = euclideanDistance(mouseX, mouseY, segment.end.x, segment.end.y); if (startDist < globalMinDistance) { globalMinDistance = startDist; nearestResult = { point: segment.start, distance: startDist, color: segment.color, seriesIndex: segment.seriesIndex }; } if (endDist < globalMinDistance) { globalMinDistance = endDist; nearestResult = { point: segment.end, distance: endDist, color: segment.color, seriesIndex: segment.seriesIndex }; } } }); return nearestResult; }; // Mouse interaction svg.on("mousemove", function(event) { const [x, y] = d3.pointer(event, g.node()); try { const nearest = findNearestPoint(x, y); if (nearest && nearest.point && typeof nearest.distance === 'number') { g.select(".nearest-point") .attr("cx", nearest.point.x) .attr("cy", nearest.point.y) .style("fill", nearest.color) .style("display", "block"); g.select(".range-circle") .attr("cx", x) .attr("cy", y) .attr("r", nearest.distance) .style("stroke", nearest.color) .style("display", "block"); } else { g.select(".nearest-point").style("display", "none"); g.select(".range-circle").style("display", "none"); } } catch (e) { console.warn('Error in mouse interaction:', e); g.select(".nearest-point").style("display", "none"); g.select(".range-circle").style("display", "none"); } }); svg.on("mouseleave", function() { g.select(".nearest-point").style("display", "none"); g.select(".range-circle").style("display", "none"); }); // Event handlers const rerollBtn = container.querySelector("#rerollBtn"); const pointsSlider = container.querySelector("#pointsSlider"); const pointsInput = container.querySelector("#pointsInput"); function regenerateData() { fullDataset = curves.map((curveInfo, i) => { const rawData = generateRandomWalk(1000); return { name: curveInfo.name, data: rawData, curve: curveInfo.curve, color: colors[i] }; }); updateChartData(); } function updatePointCount(points, fromSlider = false) { currentPointCount = Math.max(3, Math.min(1000, parseInt(points))); if (fromSlider) { currentPointCount = sliderToPoints(points); pointsInput.value = currentPointCount; } else { pointsSlider.value = pointsToSlider(currentPointCount); pointsInput.value = currentPointCount; } updateChartData(); } rerollBtn.addEventListener('click', regenerateData); pointsSlider.addEventListener('input', (e) => { updatePointCount(parseInt(e.target.value), true); }); pointsInput.addEventListener('input', (e) => { const value = Math.max(3, Math.min(1000, parseInt(e.target.value) || 3)); updatePointCount(value, false); }); pointsSlider.value = pointsToSlider(currentPointCount); pointsInput.value = currentPointCount; updateChartData(); return container; }30:T4a0b,// Main visualization cell { // Create the main container const container = html`

Curve Type:

`; // Initialize variables const svg = d3.select(container).select('#bezier-chart'); const width = config.width; const height = config.height; const radius = config.radius; let currentCurveType = 'C'; // Store previous control points for intelligent transitions let previousControlPoints = {}; // Store previous arc configuration separately let previousArcConfig = null; // Initialize points with the default curve type let points = {...config.pointConfigs[currentCurveType]}; // Add event listener for curve type changes d3.select(container).select('#curve-type').on('change', function() { const oldCurveType = currentCurveType; const oldPoints = {...points}; currentCurveType = this.value; points = {...config.pointConfigs[currentCurveType]}; // Preserve shared points between curve types preserveSharedPoints(oldCurveType, currentCurveType, oldPoints); recreatePoints(); updateCurve(); updateExtremePoints(); updateBoundingBox(); updateClosestPoint(); // Always bring closest point to front after updates closestPoint.raise(); distanceCircle.raise(); }); // Function to preserve shared points when switching curve types function preserveSharedPoints(oldType, newType, oldPoints) { // Always preserve independent point if (oldPoints.independent && points.independent) { points.independent.x = oldPoints.independent.x; points.independent.y = oldPoints.independent.y; } // Save arc configuration when leaving arc mode if (oldType === 'A') { previousArcConfig = { center: { x: oldPoints.center.x, y: oldPoints.center.y }, radiusX: { x: oldPoints.radiusX.x, y: oldPoints.radiusX.y }, radiusY: { x: oldPoints.radiusY.x, y: oldPoints.radiusY.y }, arcStart: { x: oldPoints.arcStart.x, y: oldPoints.arcStart.y }, arcEnd: { x: oldPoints.arcEnd.x, y: oldPoints.arcEnd.y }, _angle: oldPoints._angle, _startAngle: oldPoints._startAngle, _endAngle: oldPoints._endAngle }; return; } // When switching to arc, restore previous arc config if available if (newType === 'A') { arcHelpers.initializeArc(points, previousArcConfig); return; } // Always preserve start point for non-arc curves if (oldPoints.start && points.start) { points.start.x = oldPoints.start.x; points.start.y = oldPoints.start.y; } // Always preserve end point for non-arc curves if (oldPoints.end && points.end) { points.end.x = oldPoints.end.x; points.end.y = oldPoints.end.y; } // Handle specific transitions with intelligent control point management if (oldType === 'C' && newType === 'Q') { if (oldPoints.control1 && points.control1) { points.control1.x = oldPoints.control1.x; points.control1.y = oldPoints.control1.y; } if (oldPoints.control2) { previousControlPoints.control2 = { x: oldPoints.control2.x, y: oldPoints.control2.y }; } } else if (oldType === 'Q' && newType === 'C') { if (oldPoints.control1 && points.control1) { points.control1.x = oldPoints.control1.x; points.control1.y = oldPoints.control1.y; } if (previousControlPoints.control2 && points.control2) { points.control2.x = previousControlPoints.control2.x; points.control2.y = previousControlPoints.control2.y; } } else if ((oldType === 'C' || oldType === 'Q') && (newType === 'L' || newType === 'H' || newType === 'V')) { if (oldType === 'C' && oldPoints.control1 && oldPoints.control2) { previousControlPoints.control1 = { x: oldPoints.control1.x, y: oldPoints.control1.y }; previousControlPoints.control2 = { x: oldPoints.control2.x, y: oldPoints.control2.y }; } else if (oldType === 'Q' && oldPoints.control1) { previousControlPoints.control1 = { x: oldPoints.control1.x, y: oldPoints.control1.y }; } } else if ((oldType === 'L' || oldType === 'H' || oldType === 'V') && newType === 'C') { if (previousControlPoints.control1 && points.control1) { points.control1.x = previousControlPoints.control1.x; points.control1.y = previousControlPoints.control1.y; } if (previousControlPoints.control2 && points.control2) { points.control2.x = previousControlPoints.control2.x; points.control2.y = previousControlPoints.control2.y; } } else if ((oldType === 'L' || oldType === 'H' || oldType === 'V') && newType === 'Q') { if (previousControlPoints.control1 && points.control1) { points.control1.x = previousControlPoints.control1.x; points.control1.y = previousControlPoints.control1.y; } } } // Create the bounding box (behind all other elements) const boundingBox = svg.append('rect') .style('fill', 'none') .style('stroke', 'steelblue') .style('stroke-width', '0.5') .style('stroke-dasharray', '5,5'); // Create the curve path const curvePath = svg.append('path') .style('fill', 'none') .style('stroke', 'steelblue') .style('stroke-width', '2'); // Create control lines const controlLine1 = svg.append('line') .style('stroke', 'steelblue') .style('stroke-width', '1'); const controlLine2 = svg.append('line') .style('stroke', 'steelblue') .style('stroke-width', '1'); // Create circles for all points let circles = svg.selectAll('.point') .data(Object.values(points).filter(d => typeof d === 'object' && d.type)) .enter() .append('circle') .attr('class', 'point') .attr('r', radius) .attr('cx', d => d.x) .attr('cy', d => d.y) .style('stroke', '#fff') .style('stroke-width', '2') .style('cursor', 'move') .style('fill', d => { if (d.type === 'control' || d.type === 'end') return 'steelblue'; if (d.type === 'independent') return '#2ecc71'; if (d.type === 'arc-center' || d.type === 'arc-radius' || d.type === 'arc-endpoint') return 'steelblue'; return 'steelblue'; }); // Initialize arc if starting with arc type if (currentCurveType === 'A') { arcHelpers.initializeArc(points, null); circles.attr('cx', d => d.x).attr('cy', d => d.y); } // Add drag behavior const drag = d3.drag() .on('drag', function(event, d) { if (currentCurveType === 'A') { handleArcDrag(event, d); } else { // Constrain points within canvas bounds d.x = Math.max(radius, Math.min(width - radius, event.x)); d.y = Math.max(radius, Math.min(height - radius, event.y)); // Update circle position d3.select(this) .attr('cx', d.x) .attr('cy', d.y); } // Update the curve and lines updateCurve(); updateExtremePoints(); updateBoundingBox(); updateClosestPoint(); // Keep closest point on top while dragging closestPoint.raise(); distanceCircle.raise(); }); // Special drag handler for arc mode function handleArcDrag(event, d) { if (d.type === 'arc-center') { // Move center and all dependent points const dx = event.x - d.x; const dy = event.y - d.y; d.x = Math.max(radius, Math.min(width - radius, event.x)); d.y = Math.max(radius, Math.min(height - radius, event.y)); // Move radius handles with center points.radiusX.x += dx; points.radiusX.y += dy; points.radiusY.x += dx; points.radiusY.y += dy; // Move endpoints with center points.arcStart.x += dx; points.arcStart.y += dy; points.arcEnd.x += dx; points.arcEnd.y += dy; } else if (d.type === 'arc-radius') { const center = points.center; const dx = event.x - center.x; const dy = event.y - center.y; if (d.radiusType === 'x') { // Calculate new angle and radius for X handle const newAngle = Math.atan2(dy, dx); points._angle = newAngle; // Update radius based on distance const distance = Math.sqrt(dx * dx + dy * dy); d.x = center.x + distance * Math.cos(newAngle); d.y = center.y + distance * Math.sin(newAngle); // Update Y handle to be 90 degrees from X handle const yAngle = newAngle + Math.PI / 2; const yDistance = Math.sqrt( Math.pow(points.radiusY.x - center.x, 2) + Math.pow(points.radiusY.y - center.y, 2) ); points.radiusY.x = center.x + yDistance * Math.cos(yAngle); points.radiusY.y = center.y + yDistance * Math.sin(yAngle); } else if (d.radiusType === 'y') { // Calculate angle for Y handle const yAngle = Math.atan2(dy, dx); // Calculate what X angle should be (90 degrees back) const xAngle = yAngle - Math.PI / 2; points._angle = xAngle; // Update Y radius based on distance const distance = Math.sqrt(dx * dx + dy * dy); d.x = center.x + distance * Math.cos(yAngle); d.y = center.y + distance * Math.sin(yAngle); // Update X handle to be 90 degrees from Y handle const xDistance = Math.sqrt( Math.pow(points.radiusX.x - center.x, 2) + Math.pow(points.radiusX.y - center.y, 2) ); points.radiusX.x = center.x + xDistance * Math.cos(xAngle); points.radiusX.y = center.y + xDistance * Math.sin(xAngle); } // Update endpoints based on their stored angles arcHelpers.updateEndpointPositions(points); } else if (d.type === 'arc-endpoint') { // Moving endpoints changes their angle on the ellipse const center = points.center; const rx = Math.sqrt( Math.pow(points.radiusX.x - center.x, 2) + Math.pow(points.radiusX.y - center.y, 2) ); const ry = Math.sqrt( Math.pow(points.radiusY.x - center.x, 2) + Math.pow(points.radiusY.y - center.y, 2) ); // Project the dragged point onto the ellipse const rotation = points._angle; // Transform to ellipse coordinate system const dx = event.x - center.x; const dy = event.y - center.y; const x = dx * Math.cos(-rotation) - dy * Math.sin(-rotation); const y = dx * Math.sin(-rotation) + dy * Math.cos(-rotation); // Calculate angle for this point let angle = Math.atan2(y / ry, x / rx); // Project onto ellipse at this angle const ex = rx * Math.cos(angle); const ey = ry * Math.sin(angle); // Transform back to world coordinates d.x = center.x + ex * Math.cos(rotation) - ey * Math.sin(rotation); d.y = center.y + ex * Math.sin(rotation) + ey * Math.cos(rotation); // Update the stored angle for this endpoint if (d === points.arcStart) { points._startAngle = angle; } else if (d === points.arcEnd) { points._endAngle = angle; } } else if (d.type === 'independent') { // Normal dragging for independent point d.x = Math.max(radius, Math.min(width - radius, event.x)); d.y = Math.max(radius, Math.min(height - radius, event.y)); d3.select(this) .attr('cx', d.x) .attr('cy', d.y); } // Update all circle positions svg.selectAll('.point') .attr('cx', d => d.x) .attr('cy', d => d.y); } circles.call(drag); function recreatePoints() { // Remove existing circles svg.selectAll('.point').remove(); // Create new circles circles = svg.selectAll('.point') .data(Object.values(points).filter(d => typeof d === 'object' && d.type)) .enter() .append('circle') .attr('class', 'point') .attr('r', radius) .attr('cx', d => d.x) .attr('cy', d => d.y) .style('stroke', '#fff') .style('stroke-width', '2') .style('cursor', 'move') .style('fill', d => { if (d.type === 'control' || d.type === 'end') return 'steelblue'; if (d.type === 'independent') return '#2ecc71'; if (d.type === 'arc-center' || d.type === 'arc-radius' || d.type === 'arc-endpoint') return 'steelblue'; return 'steelblue'; }); circles.call(drag); } // Create extreme points group const extremePointsGroup = svg.append('g'); // Create closest point and distance circle const closestPoint = svg.append('circle') .attr('r', 5) .style('fill', '#2ecc71') .style('stroke', 'white') .style('stroke-width', '2') .style('pointer-events', 'none'); const distanceCircle = svg.append('circle') .style('fill', 'none') .style('stroke', '#2ecc71') .style('stroke-width', '0.5') .style('pointer-events', 'none'); function updateClosestPoint() { const target = points.independent; const closest = nearestPoint.find(target, currentCurveType, points); closestPoint .style('display', 'block') .attr('cx', closest.point.x) .attr('cy', closest.point.y); distanceCircle .style('display', 'block') .attr('cx', target.x) .attr('cy', target.y) .attr('r', closest.distance); } function updateExtremePoints() { const extremePts = extremePoints.find(currentCurveType, points); const extremeCircles = extremePointsGroup.selectAll('.extreme-point') .data(extremePts); extremeCircles.enter() .append('circle') .attr('class', 'extreme-point') .attr('r', 5) .style('fill', 'steelblue') .style('stroke', 'white') .style('stroke-width', '2') .style('pointer-events', 'none') .merge(extremeCircles) .attr('cx', d => d.x) .attr('cy', d => d.y); extremeCircles.exit().remove(); } function updateBoundingBox() { // Hide bounding box for vertical and horizontal if (currentCurveType === 'V' || currentCurveType === 'H') { boundingBox.style('display', 'none'); return; } // Show bounding box for other curve types boundingBox.style('display', 'block'); const extremePts = extremePoints.find(currentCurveType, points); const allPoints = [...extremePts]; // Add endpoints if (currentCurveType === 'A') { allPoints.push( { x: points.arcStart.x, y: points.arcStart.y }, { x: points.arcEnd.x, y: points.arcEnd.y } ); } else if (points.start && points.end) { allPoints.push( { x: points.start.x, y: points.start.y }, { x: points.end.x, y: points.end.y } ); } if (allPoints.length === 0) return; const minX = Math.min(...allPoints.map(p => p.x)); const maxX = Math.max(...allPoints.map(p => p.x)); const minY = Math.min(...allPoints.map(p => p.y)); const maxY = Math.max(...allPoints.map(p => p.y)); boundingBox .attr('x', minX) .attr('y', minY) .attr('width', maxX - minX) .attr('height', maxY - minY); } function updateCurve() { let pathData = ''; controlLine1.style('display', 'none'); controlLine2.style('display', 'none'); switch(currentCurveType) { case 'C': pathData = `M ${points.start.x} ${points.start.y} C ${points.control1.x} ${points.control1.y}, ${points.control2.x} ${points.control2.y}, ${points.end.x} ${points.end.y}`; controlLine1.style('display', 'block') .attr('x1', points.start.x) .attr('y1', points.start.y) .attr('x2', points.control1.x) .attr('y2', points.control1.y) .style('stroke', 'steelblue'); controlLine2.style('display', 'block') .attr('x1', points.end.x) .attr('y1', points.end.y) .attr('x2', points.control2.x) .attr('y2', points.control2.y) .style('stroke', 'steelblue'); break; case 'Q': pathData = `M ${points.start.x} ${points.start.y} Q ${points.control1.x} ${points.control1.y}, ${points.end.x} ${points.end.y}`; controlLine1.style('display', 'block') .attr('x1', points.start.x) .attr('y1', points.start.y) .attr('x2', points.control1.x) .attr('y2', points.control1.y) .style('stroke', 'steelblue'); controlLine2.style('display', 'block') .attr('x1', points.end.x) .attr('y1', points.end.y) .attr('x2', points.control1.x) .attr('y2', points.control1.y) .style('stroke', 'steelblue'); break; case 'L': pathData = `M ${points.start.x} ${points.start.y} L ${points.end.x} ${points.end.y}`; break; case 'H': pathData = `M ${points.start.x} ${points.start.y} H ${points.end.x}`; break; case 'V': pathData = `M ${points.start.x} ${points.start.y} V ${points.end.y}`; break; case 'A': pathData = arcHelpers.getPathData(points); // Show lines from center to radius handles controlLine1.style('display', 'block') .attr('x1', points.center.x) .attr('y1', points.center.y) .attr('x2', points.radiusX.x) .attr('y2', points.radiusX.y) .style('stroke', 'steelblue') .style('stroke-dasharray', '3,3'); controlLine2.style('display', 'block') .attr('x1', points.center.x) .attr('y1', points.center.y) .attr('x2', points.radiusY.x) .attr('y2', points.radiusY.y) .style('stroke', 'steelblue') .style('stroke-dasharray', '3,3'); break; } curvePath.attr('d', pathData); } // Initial setup updateCurve(); updateExtremePoints(); updateBoundingBox(); updateClosestPoint(); return container; }31:T6e5,// Configuration and initial point setups config = ({ width: 600, height: 400, radius: 10, // Point configurations for different curve types pointConfigs: { 'C': { start: { x: 100, y: 200, type: 'end' }, control1: { x: 200, y: 100, type: 'control' }, control2: { x: 400, y: 300, type: 'control' }, end: { x: 500, y: 200, type: 'end' }, independent: { x: 300, y: 50, type: 'independent' } }, 'Q': { start: { x: 100, y: 200, type: 'end' }, control1: { x: 300, y: 100, type: 'control' }, end: { x: 500, y: 200, type: 'end' }, independent: { x: 300, y: 50, type: 'independent' } }, 'L': { start: { x: 150, y: 200, type: 'end' }, end: { x: 450, y: 200, type: 'end' }, independent: { x: 300, y: 50, type: 'independent' } }, 'H': { start: { x: 150, y: 200, type: 'end' }, end: { x: 450, y: 200, type: 'end' }, independent: { x: 300, y: 50, type: 'independent' } }, 'V': { start: { x: 300, y: 100, type: 'end' }, end: { x: 300, y: 300, type: 'end' }, independent: { x: 200, y: 150, type: 'independent' } }, 'A': { center: { x: 300, y: 200, type: 'arc-center' }, radiusX: { x: 380, y: 200, type: 'arc-radius', radiusType: 'x' }, radiusY: { x: 300, y: 140, type: 'arc-radius', radiusType: 'y' }, arcStart: { x: 380, y: 200, type: 'arc-endpoint' }, arcEnd: { x: 220, y: 140, type: 'arc-endpoint' }, independent: { x: 400, y: 100, type: 'independent' }, // Store internal parameters _angle: 0, // Rotation angle of the ellipse _startAngle: 0, // Angle to start point on ellipse _endAngle: Math.PI * 0.75 // Angle to end point on ellipse } } })32:Tbdb,// Functions to calculate points on different curve types curvePoints = { // Cubic Bezier point at parameter t const cubic = (t, points) => { const { start, control1, control2, end } = points; const mt = 1 - t; const mt2 = mt * mt; const mt3 = mt2 * mt; const t2 = t * t; const t3 = t2 * t; return { x: mt3 * start.x + 3 * mt2 * t * control1.x + 3 * mt * t2 * control2.x + t3 * end.x, y: mt3 * start.y + 3 * mt2 * t * control1.y + 3 * mt * t2 * control2.y + t3 * end.y }; }; // Quadratic Bezier point at parameter t const quadratic = (t, points) => { const { start, control1, end } = points; const mt = 1 - t; const mt2 = mt * mt; const t2 = t * t; return { x: mt2 * start.x + 2 * mt * t * control1.x + t2 * end.x, y: mt2 * start.y + 2 * mt * t * control1.y + t2 * end.y }; }; // Linear interpolation point at parameter t const linear = (t, points) => { const { start, end } = points; return { x: start.x + t * (end.x - start.x), y: start.y + t * (end.y - start.y) }; }; // Horizontal line point at parameter t const horizontal = (t, points) => { const { start, end } = points; return { x: start.x + t * (end.x - start.x), y: start.y }; }; // Vertical line point at parameter t const vertical = (t, points) => { const { start, end } = points; return { x: start.x, y: start.y + t * (end.y - start.y) }; }; // Arc/ellipse point at parameter t const arc = (t, points) => { const center = points.center; const rx = Math.sqrt( Math.pow(points.radiusX.x - center.x, 2) + Math.pow(points.radiusX.y - center.y, 2) ); const ry = Math.sqrt( Math.pow(points.radiusY.x - center.x, 2) + Math.pow(points.radiusY.y - center.y, 2) ); const rotation = points._angle; // Interpolate angle let startAngle = points._startAngle; let endAngle = points._endAngle; // Handle angle wrapping while (endAngle <= startAngle) endAngle += 2 * Math.PI; const angle = startAngle + t * (endAngle - startAngle); // Calculate point on ellipse const ex = rx * Math.cos(angle); const ey = ry * Math.sin(angle); // Rotate and translate return { x: center.x + ex * Math.cos(rotation) - ey * Math.sin(rotation), y: center.y + ex * Math.sin(rotation) + ey * Math.cos(rotation) }; }; // Generic function to get point based on curve type const getPoint = (t, curveType, points) => { switch(curveType) { case 'C': return cubic(t, points); case 'Q': return quadratic(t, points); case 'L': return linear(t, points); case 'H': return horizontal(t, points); case 'V': return vertical(t, points); case 'A': return arc(t, points); default: return { x: 0, y: 0 }; } }; return { cubic, quadratic, linear, horizontal, vertical, arc, getPoint }; }33:T1473,// First and second derivative functions for curves derivatives = { // First derivatives const firstCubic = (t, points) => { const { start, control1, control2, end } = points; const mt = 1 - t; const mt2 = mt * mt; const t2 = t * t; return { x: 3 * mt2 * (control1.x - start.x) + 6 * mt * t * (control2.x - control1.x) + 3 * t2 * (end.x - control2.x), y: 3 * mt2 * (control1.y - start.y) + 6 * mt * t * (control2.y - control1.y) + 3 * t2 * (end.y - control2.y) }; }; const firstQuadratic = (t, points) => { const { start, control1, end } = points; const mt = 1 - t; return { x: 2 * mt * (control1.x - start.x) + 2 * t * (end.x - control1.x), y: 2 * mt * (control1.y - start.y) + 2 * t * (end.y - control1.y) }; }; const firstLinear = (t, points) => { const { start, end } = points; return { x: end.x - start.x, y: end.y - start.y }; }; const firstHorizontal = (t, points) => { const { start, end } = points; return { x: end.x - start.x, y: 0 }; }; const firstVertical = (t, points) => { const { start, end } = points; return { x: 0, y: end.y - start.y }; }; const firstArc = (t, points) => { const center = points.center; const rx = Math.sqrt( Math.pow(points.radiusX.x - center.x, 2) + Math.pow(points.radiusX.y - center.y, 2) ); const ry = Math.sqrt( Math.pow(points.radiusY.x - center.x, 2) + Math.pow(points.radiusY.y - center.y, 2) ); const rotation = points._angle; let startAngle = points._startAngle; let endAngle = points._endAngle; while (endAngle <= startAngle) endAngle += 2 * Math.PI; const angle = startAngle + t * (endAngle - startAngle); const dAngle = endAngle - startAngle; // Derivative of parametric ellipse const dx_dt = -rx * Math.sin(angle) * dAngle; const dy_dt = ry * Math.cos(angle) * dAngle; // Apply rotation return { x: dx_dt * Math.cos(rotation) - dy_dt * Math.sin(rotation), y: dx_dt * Math.sin(rotation) + dy_dt * Math.cos(rotation) }; }; // Second derivatives const secondCubic = (t, points) => { const { start, control1, control2, end } = points; const mt = 1 - t; return { x: 6 * mt * (control2.x - 2 * control1.x + start.x) + 6 * t * (end.x - 2 * control2.x + control1.x), y: 6 * mt * (control2.y - 2 * control1.y + start.y) + 6 * t * (end.y - 2 * control2.y + control1.y) }; }; const secondQuadratic = (t, points) => { const { start, control1, end } = points; return { x: 2 * (end.x - 2 * control1.x + start.x), y: 2 * (end.y - 2 * control1.y + start.y) }; }; const secondLinear = (t, points) => ({ x: 0, y: 0 }); const secondHorizontal = (t, points) => ({ x: 0, y: 0 }); const secondVertical = (t, points) => ({ x: 0, y: 0 }); const secondArc = (t, points) => { const center = points.center; const rx = Math.sqrt( Math.pow(points.radiusX.x - center.x, 2) + Math.pow(points.radiusX.y - center.y, 2) ); const ry = Math.sqrt( Math.pow(points.radiusY.x - center.x, 2) + Math.pow(points.radiusY.y - center.y, 2) ); const rotation = points._angle; let startAngle = points._startAngle; let endAngle = points._endAngle; while (endAngle <= startAngle) endAngle += 2 * Math.PI; const angle = startAngle + t * (endAngle - startAngle); const dAngle = endAngle - startAngle; // Second derivative of parametric ellipse const d2x_dt2 = -rx * Math.cos(angle) * dAngle * dAngle; const d2y_dt2 = -ry * Math.sin(angle) * dAngle * dAngle; // Apply rotation return { x: d2x_dt2 * Math.cos(rotation) - d2y_dt2 * Math.sin(rotation), y: d2x_dt2 * Math.sin(rotation) + d2y_dt2 * Math.cos(rotation) }; }; // Generic getters const getFirst = (t, curveType, points) => { switch(curveType) { case 'C': return firstCubic(t, points); case 'Q': return firstQuadratic(t, points); case 'L': return firstLinear(t, points); case 'H': return firstHorizontal(t, points); case 'V': return firstVertical(t, points); case 'A': return firstArc(t, points); default: return { x: 0, y: 0 }; } }; const getSecond = (t, curveType, points) => { switch(curveType) { case 'C': return secondCubic(t, points); case 'Q': return secondQuadratic(t, points); case 'L': return secondLinear(t, points); case 'H': return secondHorizontal(t, points); case 'V': return secondVertical(t, points); case 'A': return secondArc(t, points); default: return { x: 0, y: 0 }; } }; return { first: { cubic: firstCubic, quadratic: firstQuadratic, linear: firstLinear, horizontal: firstHorizontal, vertical: firstVertical, arc: firstArc }, second: { cubic: secondCubic, quadratic: secondQuadratic, linear: secondLinear, horizontal: secondHorizontal, vertical: secondVertical, arc: secondArc }, getFirst, getSecond }; }34:T2907,// Functions to find the nearest point on curves - depends on curvePoints and derivatives nearestPoint = { // Helper function to check if an angle is within an arc const isAngleInArc = (angle, startAngle, endAngle) => { // Normalize all angles to [0, 2π] const normalizeAngle = (a) => { let result = a % (2 * Math.PI); if (result < 0) result += 2 * Math.PI; return result; }; angle = normalizeAngle(angle); startAngle = normalizeAngle(startAngle); endAngle = normalizeAngle(endAngle); if (startAngle <= endAngle) { return angle >= startAngle && angle <= endAngle; } else { // Arc crosses 0 return angle >= startAngle || angle <= endAngle; } }; // Find closest point on linear segments const line = (target, points) => { const { start, end } = points; const dx = end.x - start.x; const dy = end.y - start.y; const length2 = dx * dx + dy * dy; if (length2 === 0) { const distance = Math.sqrt((start.x - target.x) ** 2 + (start.y - target.y) ** 2); return { t: 0, point: start, distance }; } const t = Math.max(0, Math.min(1, ((target.x - start.x) * dx + (target.y - start.y) * dy) / length2)); const point = curvePoints.linear(t, points); const distance = Math.sqrt((point.x - target.x) ** 2 + (point.y - target.y) ** 2); return { t, point, distance }; }; const horizontal = (target, points) => { const { start, end } = points; const t = Math.max(0, Math.min(1, (target.x - start.x) / (end.x - start.x))); const point = curvePoints.horizontal(t, points); const distance = Math.sqrt((point.x - target.x) ** 2 + (point.y - target.y) ** 2); return { t, point, distance }; }; const vertical = (target, points) => { const { start, end } = points; const t = Math.max(0, Math.min(1, (target.y - start.y) / (end.y - start.y))); const point = curvePoints.vertical(t, points); const distance = Math.sqrt((point.x - target.x) ** 2 + (point.y - target.y) ** 2); return { t, point, distance }; }; // Newton-Raphson method for Bezier curves const newtonRaphson = (target, points, curveType) => { let bestT = 0; let bestDistance = Infinity; // Use more starting points for better coverage const numSamples = 50; const startingPoints = []; for (let i = 0; i <= numSamples; i++) { startingPoints.push(i / numSamples); } // First, do a coarse search to find good starting points const candidates = []; for (let t of startingPoints) { const curvePoint = curvePoints.getPoint(t, curveType, points); const distance = Math.sqrt( (curvePoint.x - target.x) ** 2 + (curvePoint.y - target.y) ** 2 ); candidates.push({ t, distance }); } // Sort candidates by distance and take the best few candidates.sort((a, b) => a.distance - b.distance); const bestCandidates = candidates.slice(0, 5).map(c => c.t); // Now refine using Newton-Raphson on the best candidates for (let startT of bestCandidates) { let t = startT; for (let i = 0; i < 20; i++) { const curvePoint = curvePoints.getPoint(t, curveType, points); const derivative = derivatives.getFirst(t, curveType, points); const secondDerivative = derivatives.getSecond(t, curveType, points); const diff = { x: curvePoint.x - target.x, y: curvePoint.y - target.y }; const f = derivative.x * diff.x + derivative.y * diff.y; const fPrime = secondDerivative.x * diff.x + secondDerivative.y * diff.y + derivative.x * derivative.x + derivative.y * derivative.y; if (Math.abs(fPrime) < 1e-10) break; const newT = t - f / fPrime; t = Math.max(0, Math.min(1, newT)); if (Math.abs(f) < 1e-10) break; } const curvePoint = curvePoints.getPoint(t, curveType, points); const distance = Math.sqrt( (curvePoint.x - target.x) ** 2 + (curvePoint.y - target.y) ** 2 ); if (distance < bestDistance) { bestDistance = distance; bestT = t; } } // Also check the endpoints explicitly const endpointChecks = [0, 1]; for (let t of endpointChecks) { const curvePoint = curvePoints.getPoint(t, curveType, points); const distance = Math.sqrt( (curvePoint.x - target.x) ** 2 + (curvePoint.y - target.y) ** 2 ); if (distance < bestDistance) { bestDistance = distance; bestT = t; } } return { t: bestT, point: curvePoints.getPoint(bestT, curveType, points), distance: bestDistance }; }; // Find closest point on arc/ellipse const arc = (target, points) => { const center = points.center; const rx = Math.sqrt( Math.pow(points.radiusX.x - center.x, 2) + Math.pow(points.radiusX.y - center.y, 2) ); const ry = Math.sqrt( Math.pow(points.radiusY.x - center.x, 2) + Math.pow(points.radiusY.y - center.y, 2) ); const rotation = points._angle; // Transform target to ellipse coordinate system const dx = target.x - center.x; const dy = target.y - center.y; const tx = dx * Math.cos(-rotation) - dy * Math.sin(-rotation); const ty = dx * Math.sin(-rotation) + dy * Math.cos(-rotation); // Find ALL points on the full ellipse where the gradient points to/from target const candidates = []; // Method: Newton-Raphson from multiple starting points const startAngles = [ Math.atan2(ty, tx), // Direct angle Math.atan2(ty/ry, tx/rx), // Stretched angle Math.atan2(-ty, -tx), // Opposite angle Math.atan2(ty/ry, tx/rx) + Math.PI, // Stretched opposite 0, Math.PI/2, Math.PI, 3*Math.PI/2 // Cardinal directions ]; for (let initialTheta of startAngles) { let theta = initialTheta; let converged = false; // Newton-Raphson iteration for (let iter = 0; iter < 15; iter++) { const cosT = Math.cos(theta); const sinT = Math.sin(theta); const px = rx * cosT; const py = ry * sinT; const dx = px - tx; const dy = py - ty; const dpx = -rx * sinT; const dpy = ry * cosT; const d2px = -rx * cosT; const d2py = -ry * sinT; // Function: gradient of distance squared should be perpendicular to ellipse const f = dx * dpx + dy * dpy; // Derivative const df = dpx * dpx + dpy * dpy + dx * d2px + dy * d2py; if (Math.abs(f) < 1e-8) { converged = true; break; } if (Math.abs(df) < 1e-10) break; theta -= f / df; } if (converged) { // Normalize angle to [0, 2π) while (theta < 0) theta += 2 * Math.PI; while (theta >= 2 * Math.PI) theta -= 2 * Math.PI; // Check for duplicates const isDuplicate = candidates.some(c => Math.abs(c - theta) < 0.01 || Math.abs(c - theta + 2*Math.PI) < 0.01 || Math.abs(c - theta - 2*Math.PI) < 0.01 ); if (!isDuplicate) { candidates.push(theta); } } } // Now check which candidates are on the arc and find the closest let bestT = 0; let bestPoint = curvePoints.arc(0, points); let bestDistance = Infinity; let startAngle = points._startAngle; let endAngle = points._endAngle; // Normalize angles to [0, 2π) while (startAngle < 0) startAngle += 2 * Math.PI; while (startAngle >= 2 * Math.PI) startAngle -= 2 * Math.PI; while (endAngle < 0) endAngle += 2 * Math.PI; while (endAngle >= 2 * Math.PI) endAngle -= 2 * Math.PI; // Check all candidates for (let theta of candidates) { // Calculate parameter t for this angle let t; // Handle the arc direction properly if (startAngle <= endAngle) { // Arc doesn't cross 0 if (theta >= startAngle && theta <= endAngle) { t = (theta - startAngle) / (endAngle - startAngle); } else { continue; // Not on arc } } else { // Arc crosses 0 if (theta >= startAngle) { t = (theta - startAngle) / (endAngle + 2*Math.PI - startAngle); } else if (theta <= endAngle) { t = (theta + 2*Math.PI - startAngle) / (endAngle + 2*Math.PI - startAngle); } else { continue; // Not on arc } } if (t >= 0 && t <= 1) { const point = curvePoints.arc(t, points); const distance = Math.sqrt( (point.x - target.x) ** 2 + (point.y - target.y) ** 2 ); if (distance < bestDistance) { bestDistance = distance; bestPoint = point; bestT = t; } } } // Also check the arc endpoints explicitly const startPoint = curvePoints.arc(0, points); const endPoint = curvePoints.arc(1, points); const startDist = Math.sqrt( (startPoint.x - target.x) ** 2 + (startPoint.y - target.y) ** 2 ); const endDist = Math.sqrt( (endPoint.x - target.x) ** 2 + (endPoint.y - target.y) ** 2 ); if (startDist < bestDistance) { bestDistance = startDist; bestPoint = startPoint; bestT = 0; } if (endDist < bestDistance) { bestDistance = endDist; bestPoint = endPoint; bestT = 1; } return { t: bestT, point: bestPoint, distance: bestDistance }; }; // Generic find function const find = (target, curveType, points) => { switch(curveType) { case 'L': return line(target, points); case 'H': return horizontal(target, points); case 'V': return vertical(target, points); case 'C': return newtonRaphson(target, points, 'C'); case 'Q': return newtonRaphson(target, points, 'Q'); case 'A': return arc(target, points); default: return { t: 0, point: curvePoints.getPoint(0, curveType, points), distance: 0 }; } }; return { isAngleInArc, line, horizontal, vertical, newtonRaphson, arc, find }; }35:T1528,// Functions to find extreme points (local minima/maxima) on curves - depends on curvePoints and nearestPoint extremePoints = { // Find extreme points on cubic Bezier const cubic = (points) => { const { start, control1, control2, end } = points; const extremePts = []; // Calculate for X coordinate const a_x = 3 * (end.x - 3*control2.x + 3*control1.x - start.x); const b_x = 6 * (control2.x - 2*control1.x + start.x); const c_x = 3 * (control1.x - start.x); if (Math.abs(a_x) > 1e-10) { const discriminant_x = b_x * b_x - 4 * a_x * c_x; if (discriminant_x >= 0) { const t1_x = (-b_x + Math.sqrt(discriminant_x)) / (2 * a_x); const t2_x = (-b_x - Math.sqrt(discriminant_x)) / (2 * a_x); [t1_x, t2_x].forEach(t => { if (t > 0 && t < 1) { const point = curvePoints.cubic(t, points); extremePts.push({...point, type: 'x-extreme'}); } }); } } else if (Math.abs(b_x) > 1e-10) { const t = -c_x / b_x; if (t > 0 && t < 1) { const point = curvePoints.cubic(t, points); extremePts.push({...point, type: 'x-extreme'}); } } // Calculate for Y coordinate const a_y = 3 * (end.y - 3*control2.y + 3*control1.y - start.y); const b_y = 6 * (control2.y - 2*control1.y + start.y); const c_y = 3 * (control1.y - start.y); if (Math.abs(a_y) > 1e-10) { const discriminant_y = b_y * b_y - 4 * a_y * c_y; if (discriminant_y >= 0) { const t1_y = (-b_y + Math.sqrt(discriminant_y)) / (2 * a_y); const t2_y = (-b_y - Math.sqrt(discriminant_y)) / (2 * a_y); [t1_y, t2_y].forEach(t => { if (t > 0 && t < 1) { const point = curvePoints.cubic(t, points); extremePts.push({...point, type: 'y-extreme'}); } }); } } else if (Math.abs(b_y) > 1e-10) { const t = -c_y / b_y; if (t > 0 && t < 1) { const point = curvePoints.cubic(t, points); extremePts.push({...point, type: 'y-extreme'}); } } return extremePts; }; // Find extreme points on quadratic Bezier const quadratic = (points) => { const { start, control1, end } = points; const extremePts = []; // X coordinate const denom_x = start.x - 2*control1.x + end.x; if (Math.abs(denom_x) > 1e-10) { const t_x = (start.x - control1.x) / denom_x; if (t_x > 0 && t_x < 1) { const point = curvePoints.quadratic(t_x, points); extremePts.push({...point, type: 'x-extreme'}); } } // Y coordinate const denom_y = start.y - 2*control1.y + end.y; if (Math.abs(denom_y) > 1e-10) { const t_y = (start.y - control1.y) / denom_y; if (t_y > 0 && t_y < 1) { const point = curvePoints.quadratic(t_y, points); extremePts.push({...point, type: 'y-extreme'}); } } return extremePts; }; // Find extreme points on arc/ellipse const arcExtreme = (points) => { const center = points.center; const rx = Math.sqrt( Math.pow(points.radiusX.x - center.x, 2) + Math.pow(points.radiusX.y - center.y, 2) ); const ry = Math.sqrt( Math.pow(points.radiusY.x - center.x, 2) + Math.pow(points.radiusY.y - center.y, 2) ); const rotation = points._angle; const extremePts = []; // Get the actual arc angles let startAngle = points._startAngle; let endAngle = points._endAngle; // For X extrema const tanRot = Math.tan(rotation); const xCriticalAngle = Math.atan(-ry * tanRot / rx); const xAngles = [ xCriticalAngle, xCriticalAngle + Math.PI, ]; // For Y extrema const yCriticalAngle = Math.atan(ry / (rx * tanRot)); const yAngles = [ yCriticalAngle, yCriticalAngle + Math.PI, ]; // Check each critical angle [...xAngles, ...yAngles].forEach((angle, idx) => { // Check multiple periods to catch all possibilities for (let k = -1; k <= 2; k++) { let checkAngle = angle + k * 2 * Math.PI; // Check if this angle is within the arc if (nearestPoint.isAngleInArc(checkAngle, startAngle, endAngle)) { const ex = rx * Math.cos(checkAngle); const ey = ry * Math.sin(checkAngle); const x = center.x + ex * Math.cos(rotation) - ey * Math.sin(rotation); const y = center.y + ex * Math.sin(rotation) + ey * Math.cos(rotation); // Avoid duplicates const isDuplicate = extremePts.some(p => Math.abs(p.x - x) < 0.1 && Math.abs(p.y - y) < 0.1 ); if (!isDuplicate) { extremePts.push({ x: x, y: y, type: idx < 2 ? 'x-extreme' : 'y-extreme' }); } } } }); return extremePts; }; // Generic find function const find = (curveType, points) => { switch(curveType) { case 'C': return cubic(points); case 'Q': return quadratic(points); case 'L': case 'H': case 'V': return []; // Linear curves have no internal extrema case 'A': return arcExtreme(points); default: return []; } }; return { cubic, quadratic, arc: arcExtreme, find }; }36:T112f,// Helper functions specific to arc/ellipse handling arcHelpers = { // Update arc endpoint positions based on angles const updateEndpointPositions = (points) => { const center = points.center; const rx = Math.sqrt( Math.pow(points.radiusX.x - center.x, 2) + Math.pow(points.radiusX.y - center.y, 2) ); const ry = Math.sqrt( Math.pow(points.radiusY.x - center.x, 2) + Math.pow(points.radiusY.y - center.y, 2) ); const rotation = points._angle; // Calculate start point position const sx = rx * Math.cos(points._startAngle); const sy = ry * Math.sin(points._startAngle); points.arcStart.x = center.x + sx * Math.cos(rotation) - sy * Math.sin(rotation); points.arcStart.y = center.y + sx * Math.sin(rotation) + sy * Math.cos(rotation); // Calculate end point position const ex = rx * Math.cos(points._endAngle); const ey = ry * Math.sin(points._endAngle); points.arcEnd.x = center.x + ex * Math.cos(rotation) - ey * Math.sin(rotation); points.arcEnd.y = center.y + ex * Math.sin(rotation) + ey * Math.cos(rotation); }; // Initialize arc configuration const initializeArc = (points, previousArcConfig) => { if (previousArcConfig) { // Restore previous arc configuration points.center.x = previousArcConfig.center.x; points.center.y = previousArcConfig.center.y; points.radiusX.x = previousArcConfig.radiusX.x; points.radiusY.y = previousArcConfig.radiusY.y + 1; points.radiusY.x = previousArcConfig.radiusY.x; points.radiusY.y = previousArcConfig.radiusY.y; points._angle = previousArcConfig._angle; points._startAngle = previousArcConfig._startAngle; points._endAngle = previousArcConfig._endAngle; // Trigger a small adjustment to radiusY to force proper initialization const center = points.center; const dx = points.radiusY.x - center.x; const dy = points.radiusY.y - center.y; const yAngle = Math.atan2(dy, dx); const xAngle = yAngle - Math.PI / 2; points._angle = xAngle; // Update X handle to be 90 degrees from Y handle const xDistance = Math.sqrt( Math.pow(previousArcConfig.radiusX.x - previousArcConfig.center.x, 2) + Math.pow(previousArcConfig.radiusX.y - previousArcConfig.center.y, 2) ); points.radiusX.x = center.x + xDistance * Math.cos(xAngle); points.radiusX.y = center.y + xDistance * Math.sin(xAngle); // Now restore exact Y position points.radiusY.x = previousArcConfig.radiusY.x; points.radiusY.y = previousArcConfig.radiusY.y; } else { // First time initializing arc const center = points.center; const radiusY = points.radiusY; radiusY.y += 1; const dy = radiusY.y - center.y; const dx = radiusY.x - center.x; const yAngle = Math.atan2(dy, dx); const xAngle = yAngle - Math.PI / 2; points._angle = xAngle; const xDistance = Math.sqrt( Math.pow(points.radiusX.x - center.x, 2) + Math.pow(points.radiusX.y - center.y, 2) ); points.radiusX.x = center.x + xDistance * Math.cos(xAngle); points.radiusX.y = center.y + xDistance * Math.sin(xAngle); } updateEndpointPositions(points); }; // Get SVG path data for arc const getPathData = (points) => { const center = points.center; const rx = Math.sqrt( Math.pow(points.radiusX.x - center.x, 2) + Math.pow(points.radiusX.y - center.y, 2) ); const ry = Math.sqrt( Math.pow(points.radiusY.x - center.x, 2) + Math.pow(points.radiusY.y - center.y, 2) ); const rotation = points._angle * 180 / Math.PI; // Convert to degrees // Determine arc flags based on angle difference let angleDiff = points._endAngle - points._startAngle; while (angleDiff < 0) angleDiff += 2 * Math.PI; while (angleDiff > 2 * Math.PI) angleDiff -= 2 * Math.PI; const largeArcFlag = angleDiff > Math.PI ? 1 : 0; const sweepFlag = 1; // Always clockwise for consistency return `M ${points.arcStart.x} ${points.arcStart.y} A ${rx} ${ry} ${rotation} ${largeArcFlag} ${sweepFlag} ${points.arcEnd.x} ${points.arcEnd.y}`; }; return { updateEndpointPositions, initializeArc, getPathData }; }37:Tc2a,optimizeLabels = function(points, options = {}) { const { space = 15, // Minimum distance between labels in pixels minY = 0, // Minimum y position maxY = 500, // Maximum y position yScale = d => d // Y scale function (identity by default) } = options; // Sort points by y value (descending) const sortedPoints = [...points].sort((a, b) => b.y - a.y); // Add rank and initial dy position const labelPoints = sortedPoints.map((point, i) => ({ ...point, rank: i, dy: yScale(point.y) })); // Check if we need even spacing const totalRequiredSpace = labelPoints.length * space; const availableSpace = maxY - minY; if (totalRequiredSpace > availableSpace) { // Even spacing mode - distribute labels evenly labelPoints.forEach((point, i) => { point.dy = minY + (availableSpace / (labelPoints.length - 1)) * i; }); } else { // Clustering algorithm to avoid overlaps const groups = []; // Binary search helper function bisectLeft(arr, value) { let left = 0; let right = arr.length; while (left < right) { const mid = Math.floor((left + right) / 2); if (arr[mid].lo < value) { left = mid + 1; } else { right = mid; } } return left; } // Process each point labelPoints.forEach(point => { const targetY = point.dy; const group = { lo: targetY, hi: targetY, center: targetY, items: [point] }; // Insert and merge overlapping groups let j = bisectLeft(groups, group.lo); groups.splice(j, 0, group); // Merge with adjacent groups if they overlap while ( (groups[j + 1]?.lo < groups[j].hi + space) || (groups[j - 1]?.hi > groups[j].lo - space && (--j, true)) ) { const mergedItems = groups[j].items.concat(groups[j + 1].items); const positions = mergedItems.map(item => yScale(item.y)); const center = positions.reduce((sum, pos) => sum + pos, 0) / positions.length; const rangeNeeded = (mergedItems.length - 1) * space; let newLo = center - rangeNeeded / 2; let newHi = center + rangeNeeded / 2; // Constrain to bounds if (newLo < minY) { newLo = minY; newHi = newLo + rangeNeeded; } else if (newHi > maxY) { newHi = maxY; newLo = newHi - rangeNeeded; } groups.splice(j, 2, { lo: newLo, hi: newHi, center: (newLo + newHi) / 2, items: mergedItems }); } }); // Position items within each group groups.forEach(group => { // Sort by original rank group.items.sort((a, b) => a.rank - b.rank); // Distribute evenly within the group group.items.forEach((item, i) => { if (group.items.length === 1) { item.dy = group.center; } else { item.dy = group.lo + i * space; } }); }); } return labelPoints; }38:T629,{ let n = 300 let l0 = {points:[], domain:[.1, 10.1]} let l1 = {points:[], domain:[.1, 3.1]} let l2 = {points:[], domain:[7, 10]} let lines = [l0, l1, l2] let t for( let j=0; j 1/x; let df = (x) => -1/x**2; let rHat = (x) => r / Math.sqrt(1 + df(x)**2) let x=.1 for(let i=0; i<200; i++) { x = x + rHat(x) dx.push({x:x, y:-.6}) ds.push({x:x, y:f(x)}) } let text = [ {x:5, y:1.4, text:'f(x) = 1/x', fill:'black'}, {x:.1, y:-1, text:'0.1', fill:'black'}, {x:1, y:-1, text:'dx', fill:'black'}, {x:.6, y:5.4, text:'∼ds', fill:'red'}, ] return Plot.plot({ x: {domain: [0, 10], grid:true, label: null, ticks:10}, y: {domain: [0, 10], grid:true, label: null, ticks:10}, marginTop:5, marginBottom: 60, width: 500, height: 500, marks: [ Plot.lineY(l0.points, {x: "x", y: "y", strokeWidth :.5}), Plot.lineY(dx, {x: "x", y: "y", stroke :'black', markerStart: 'tick', marker: 'arrow', markerEnd: 'arrow'}), Plot.lineY(ds, {x: "x", y: "y", stroke :'red', markerStart: 'tick', marker: 'arrow', markerEnd: 'arrow'}), Plot.text(text, {x: "x", y: "y", text: 'text', fill:'fill', fontWeight: 'bold', fontSize:12, lineAnchor: "bottom"}), ] }) }3b:[] 2d:{"id":"2564004cb64a321c","slug":null,"title":"Nearest Point on an SVG Curve","thumbnail":"5e024fce4dbe418a960db6839030eaeb68c1d9663f3a0180040028b568c69a00","access_level":"public","create_time":"$D2024-01-30T16:55:43.718Z","update_time":"$D2025-08-22T18:37:21.738Z","view_time":null,"first_public_time":"$D2024-01-30T17:16:10.659Z","fork":false,"stars":6,"starred":false,"owner":{"type":"team","id":"cf45be0120eccaad","login":"laotzunami","name":"Lao","avatar_url":"https://avatars-next.observableusercontent.com/aeddc181df6ca80a347940ba62e17601ac6395e9d2c21142887eca5fd277326a","tier":"starter_2024"},"version":652,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"5da1d0646b8496ac","login":"laotzunami","name":"Lao","avatar_url":"https://avatars-next.observableusercontent.com/9c14da488e1a68ca1868ed025eb7edcce3d300c8a9f3fbcdae66a3daa9ccca63","tier":null}],"members":[{"type":"individual","id":"5da1d0646b8496ac","login":"laotzunami","name":"Lao","avatar_url":"https://avatars-next.observableusercontent.com/9c14da488e1a68ca1868ed025eb7edcce3d300c8a9f3fbcdae66a3daa9ccca63","tier":null,"role":"editor"},{"type":"team","id":"cf45be0120eccaad","login":"laotzunami","name":"Lao","avatar_url":"https://avatars-next.observableusercontent.com/aeddc181df6ca80a347940ba62e17601ac6395e9d2c21142887eca5fd277326a","tier":"starter_2024","role":"viewer"}],"comments":[],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":1,"collection":null,"type":"notebook","body":{"title":"Nearest Point on an SVG Curve","cells":[{"id":0,"value":"# Nearest Point on an SVG Curve","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":624,"value":"Mouse over the chart below to reveal the nearest point on the SVG curves.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":610,"value":"$2f","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":645,"value":"Drag the green point to explore the nearest point on the curve.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":589,"value":"$30","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":571,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":574,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":577,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":580,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":583,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":586,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":628,"value":"$37","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":601,"value":"------------------------","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":648,"value":"## Work in Progress","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":5,"value":"This algorithm finds the nearest point on a set of curves to a mouse position.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":12,"value":"We would like to minimize the distance between a given mouse position ${tex`(p_x, p_y)`} and a point on a function curve ${tex`(x, f(x) )`}. A general strategy is to make a guess based on a heuristic and then optimize with gradient decent.\n\nFirst, we are trying to minimize is the distance between these point, which is given by the Pythagorean formula:\n\n> ${tex`d = \\sqrt{(x-p_x)^2+(f(x)-p_y)^2}`}\n\nWe can use the squared distance as the loss function, which is convenient because it gets rid of the square root:\n\n> ${tex`L = d^2`}
\n> ${tex`L = (x-p_x)^2+(f(x)-p_y)^2`}
\n> ${tex`L = x^2 - 2p_x \\cdot x+ p_x^2 + f^2(x) - 2p_y \\cdot f(x) + p_y^2 `}\n\nLast, the derivative of the loss function:\n\n> ${tex`L' = dL/dx`}
\n> ${tex`L' = 2x - 2p_x + 2 f(x) \\cdot f'(x) - 2p_y \\cdot f'(x)`}
\n> ${tex`L' = 2 ( x - p_x + f'(x) \\cdot [ f(x) - p_y ])`} ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":74,"value":"When creating a list of functions we'd like to consider snapping to, it would be nice to allow a precalculated heuristic, derivative and loss function to speed up efficiency, but also be able to figure out good approximations if it is too much work or there aren't analytic solutions. \n\nAn element in our list of functions will look like this:\n

  element = ({\n    function: f(x),\n    derivative: f'(x)\n    heuristic: h(px, py),\n    domain: [x0, x1],\n    learningRate: dx,\n    optimize: true,\n    radius: false,\n    flip: false,\n  })

\n\nWe need default methods we can use if some of these are missing, or for special cases.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":107,"value":"The first case we should consider is when we just want to use the heuristic without optimizing with gradient decent. This is for when the heuristic give exact solutions or when a line can't be expressed as, especially for a vertical line, which can't be expressed as a function with respect to x. In both of these cases, let's use the heuristic answer as final if the learning rate is 0 or optimize is false, skipping the need for a function, derivative or a domain.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":119,"value":"function defaultFunction ( x ){\n return x\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":151,"value":"function defaultHeuristic( {f=defaultFunction, point=[0,0], domain=defaultDomain} ){\n let n = 1000 // number of sample points\n let x = Math.max( domain[0], Math.min( domain[1], point[0]))\n let dy = Math.sqrt( (point[0] - x )**2 + (point[1] - f(x))**2 ) // distance from the function at the closest x value and the point\n let interval = [ // \n Math.max( domain[0], Math.min( domain[1], x-dy )),\n Math.max( domain[0], Math.min( domain[1], x+dy ))\n ]\n let sampleList = []\n let dx = (interval[1] - interval[0]) / (n-1)\n let Q, sample\n for( let i=0; ix**2, point:[10,0]})","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":134,"value":"defaultDerivative( x => x**2, 1 )","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":288,"value":"We can optimize the heuristic using gradient decent. A key parameter is the learning rate, which defines how big the step the next guess is. A complicating factor is we are optimizing the x position, but really we care about the position of the function point. ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":471,"value":"**Depending on the derivative of the function, a small change in x can result in very different changes along the path**","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":291,"value":"$38","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":416,"value":"Since we are optimizing Euclidean distance, we can normalize the learning rate by approximating the change along the pathlength, and dividing the change in x by this factor. Path length can be approximated by this equation:\n\n> ${tex`ds \\approx \\sqrt{dx^2 + dy^2}`}","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":468,"value":"**The Pythagorean formula can approximate the change in pathlength**","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":441,"value":"$39","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":475,"value":"If we use a unit one change in the x direction, then our path length becomes:\n\n> ${tex`\\hat{ds} \\approx \\sqrt{1 + (f'(x))^2}`}\n\nNow the learning rate ${tex`r`} can be divided by the factor to create the normalized learning rate ${tex`\\hat{r}`}:\n\n> ${tex`\\hat{r} \\approx \\dfrac{r}{\\sqrt{1 + (f'(x))^2}}`}","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":489,"value":"viewof r = Inputs.range([0.1, 5], {label: 'Learning rate r = ', step: 0.01, value: 1})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":485,"value":"**Normalizing a learning rate of ${r.toFixed(2)} produces approximately equal path steps**","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":516,"value":"$3a","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":7,"value":"list = [\n ({function: x=>x**2, derivative: x=>2*x, heuristic: x=>x, domain:[0,1], learningRate:1,})\n]","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"}],"files":"$W3b","stdlib":"1","titling":"auto"}} 2e:"$2d:body"