1import { useCallback, useEffect, useMemo, useRef, useState } from 'react'
2import {
3 Box, Button, Checkbox, FormControl, FormControlLabel, InputLabel,
4 MenuItem, Select, Slider, Stack, Typography,
5} from '@mui/material'
6import { getQhull } from '../qhull'
7import { points2D, type Dist2D } from '../points'
9const SIZE = 520
10const PAD = 24
12interface Result { pts: number[][]; tris: number[][]; hull: number[][] }
14export function Delaunay2D() {
15 const [dist, setDist] = useState<Dist2D>('uniform')
16 const [n, setN] = useState(60)
17 const [seed, setSeed] = useState(1)
18 const [extra, setExtra] = useState<number[][]>([])
19 const [showTri, setShowTri] = useState(true)
20 const [showHull, setShowHull] = useState(true)
21 const [showCircles, setShowCircles] = useState(false)
23 const pts = useMemo(
24 () => [...points2D(n, dist, seed), ...extra],
25 [n, dist, seed, extra],
26 )
28 // The triangulation/hull are stored together with the exact points they were
29 // computed from, so facet indices can never reference a stale (out-of-range)
30 // point set while qhull is recomputing.
31 const [result, setResult] = useState<Result>({ pts: [], tris: [], hull: [] })
33 useEffect(() => {
34 let cancelled = false
35 getQhull().then((q) => {
36 if (cancelled) return
37 if (pts.length < 3) { setResult({ pts, tris: [], hull: [] }); return }
38 try {
39 setResult({ pts, tris: q.delaunay(pts, 2).facets, hull: q.convexHull(pts, 2).facets })
40 } catch {
41 setResult({ pts, tris: [], hull: [] })
42 }
43 })
44 return () => { cancelled = true }
45 }, [pts])
47 // Map data coords (roughly [0,1]) to screen.
48 const toScreen = useCallback((p: number[]) => [
49 PAD + p[0] * (SIZE - 2 * PAD),
50 SIZE - (PAD + p[1] * (SIZE - 2 * PAD)),
51 ], [])
53 const svgRef = useRef<SVGSVGElement>(null)
54 const addPoint = (e: React.MouseEvent) => {
55 const svg = svgRef.current
56 if (!svg) return
57 const r = svg.getBoundingClientRect()
58 const sx = ((e.clientX - r.left) / r.width) * SIZE
59 const sy = ((e.clientY - r.top) / r.height) * SIZE
60 const x = (sx - PAD) / (SIZE - 2 * PAD)
61 const y = (SIZE - sy - PAD) / (SIZE - 2 * PAD)
62 setExtra((cur) => [...cur, [x, y]])
63 }
65 const { pts: rpts, tris, hull } = result
66 const circles = useMemo(
67 () => (showCircles ? tris.map((t) => circumcircle(rpts[t[0]], rpts[t[1]], rpts[t[2]])) : []),
68 [showCircles, tris, rpts],
69 )
71 return (
72 <Stack spacing={2}>
73 <Typography variant="body2" color="text.secondary">
74 Delaunay triangulation (blue) and convex hull (orange) computed by qhull-wasm.
75 Click the canvas to add points.
76 </Typography>
77 <Stack direction="row" spacing={2} flexWrap="wrap" alignItems="center" useFlexGap>
78 <FormControl size="small" sx={{ minWidth: 130 }}>
79 <InputLabel>Distribution</InputLabel>
80 <Select label="Distribution" value={dist} onChange={(e) => { setDist(e.target.value as Dist2D); setExtra([]) }}>
81 <MenuItem value="uniform">Uniform</MenuItem>
82 <MenuItem value="disk">Disk</MenuItem>
83 <MenuItem value="gaussian">Gaussian</MenuItem>
84 <MenuItem value="grid">Jittered grid</MenuItem>
85 </Select>
86 </FormControl>
87 <Box sx={{ width: 180 }}>
88 <Typography variant="caption">Points: {n}</Typography>
89 <Slider size="small" min={4} max={400} value={n} onChange={(_, v) => setN(v as number)} />
90 </Box>
91 <Button size="small" variant="outlined" onClick={() => { setSeed((s) => s + 1); setExtra([]) }}>
92 Regenerate
93 </Button>
94 <FormControlLabel control={<Checkbox size="small" checked={showTri} onChange={(e) => setShowTri(e.target.checked)} />} label="Triangulation" />
95 <FormControlLabel control={<Checkbox size="small" checked={showHull} onChange={(e) => setShowHull(e.target.checked)} />} label="Hull" />
96 <FormControlLabel control={<Checkbox size="small" checked={showCircles} onChange={(e) => setShowCircles(e.target.checked)} />} label="Circumcircles" />
97 </Stack>
99 <Box sx={{ border: '1px solid #ddd', borderRadius: 1, width: 'fit-content', maxWidth: '100%' }}>
100 <svg
101 ref={svgRef}
102 viewBox={`0 0 ${SIZE} ${SIZE}`}
103 style={{ width: SIZE, maxWidth: '100%', height: 'auto', display: 'block', cursor: 'crosshair', background: '#fafafa' }}
104 onClick={addPoint}
105 >
106 {showCircles && circles.map((c, i) => c && (
107 <circle key={`c${i}`} cx={toScreen([c.x, c.y])[0]} cy={toScreen([c.x, c.y])[1]}
108 r={c.r * (SIZE - 2 * PAD)} fill="none" stroke="#26a69a" strokeWidth={0.5} opacity={0.4} />
109 ))}
110 {showTri && tris.map((t, i) => {
111 const a = toScreen(rpts[t[0]]), b = toScreen(rpts[t[1]]), c = toScreen(rpts[t[2]])
112 return <polygon key={`t${i}`} points={`${a[0]},${a[1]} ${b[0]},${b[1]} ${c[0]},${c[1]}`}
113 fill="#1976d2" fillOpacity={0.07} stroke="#1976d2" strokeWidth={0.8} />
114 })}
115 {showHull && hull.map((e, i) => {
116 const a = toScreen(rpts[e[0]]), b = toScreen(rpts[e[1]])
117 return <line key={`h${i}`} x1={a[0]} y1={a[1]} x2={b[0]} y2={b[1]} stroke="#f57c00" strokeWidth={2.2} />
118 })}
119 {rpts.map((p, i) => {
120 const s = toScreen(p)
121 return <circle key={`p${i}`} cx={s[0]} cy={s[1]} r={2.4} fill="#222" />
122 })}
123 </svg>
124 </Box>
126 <Typography variant="body2" color="text.secondary">
127 {rpts.length} points → {tris.length} triangles, {hull.length} hull edges.
128 </Typography>
129 </Stack>
130 )
131}
133function circumcircle(a: number[], b: number[], c: number[]) {
134 const ax = a[0], ay = a[1], bx = b[0], by = b[1], cx = c[0], cy = c[1]
135 const d = 2 * (ax * (by - cy) + bx * (cy - ay) + cx * (ay - by))
136 if (Math.abs(d) < 1e-12) return null
137 const ux = ((ax * ax + ay * ay) * (by - cy) + (bx * bx + by * by) * (cy - ay) + (cx * cx + cy * cy) * (ay - by)) / d
138 const uy = ((ax * ax + ay * ay) * (cx - bx) + (bx * bx + by * by) * (ax - cx) + (cx * cx + cy * cy) * (bx - ax)) / d
139 return { x: ux, y: uy, r: Math.hypot(ax - ux, ay - uy) }
140}