edemaine
commented
2 years ago Yevhenii and I discussed how to best approach this important PR.
- For starters, we should merge the linear-time checking of intersection, to fix rectangle behavior on Chrome and fix selection overall on Firefox. Need to test in Chrome whether it's faster to filter using the built-in bounding box selection and then do a second pass, or just do the single pass (probably the former).
- We should do some measurement to see whether selection is slow because it's slow to find the items, or something else (DOM manipulation - see #196). If just the latter, the actual data structure here may not be useful, except for huge pages?
- If we do want a data structure, I think we don't want it for the objects that are actively changing, so there should be a delay between when objects change and when the data structure updates (for the case where an object changes a lot in quick succession, to avoid the log factor).
- One natural approach is a FIFO queue of objects. When the data structure is idle, can take the first item off the queue and update the data structure. When an object gets updated, either leave it alone in the queue or move it to the end (but crucially, don't add a second queue item). When doing a search, manually check everything in the queue in addition to querying the data structure.
- If we want, can avoid processing things in the queue that have been updated within the last k seconds.
- This approach might be more difficult to implement with a worker thread, because of the limitations on shared data structures. Maybe it could work by having at most one "update" message for the worker at any time, and when serviced, add another via the queue in the main thread. Queries will also have to be worker messages; hopefully they won't be much delayed.
Fixes #87
Dynamic AABB tree for pruning, and narrowphase collision algorithms for the 6 types of objects: pen, polyline, rectangle, ellipse, text, and image. (Though text just uses its bounding box)