Summary
NonHierarchicalDistanceBasedAlgorithm.updateItem() may fail to remove the previously indexed QuadItem when a mutable ClusterItem changes position before calling updateItem().
Expected behavior
Calling updateItem() after modifying a ClusterItem's position should remove the previously indexed QuadItem from the PointQuadTree and reinsert the updated item, leaving only a single indexed entry.
Observed behavior
removeItem() reconstructs a new QuadItem using the current state of the ClusterItem.
Since QuadItem caches the projected point during construction, if the item's position has changed before updateItem() is called, the reconstructed QuadItem contains the updated coordinates instead of the coordinates used during insertion.
PointQuadTree.remove() navigates the tree using these updated coordinates and may fail to remove the originally indexed QuadItem, leaving a stale entry in the spatial index.
Environment details
- Device: N/A (algorithm-level issue)
- Android version: N/A
- Library version: Current
main branch (commit 0147954)
Steps to reproduce
- Create a mutable implementation of
ClusterItem.
- Add the item to
NonHierarchicalDistanceBasedAlgorithm.
- Change the item's position.
- Call
updateItem(item).
- Observe that
removeItem() reconstructs a new QuadItem using the updated coordinates rather than the original indexed instance.
Code example
TestingItem item = new TestingItem("item", 0.1, 0.1);
NonHierarchicalDistanceBasedAlgorithm<ClusterItem> algo =
new NonHierarchicalDistanceBasedAlgorithm<>();
algo.addItem(item);
// Position changes before update.
item.setPosition(0.8, 0.8);
algo.updateItem(item);
Stack trace
N/A (logical correctness issue; no exception is thrown).
Summary
NonHierarchicalDistanceBasedAlgorithm.updateItem()may fail to remove the previously indexedQuadItemwhen a mutableClusterItemchanges position before callingupdateItem().Expected behavior
Calling
updateItem()after modifying aClusterItem's position should remove the previously indexedQuadItemfrom thePointQuadTreeand reinsert the updated item, leaving only a single indexed entry.Observed behavior
removeItem()reconstructs a newQuadItemusing the current state of theClusterItem.Since
QuadItemcaches the projected point during construction, if the item's position has changed beforeupdateItem()is called, the reconstructedQuadItemcontains the updated coordinates instead of the coordinates used during insertion.PointQuadTree.remove()navigates the tree using these updated coordinates and may fail to remove the originally indexedQuadItem, leaving a stale entry in the spatial index.Environment details
mainbranch (commit0147954)Steps to reproduce
ClusterItem.NonHierarchicalDistanceBasedAlgorithm.updateItem(item).removeItem()reconstructs a newQuadItemusing the updated coordinates rather than the original indexed instance.Code example
Stack trace
N/A (logical correctness issue; no exception is thrown).