perf(modeling): O(n²) hole assignment in earcut/assignHoles.js

[jbroll]

Summary

assignHoles.js uses nested loops to assign holes to their containing solids, resulting in O(solids × holes × vertices) complexity.

Usage Frequency: MEDIUM

Used during extrusion of 2D shapes that contain holes (e.g., text, shapes with cutouts).

Typical model usage:

• Simple extrusions without holes: Never called
• Text extrusion: Called once per character (letters like 'O', 'A', 'B' have holes)
• Complex 2D shapes with holes: Called during extrusion

Estimated: 10-20% of models use shapes with holes

Problem

File: packages/modeling/src/operations/extrusions/earcut/assignHoles.js
Lines: 38-50

solids.forEach((s, i) => {
  const solid = outlines[s]
  children[i] = []
  holes.forEach((h, j) => {  // O(solids × holes)
    const hole = outlines[h]
    if (arePointsInside([hole[0]], { vertices: solid })) {  // Point-in-polygon: O(vertices)
      children[i].push(h)
      // ...
    }
  })
})

For N solids and M holes with V vertices average, complexity is O(N × M × V).

Suggested Fix

For many holes, use spatial indexing:

// Build bounding boxes for quick rejection
const solidBounds = solids.map(s => getBoundingBox(outlines[s]))

solids.forEach((s, i) => {
  const solid = outlines[s]
  const bounds = solidBounds[i]
  children[i] = []
  
  holes.forEach((h, j) => {
    const hole = outlines[h]
    const holePoint = hole[0]
    
    // Quick bounding box check first
    if (holePoint[0] < bounds.min[0] || holePoint[0] > bounds.max[0] ||
        holePoint[1] < bounds.min[1] || holePoint[1] > bounds.max[1]) {
      return  // Skip expensive point-in-polygon test
    }
    
    if (arePointsInside([holePoint], { vertices: solid })) {
      children[i].push(h)
    }
  })
})

For very many holes, consider R-tree or grid-based spatial indexing.

Impact

Medium - noticeable when extruding text or complex shapes with many holes. Most simple models won't hit this.