Skip to main content

Space-partitioning trees

Use a tree to represent a recursive subdivision of 2d space

Grid - Divide space uniformly into squares​

2d tree - Recursively divide space into two halfplanes​

Quadtree / Rtree - Recursively divide space into four quadrants​

It is a two-dimensional analog of octrees and is most often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions.

𝙐𝙨𝙚 𝙘𝙖𝙨𝙚: find nearby interest points

BSP tree - Recursively divide space into two regions​

Applications​

  • Ray tracing
  • 2d range search
  • Flight simulators
  • N-body simulation
  • Collision detection
  • Astronomical databases
  • Nearest neighbor search
  • Adaptive mesh generation
  • Accelerate rendering in Doom (game)
  • Hidden surface removal and shadow casting

𝗥𝗔𝗬 𝗖𝗔𝗦𝗧𝗜𝗡𝗚

It is the most basic of many computer graphics rendering algo that uses geometric algo of ray tracing.

𝙐𝙨𝙚 𝙘𝙖𝙨𝙚: using longitude and latitude, return the Country of the point.