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