21992

Python QuadTree index returning nodes

I have a bounding box of a city containing points. I would like to divide this bounding box into sub boxes according to the importance of the points. For example, regions with more points should correspond to higher number of sub-boxes. Regions with less points should respond to less boxes with larger width.

I understood that a good data structure for that is a quad tree or maybe a KD-Tree. It turns out that most of these libraries just return me the nearest neighbor (This is their main use). I would like to have not the nearest neighbor but the sub box of a point. (lets say leaf id) Is this possible? or event the Quadtree-Data structure the correct to use ? In other words I need the quad tree just to divide the region into sub boxes and not to be used as an index.

The naive solution is to just to divide the bounding box into equal sub boxes.

Answer1:

This is essentially what an R-Tree does. It produces a more or less balanced tree, based on bounding rectangles (boxes), but based on the number of geometric objects that fit inside the box, not on the boxes's area. KD-Trees, on the other hand, recursively divide a space first in the x and then in the y direction, which can make for very efficient searching, but can not be adjusted for areas with a lower or higher density of points. There is a Python implementation of R-Trees here, https://pypi.python.org/pypi/Rtree/. I have never used this (it is built into Postgres/Postgis which I use all the time), but I looks like it could be useful for what you describe.

Recommend

  • For every point in an array, find the closest point to it in a second array and output that index
  • Missing texture in .OBJ model on min3d framwork android
  • How to increase performance of shortest path using Gremlin?
  • Recursion into stack-form. Preserving a search path towards ends of recursion
  • Calculating the vertex normals of a quad
  • Why we need a coarse quantizer?
  • Rendering Blended Lines In OpenGL
  • quadpack.error: Supplied function does not return a valid float in python
  • Python QuadTree index returning nodes
  • Can't unload kext while installing VirtualBox 4.3.6
  • What is the ε (epsilon) parameter in Locality Sensitive Hashing (LSH)?
  • redirect_uri is not owned by the application
  • How to label the weekly chart in ASP.Net chart control
  • Display Table form with Eloquent Data Laravel
  • Render face of cube map to a quad
  • Read file line by line as soon as these lines appear in the file using Apache Camel
  • how does postgres handle the bit data type?
  • Indexing k-d tree?
  • Android Chrome input onkeydown
  • How to find MongoDB field name at arbitrary depth
  • Combining many rectangles into fewer rectangles
  • How to remove left and right margins from all wrapped rows in flexbox (without nth-child or js)
  • undefined reference to `SOIL_load_OGL_texture'?
  • Launch powershell script from UWP app with FullTrustProcessLauncher class
  • include dlls in visual studio c++ 2008
  • Oracle - Second level subquery cannot see field from main query
  • Changing references to deprecated methods C++
  • react split panel resize
  • Can you pass an array from javascript to asp.net mvc controller action without using a form?
  • Configure nginx to return different files to different authenticated users with the same URI
  • Copy to all folders batch file?
  • D3 nodes and links from JSON with nested arrays of children
  • Updated Ionic CLI but shows previous version (Windows)
  • Timeout for blocking function call, i.e., how to stop waiting for user input after X seconds?
  • Benchmarking RAM performance - UWP and C#
  • Django query for large number of relationships
  • Why is Django giving me: 'first_name' is an invalid keyword argument for this function?
  • How can I use `wmic` in a Windows PE script?
  • How to push additional view controllers onto NavigationController but keep the TabBar?