perf(modeling): Inefficient union-find algorithm in scissionGeom3.js

[jbroll]

Summary

scissionGeom3.js implements a union-find-like algorithm inefficiently with nested loops instead of proper Union-Find with path compression.

Usage Frequency: LOW

Only used by scission() operation which splits geometry into disconnected pieces.

Typical model usage: Rare - maybe 1% of models use scission

Problem

File: packages/modeling/src/operations/booleans/scissionGeom3.js
Lines: 53-77

for (let i = 0; i < ippl; i++) {
  const mapi = indexesPerPolygon[i]
  if (mapi.e > 0) {
    const indexes = new Array(pl)
    indexes[i] = true
    do {
      merges = 0
      indexes.forEach((e, j) => {  // O(pl) per iteration
        const mapj = indexesPerPolygon[j]
        if (mapj.e > 0) {
          mapj.e = -1
          for (let d = 0; d < mapj.d.length; d++) {
            indexes[mapj.d[d]] = true
          }
          merges++
        }
      })
    } while (merges > 0)
    // ...
  }
}

This is essentially finding connected components but implemented with O(n²) or worse complexity. The outer loop runs O(polygons), the do-while runs until convergence, and forEach scans all polygons each iteration.

Suggested Fix

Implement proper Union-Find with path compression and union by rank:

class UnionFind {
  constructor(n) {
    this.parent = Array.from({length: n}, (_, i) => i)
    this.rank = new Array(n).fill(0)
  }
  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x])  // Path compression
    }
    return this.parent[x]
  }
  union(x, y) {
    const px = this.find(x), py = this.find(y)
    if (px === py) return
    if (this.rank[px] < this.rank[py]) this.parent[px] = py
    else if (this.rank[px] > this.rank[py]) this.parent[py] = px
    else { this.parent[py] = px; this.rank[px]++ }
  }
}

This gives O(n * α(n)) ≈ O(n) complexity where α is the inverse Ackermann function.

Impact

Low overall (rare operation), but when scission is used on complex geometry with thousands of polygons, the current implementation can be very slow.