Shape-aware hitmap / touch-funnelling for dense touch UIs
touch-funnel is a small library and reference implementation designed to produce deterministic, shape-aware hit partitions for dense touch interfaces (mobile/web). The project converts a set of interactive "sites" (rectangular buttons, icons, breadcrumbs, or arbitrary polygons) into an overlay of disjoint hit regions that map every pointer location either to the nearest active site or leave the location uncovered (a "hole") so the underlying content receives the event.
The goal is to provide an approachable, web-centric solution that:
- Preserves visual density while guaranteeing usable effective hit areas where possible.
- Partitions space predictably (midline boundaries) between sites, but allows per-site constraints (minimum area, max influence radius, exclusion masks).
- Integrates with standard web UAs by rendering an overlay (SVG/Canvas/WebGL) that participates in normal UA hit testing rather than relying on late event-swizzling by page JS.
- Is pragmatic, incremental, and easy to iterate on (sampling+merge baseline; GPU/exact fallbacks planned).
- Dense toolbars / icon strips where visual spacing is tight but touching should still be reliable.
- Canvas- or map-like UIs with many small interactive hotspots where nearest-target behavior should be deterministic and configurable.
- Touch-first applications where accessibility and reduced mis-tap rates are critical.
- UIs that need holes — areas that intentionally let events pass through to content (e.g., text, map pan, interactive content areas).
The plain point-site Voronoi (as implemented by d3-delaunay / typical Voronoi libs) partitions the plane by distance to site centroids. That makes a number of implicit assumptions that are incorrect for UI hitmaps:
- Sites have non-trivial extents. UI controls are rectangles or rounded rects, not points. Midlines between centers are not the same as midlines between shapes.
- Minimum effective hit area (44pt/48dp or custom) is essential. Voronoi makes no provision to guarantee a minimum area per-site; small sites in dense clusters get tiny cells.
- Full coverage by default (no holes). Standard Voronoi fills the bounding box, which will steal events from underlying content unless you explicitly clip or omit cells.
- Weighted/Apollonius diagrams (by site size) partially help, but still don’t express constraints like "at least N px area" or "cap influence at radius R" cleanly.
Because of these reasons, using point-Voronoi verbatim leads to surprising UX: tiny cells, non-intuitive boundaries, or stolen events. Instead touch-funnel is opinionated about what the overlay should do and provides mechanisms to enforce min areas, clip influence, and create holes.
The project implements an initial, practical algorithm (sampling + merge + clip) with these stages:
- Site representation: each interactive site is provided as a descriptor (rect or polygon) plus optional per-site constraints (minArea padding, maxInfluenceRadius, priority/weight).
- Sampling: each site is sampled using a small set of points (center, edge samples, optional corners). The sampling density is tunable per-site or globally.
- Point Voronoi: compute a point-based Voronoi (delaunay/voronoi via d3-delaunay) for the collected sample points.
- Merge: union all Voronoi cells that belong to the same site (polygon union of the sample cells) producing a MultiPolygon per site.
- Clip & mask: intersect each merged polygon with the site’s active mask, which can be:
- an expanded rectangle (hit-slop) representing minimum area, or
- a circle of radius R around the site center (maxInfluence), or
- a custom exclusion/inclusion mask to create holes.
- Render overlay: emit SVG polygons (pointer-events enabled) or a WebGL/canvas hitmap that the UA will pick up as the event target. The overlay is aria-hidden and forwards activations (focus() + click()/activation) to underlying DOM elements.
This approach is a pragmatic compromise: it runs in-browser, is tunable, and produces predictable midline partitions while letting you enforce per-site minimums and holes.
-
Exact geometric Voronoi for shapes (polygons/segments): mathematically correct (use CGAL, Boost.Polygon Voronoi, or other computational geometry libs). Pros: exact boundaries between arbitrary shapes. Cons: heavy C++ libraries, harder to compile to WASM, more complex integration and licensing considerations.
-
Apollonius / power diagrams (weighted Voronoi): useful when site radius/weight can be encoded as a scalar. Pros: often better matches variable-size sites. Cons: weights are a limited model for true rectangular shapes and minimum-area constraints.
-
GPU / fragment-shader hitmap: Render nearest-site id per-pixel in an offscreen WebGL shader using signed-distance-to-shape or distance-to-rect metrics. Pros: extremely fast for dynamic scenes and continuous transforms; exact per-pixel control and supports masking. Cons: more complex to implement, must handle DPR, accessibility mapping, and shaders for complex shapes.
-
Pure JS exact geometry libraries / WASM: port/compile a geometry library (CGAL/Boost) to WebAssembly. Pros: exact result in-browser. Cons: heavy build, large binary, and complexity of maintaining a WASM toolchain.
- Performance: sampling density trades off fidelity vs CPU. For typical UI scales (tens to low hundreds of sites) sampling+merge is acceptable on modern devices. For very large or highly dynamic scenes prefer GPU hitmap.
- DPR and transforms: overlay coordinates must match visual coordinates at devicePixelRatio and during CSS transforms/zoom; recompute on resize/scroll/transform and debounce via requestAnimationFrame.
- Accessibility: ensure underlying controls remain in the accessibility tree. The overlay should be aria-hidden and activations forwarded to the real elements. Keep keyboard focus order intact and provide equivalent keyboard activation paths.
- Hit testing semantics: overlay polygons change UA hit-testing behavior. Provide debug mode to visualize polygons and QA the hitmap.
- Edge cases: overlapping rectangles, collinear centers, degenerate triangulations. Use robust polygon-clipping libraries and add fallbacks.
- Input latency & gestures: avoid synthesizing pointer events for primary gesture flows because it can break native gestures; prefer overlay elements that the UA will pick natively.
A minimal public API to begin with (example):
import { buildTouchFunnel } from 'touch-funnel';
const funnel = buildTouchFunnel({
sites: [
{ id: 'a', rect: { x: 12, y: 20, width: 28, height: 28 }, minAreaPadding: 8, maxRadius: 48 },
{ id: 'b', rect: { x: 60, y: 20, width: 28, height: 28 }, minAreaPadding: 8 }
],
bounds: [0,0,deviceWidth, deviceHeight],
options: { samplesPerEdge: 4, circleSegments: 24 }
});
// returns polygons per site (MultiPolygon) suitable for rendering as SVG overlay
const { polygonsById } = funnel.compute();
// optional: funnel.renderSvgOverlay(container);- src/
- index.js (exports)
- touchFunnel.js (core algorithm)
- util/ (geometry helpers, sampling)
- examples/
- demo.html (browser demo with SVG overlay)
- test/
- example.js
- package.json
- README.md
Initial implementation uses d3-delaunay for triangulation and martinez-polygon-clipping for polygon union/intersection. These choices keep the code small and browser-friendly.
- Visual debugging mode to render overlay polygons with semitransparent fills and outlines.
- Unit tests for:
- sample generation correctness,
- merging correctness (simple 2-site, 3-site configs),
- clipping behavior when maxRadius or mask present,
- edge cases (collinear, coincident sites).
- Integration tests on real devices (iPhones and Android) to validate perceived tap ease and mis-tap rates.
- Overlay elements must be aria-hidden to avoid duplication in the accessibility tree.
- Activation must forward to the original DOM control using focus() then activation (click() or custom handler).
- Keyboard users must be able to reach every control via tab order — overlay should not obstruct focus navigation.
- GPU hitmap implementation (WebGL / fragment shader) for very dynamic or large-scale UIs.
- Exact polygonal Voronoi via WASM binding to computational geometry library for high-fidelity requirements.
- Plugin hooks for custom distance metrics (e.g., Manhattan, weighted, shape-aware metrics).
- Integration examples for React / React Native Web / Svelte.
Default to ISC-compatible permissive license (same as d3-delaunay) unless you prefer MIT. Add LICENSE file later.
- Primary design decision: keep triangulation (Delaunay) plumbing if you want; replace only the diagram generator. The d3-delaunay repo is a good reference and a useful dependency for the sampling approach.
- Essential source files to inspect when modifying:
src/touchFunnel.js(or equivalent),src/util/sampling.js, and the demo renderer. - Tests should be deterministic; use fixed bounds and predictable sample densities when asserting polygon shapes.
- Performance: add a micro-benchmark harness that measures compute time for N sites with S samples-per-edge on representative devices/browsers.
End of README