diff options
Diffstat (limited to 'src/smart-label-positioning.js')
| -rw-r--r-- | src/smart-label-positioning.js | 524 |
1 files changed, 524 insertions, 0 deletions
diff --git a/src/smart-label-positioning.js b/src/smart-label-positioning.js new file mode 100644 index 0000000..5a48e29 --- /dev/null +++ b/src/smart-label-positioning.js @@ -0,0 +1,524 @@ +/** + * Smart label positioning algorithm + * Finds optimal label positions to avoid collisions with lines and notes + */ + +import { percentToPixel } from "./utils.js"; + +/** + * Calculate optimal label position for a component + * @param {Object} component - Component object with label and coordinates + * @param {Object} mapData - Map data containing all components, edges, notes, etc. + * @param {Object} config - Configuration object + * @param {CanvasRenderingContext2D} ctx - Canvas context for text measurement + * @param {Array} allLines - Pre-collected lines from edges, evolutions, etc. + * @param {Array} noteRects - Pre-collected note rectangles + * @param {Array} inertiaRects - Pre-collected inertia rectangles + * @returns {Object} Position object with x, y coordinates in pixels + */ +export function calculateOptimalLabelPosition( + component, + mapData, + config, + ctx, + allLines, + noteRects, + inertiaRects, +) { + const { mapWidth, mapHeight, vertexWidth, vertexHeight } = + config.theme.sizes; + const { family: fontFamily, vertexLabel: fontSize } = config.theme.fonts; + + const vertexPixelPos = { + x: percentToPixel(component.coordinates[0], mapWidth), + y: percentToPixel(component.coordinates[1], mapHeight), + }; + + // Measure label size + ctx.font = `${fontSize}px ${fontFamily}`; + const actualLabelSize = calculateLabelSize(component.label, ctx, config); + + // Generate 8 candidate positions + const candidatePositions = generateCandidatePositions( + vertexPixelPos, + { width: vertexWidth, height: vertexHeight }, + actualLabelSize, + ); + + // Check default position (right side) first + const defaultPosition = candidatePositions[0]; + const defaultRect = { + x: defaultPosition.x, + y: defaultPosition.y, + width: actualLabelSize.width, + height: actualLabelSize.height, + }; + + if ( + countCollisions(defaultRect, allLines) === 0 && + countNoteCollisions(defaultRect, noteRects) === 0 && + countNoteCollisions(defaultRect, inertiaRects) === 0 + ) { + return defaultPosition; + } + + // Find best position by scoring all candidates + let bestPosition = defaultPosition; + let bestScore = Infinity; + + for (let index = 0; index < candidatePositions.length; index++) { + const position = candidatePositions[index]; + const labelRect = { + x: position.x, + y: position.y, + width: actualLabelSize.width, + height: actualLabelSize.height, + }; + + const collisionCount = countCollisions(labelRect, allLines); + const noteCollisionCount = countNoteCollisions(labelRect, noteRects); + const inertiaCollisionCount = countNoteCollisions( + labelRect, + inertiaRects, + ); + + const distance = Math.sqrt( + Math.pow(position.x - (vertexPixelPos.x + vertexWidth / 2), 2) + + Math.pow(position.y - (vertexPixelPos.y + vertexHeight / 2), 2), + ); + + const ownershipPenalty = calculateOwnershipPenalty( + labelRect, + component, + mapData.components, + config, + ); + + const score = + collisionCount * 100 + + noteCollisionCount * 500 + + inertiaCollisionCount * 300 + + distance * 0.5 + + index * 0.1 + + ownershipPenalty; + + if (score < bestScore) { + bestScore = score; + bestPosition = position; + } + } + + return bestPosition; +} + +/** + * Calculate label size including padding + */ +function calculateLabelSize(text, ctx, config) { + const cleanText = text.replace(/\\n/g, "\n"); + const lines = cleanText.split("\n"); + const lineHeight = config.theme.lineHeights.vertexLabel; + + let maxWidth = 0; + let totalHeight = 0; + + for (const line of lines) { + const metrics = ctx.measureText(line); + maxWidth = Math.max(maxWidth, metrics.width); + totalHeight += lineHeight; + } + + return { + width: Math.ceil(maxWidth) + 4, + height: Math.ceil(totalHeight) + 2, + }; +} + +/** + * Generate 8 candidate positions around the vertex + * Order: right, left, top, bottom, top-right, top-left, bottom-right, bottom-left + */ +function generateCandidatePositions(vertexPixelPos, vertexSize, labelSize) { + const padding = 5; + + return [ + // Right + { + x: vertexPixelPos.x + vertexSize.width + padding, + y: vertexPixelPos.y + (vertexSize.height - labelSize.height) / 2, + }, + // Left + { + x: vertexPixelPos.x - labelSize.width - padding, + y: vertexPixelPos.y + (vertexSize.height - labelSize.height) / 2, + }, + // Top + { + x: vertexPixelPos.x + (vertexSize.width - labelSize.width) / 2, + y: vertexPixelPos.y - labelSize.height - padding, + }, + // Bottom + { + x: vertexPixelPos.x + (vertexSize.width - labelSize.width) / 2, + y: vertexPixelPos.y + vertexSize.height + padding, + }, + // Top-right + { + x: vertexPixelPos.x + vertexSize.width + padding, + y: vertexPixelPos.y - labelSize.height - padding, + }, + // Top-left + { + x: vertexPixelPos.x - labelSize.width - padding, + y: vertexPixelPos.y - labelSize.height - padding, + }, + // Bottom-right + { + x: vertexPixelPos.x + vertexSize.width + padding, + y: vertexPixelPos.y + vertexSize.height + padding, + }, + // Bottom-left + { + x: vertexPixelPos.x - labelSize.width - padding, + y: vertexPixelPos.y + vertexSize.height + padding, + }, + ]; +} + +/** + * Collect all lines from edges, evolutions, inertias, and axes + */ +export function collectAllLines(mapData, config, componentMap) { + const { mapWidth, mapHeight, vertexWidth, vertexHeight } = + config.theme.sizes; + const lines = []; + + // Lines from edges (dependencies) + if (mapData.dependencies) { + mapData.dependencies.forEach((edge) => { + const originCoords = componentMap[edge.origin]; + const destCoords = componentMap[edge.destination]; + if (!originCoords || !destCoords) return; + + const origin = { + x: originCoords[0], + mapWidth, + y: originCoords[1], + mapHeight, + }; + const destination = { + x: destCoords[0], + mapWidth, + y: destCoords[1], + mapHeight, + }; + + const slope = + (destination.y - origin.y) / (destination.x - origin.x); + const angle = Math.atan(slope); + const multiplier = slope < 0 ? -1.0 : 1.0; + + const offsetOrigin = { + x: + origin.x + + multiplier * (vertexWidth / 2.0) * Math.cos(angle), + y: + origin.y + + multiplier * (vertexHeight / 2.0) * Math.sin(angle), + }; + const offsetDestination = { + x: + destination.x - + multiplier * (vertexWidth / 2.0) * Math.cos(angle), + y: + destination.y - + multiplier * (vertexHeight / 2.0) * Math.sin(angle), + }; + + const adjustedOrigin = { + x: offsetOrigin.x + vertexWidth / 2.0, + y: offsetOrigin.y + vertexHeight / 2.0, + }; + const adjustedDestination = { + x: offsetDestination.x + vertexWidth / 2.0, + y: offsetDestination.y + vertexHeight / 2.0, + }; + + lines.push({ start: adjustedOrigin, end: adjustedDestination }); + }); + } + + // Lines from evolutions + if (mapData.evolutions) { + mapData.evolutions.forEach((evolution) => { + const coords = componentMap[evolution.component]; + if (!coords) return; + + const originX = coords[0]; + const originY = coords[1]; + const destX = evolution.value; + + const origin = { + x: originX, + mapWidth, + y: originY, + mapHeight, + }; + const destination = { + x: destX, + mapWidth, + y: originY, + mapHeight, + }; + + const multiplier = destX > originX ? 1.0 : -1.0; + + const offsetOrigin = { + x: origin.x + multiplier * (vertexWidth / 2.0), + y: origin.y, + }; + const offsetDestination = { + x: destination.x - multiplier * (vertexWidth / 2.0), + y: destination.y, + }; + + const adjustedOrigin = { + x: offsetOrigin.x + vertexWidth / 2.0, + y: offsetOrigin.y + vertexHeight / 2.0, + }; + const adjustedDestination = { + x: offsetDestination.x + vertexWidth / 2.0, + y: offsetDestination.y + vertexHeight / 2.0, + }; + + lines.push({ start: adjustedOrigin, end: adjustedDestination }); + }); + } + + // Axis lines (Y-axis and X-axis) + lines.push( + { start: { x: 0, y: 0 }, end: { x: 0, y: mapHeight } }, + { start: { x: 0, y: mapHeight }, end: { x: mapWidth, y: mapHeight } }, + ); + + return lines; +} + +/** + * Collect all note rectangles + */ +export function collectNoteRects(mapData, config, ctx) { + if (!mapData.notes) return []; + + const { mapWidth, mapHeight } = config.theme.sizes; + + return mapData.notes.map((note) => { + const notePixelPos = { + x: percentToPixel(note.coordinates[0], mapWidth), + y: percentToPixel(note.coordinates[1], mapHeight), + }; + const noteSize = calculateLabelSize(note.text, ctx, config); + + return { + x: notePixelPos.x, + y: notePixelPos.y, + width: noteSize.width, + height: noteSize.height, + }; + }); +} + +/** + * Collect all inertia rectangles + */ +export function collectInertiaRects(mapData, config, componentMap) { + if (!mapData.inertias) return []; + + const { vertexWidth, vertexHeight } = config.theme.sizes; + + return mapData.inertias + .map((inertia) => { + if (!inertia.component) return null; + const coordinates = componentMap[inertia.component.toLowerCase()]; + if (!coordinates) return null; + + const x = coordinates[0] + 3 * vertexWidth; + const y = coordinates[1] - (vertexHeight * 2) / 3; + const rectWidth = vertexWidth / 2; + const rectHeight = vertexHeight * 2; + + return { + x, + y, + width: rectWidth, + height: rectHeight, + }; + }) + .filter((rect) => rect !== null); +} + +/** + * Count how many lines intersect with the label rectangle + */ +function countCollisions(labelRect, lines) { + let collisions = 0; + for (const line of lines) { + if (lineIntersectsRect(line, labelRect)) { + collisions++; + } + } + return collisions; +} + +/** + * Count how many notes intersect with the label rectangle + */ +function countNoteCollisions(labelRect, noteRects) { + let collisions = 0; + for (const noteRect of noteRects) { + if (rectsIntersect(labelRect, noteRect)) { + collisions++; + } + } + return collisions; +} + +/** + * Check if two rectangles intersect + */ +function rectsIntersect(rect1, rect2) { + return !( + rect1.x + rect1.width < rect2.x || + rect2.x + rect2.width < rect1.x || + rect1.y + rect1.height < rect2.y || + rect2.y + rect2.height < rect1.y + ); +} + +/** + * Check if a line intersects a rectangle + */ +function lineIntersectsRect(line, rect) { + const rectLines = [ + { + start: { x: rect.x, y: rect.y }, + end: { x: rect.x + rect.width, y: rect.y }, + }, + { + start: { x: rect.x + rect.width, y: rect.y }, + end: { x: rect.x + rect.width, y: rect.y + rect.height }, + }, + { + start: { x: rect.x + rect.width, y: rect.y + rect.height }, + end: { x: rect.x, y: rect.y + rect.height }, + }, + { + start: { x: rect.x, y: rect.y + rect.height }, + end: { x: rect.x, y: rect.y }, + }, + ]; + + for (const rectLine of rectLines) { + if (linesIntersect(line, rectLine)) { + return true; + } + } + + // Check if line endpoints are inside rect + return pointInRect(line.start, rect) || pointInRect(line.end, rect); +} + +/** + * Check if a point is inside a rectangle + */ +function pointInRect(point, rect) { + return ( + point.x >= rect.x && + point.x <= rect.x + rect.width && + point.y >= rect.y && + point.y <= rect.y + rect.height + ); +} + +/** + * Check if two line segments intersect + */ +function linesIntersect(line1, line2) { + const x1 = line1.start.x; + const y1 = line1.start.y; + const x2 = line1.end.x; + const y2 = line1.end.y; + const x3 = line2.start.x; + const y3 = line2.start.y; + const x4 = line2.end.x; + const y4 = line2.end.y; + + const denom = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4); + + if (Math.abs(denom) < 1e-10) { + return false; + } + + const t = ((x1 - x3) * (y3 - y4) - (y1 - y3) * (x3 - x4)) / denom; + const u = -((x1 - x2) * (y1 - y3) - (y1 - y2) * (x1 - x3)) / denom; + + return t >= 0 && t <= 1 && u >= 0 && u <= 1; +} + +/** + * Calculate penalty if label is closer to another vertex than its own + */ +function calculateOwnershipPenalty( + labelRect, + ownComponent, + allComponents, + config, +) { + if (allComponents.length === 0) return 0; + + const { mapWidth, mapHeight, vertexWidth, vertexHeight } = + config.theme.sizes; + + const labelCenter = { + x: labelRect.x + labelRect.width / 2, + y: labelRect.y + labelRect.height / 2, + }; + + const ownVertexPixelPos = { + x: percentToPixel(ownComponent.coordinates[0], mapWidth), + y: percentToPixel(ownComponent.coordinates[1], mapHeight), + }; + const ownVertexCenter = { + x: ownVertexPixelPos.x + vertexWidth / 2, + y: ownVertexPixelPos.y + vertexHeight / 2, + }; + + const distanceToOwnVertex = Math.sqrt( + Math.pow(labelCenter.x - ownVertexCenter.x, 2) + + Math.pow(labelCenter.y - ownVertexCenter.y, 2), + ); + + for (const otherComponent of allComponents) { + if (otherComponent === ownComponent) continue; + + const otherVertexPixelPos = { + x: percentToPixel(otherComponent.coordinates[0], mapWidth), + y: percentToPixel(otherComponent.coordinates[1], mapHeight), + }; + const otherVertexCenter = { + x: otherVertexPixelPos.x + vertexWidth / 2, + y: otherVertexPixelPos.y + vertexHeight / 2, + }; + + const distanceToOtherVertex = Math.sqrt( + Math.pow(labelCenter.x - otherVertexCenter.x, 2) + + Math.pow(labelCenter.y - otherVertexCenter.y, 2), + ); + + if (distanceToOtherVertex < distanceToOwnVertex) { + return 50.0; + } + } + + return 0; +} |