0

I'm attempting to build a multi-shape index in Python. The shapes are recognized using OpenCV and a CNN, yielding x, y, w, h, class and dominant color of the shape. The shapes move around and position changes are captured in real-time.

In order to work with the shapes, I'm thinking that the coordinates (x,y) might be the best choice for an index. I'm now looking for an updatable data structure with fast lookup by coordinates. The datastructure should have a well-tested Python implementation and support the following operations (fast):

  • Store object A with coordinates (x0, y0)
  • Retrieve closest object to coordinates (x,y) (returns object O)
  • Update object A with previous coordinates (x0,y0) for new position (x1,y1)
  • Delete object A with previous coordinates (x1,y1)

I've looked at scipy.spatial.KDTree but it doesn't support updates. Theoretically R*-Trees would be an adequate choice (correct me if I'm wrong), but I can't find a Python library that explicitely claims to have fast updates.

Which libraries should I look at? Alternative solutions for the given problem are welcome as well.

Kalsan
  • 822
  • 1
  • 8
  • 19
  • You can look into quad trees. – Silver Nov 14 '18 at 15:54
  • Most implementations (e.g. https://stackoverflow.com/questions/2298517/are-any-of-these-quad-tree-libraries-any-good or https://github.com/karimbahgat/Pyqtree ) provide "updates" under the form of removing and adding objects. Do you know of a library that allows to actually modify the coordinates as in operation 3? – Kalsan Nov 14 '18 at 16:00
  • Can't you just remove and add with the new co-ords? – Silver Nov 14 '18 at 16:07
  • Would that be the state-of-the-art way to update a coordinate? I'm completely unexperienced and my whole question might be due to a misconception. – Kalsan Nov 14 '18 at 20:51

0 Answers0