Pedro M. M. de Castro · derived from SoCG 2011
Choose a point to begin.
Experiment settings
Four square corners are retained at every level. Changing the point set clears memory, playback and accumulated counts.
One x y pair per line in [0, 1]; up to 180 points and 30 KB.
Six strategies. The same query.
Pedro M. M. de Castroderived from Olivier Devillers and Pedro Machado Manhães de Castro. A Pedagogic JavaScript Program for Point Location Strategies. Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry (SoCG ’11). ACM, 2011, pp. 295–296. doi:10.1145/1998196.1998244.
We would like to thank Olivier Devillers, coauthor of the source paper. Tools for computational exploration and implementation: OpenAI Codex and Anthropic Claude.
Click the map or enter coordinates. Compare where each search starts and how it crosses edges or changes levels.
q The query stays at its true position.
→ Blue edges were crossed; arrows show the visit order.
J Chosen landmark: jump to its starting triangle.
1 Remembered query: age 1 is the most recent.
v Vertex in the fixed random sample.
▧ The outlined triangle contains q.
↕ Connected levels show climbs and descents.
Labels may move apart to stay readable; leader lines point to exact coordinates. The Detail button opens an enlarged view of close points or thin triangles without covering the map. Keep strategies store previous queries, shown as numbered circles. A fixed sample uses vertex labels instead. J marks the chosen jump source, even when its age changes after q is added. × marks the query that left memory. The red edge is the current crossing; blue edges have already been crossed on the level shown. A search can leave a level and return later: these are separate passes, labelled P1, P2 on the map when more than one has been recorded. The history below the map counts crossings on the viewed level and lists each pass’s entry and exit levels. Travel between passes takes place on other levels; no flat arrow joins them. The event strip reports the active search level. Use the level squares below a hierarchical map to inspect any existing level; their numbers show vertex counts. The outlined square is the map you are viewing; the wine-coloured bar marks the active search level. Follow resumes automatic tracking. A new query, replay or strategy change also resumes tracking. Hierarchy opens the actual triangulations with query projections; opening and closing it preserves playback.
Keyboard: on the map, use arrow keys to position the target and Enter to query. Elsewhere, Space plays/pauses; Left/Right step; Home/End go to the first/last event. Reduced motion starts queries paused.
All six searches are computed. Playback follows the visible panels; the counts are illustrative operations, not running times.
Scientific notes & credits ↗SoCG 2011 paper ↗Point-location research ↗
Original demonstration: Pedro Machado Manhães de Castro & Olivier Devillers.
Totals belong to the computed query. Playback is a separate view of its trace. Counts exclude triangulation, predicates and drawing; they are not execution times. Accumulation resets only on request or a new point set.
