Skip to content

Fix stale QuadItem removal after mutable ClusterItem position updates #1729

Description

@Aparnamohan1312

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

  1. Device: N/A (algorithm-level issue)
  2. Android version: N/A
  3. Library version: Current main branch (commit 0147954)

Steps to reproduce

  1. Create a mutable implementation of ClusterItem.
  2. Add the item to NonHierarchicalDistanceBasedAlgorithm.
  3. Change the item's position.
  4. Call updateItem(item).
  5. 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).

Metadata

Metadata

Assignees

No one assigned

    Labels

    triage meI really want to be triaged.type: bugError or flaw in code with unintended results or allowing sub-optimal usage patterns.

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions