Timeline for Optimizing a quadtree for circles and circular queries
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 30, 2020 at 12:50 | comment | added | wondra | I wonder if Lp space would be of use here, after all, L1 circle is a square and Linf circle is axis-aligned square... | |
| Sep 29, 2020 at 16:25 | comment | added | Romen | @Philipp, Suppose you called this structure a "Hex Tree". You would need each hexagon node on the tree to be composed of hexagons. Luckily 7 hexagons in a flower shape make a pretty good approximation of a hexagon overall, but even this kind of tree would cover space such that a point near hexagon borders could be inserted in more than one branch on the tree. Maybe you could come up with a clever rule about the hexagon borders to determine which branch the point is in... But that still makes searching the tree for that entry a lot less optimized than a quad tree. | |
| Sep 29, 2020 at 11:55 | answer | added | Philipp | timeline score: 3 | |
| Sep 29, 2020 at 11:01 | comment | added | Philipp | Circles could be difficult. But I wonder if a hexagonal data structure could work. Hexagons are a pretty good approximation of circles, and they are one of the three regular polygons which can be used to tessellate a 2-dimensional plane. | |
| Sep 29, 2020 at 9:06 | comment | added | wondra | Do the object stored move frequently? If so, are you sure(tried regular quad-tree) the cost of maintaining any structure would not massively overshadow the rather cheap circle-circle collision detection? Are the objects more or less distributed evenly or in clusters? | |
| Sep 28, 2020 at 20:58 | answer | added | Romen | timeline score: 2 | |
| Sep 28, 2020 at 18:27 | review | First posts | |||
| Oct 12, 2020 at 18:20 | |||||
| Sep 28, 2020 at 18:19 | history | asked | Aaron Eads | CC BY-SA 4.0 |