Difference between revisions of "User:AW/Kd-Tree/thoughts"
(not quite how the algorithm works...) |
|||
| Line 19: | Line 19: | ||
In this case - and I'm kind of mangling the algorithm here, but for the sake of argument - let's say it gets back to the root and the closest point so far is point one=(0.5, 0.8). It then checks: what is the shortest possible distance for any theoretical point ont he other side of the partition? This is just the distance on the splitting axis, so 0.55-0.5=0.05 for the theoretical point (0.5, 0.45) that could exist on the other side. Since this is closer than the distance to the current nearest point, it will descend the other side of that node and look for closer points. Does that make sense? --[[User:Voidious|Voidious]] 01:43, 14 March 2011 (UTC) | In this case - and I'm kind of mangling the algorithm here, but for the sake of argument - let's say it gets back to the root and the closest point so far is point one=(0.5, 0.8). It then checks: what is the shortest possible distance for any theoretical point ont he other side of the partition? This is just the distance on the splitting axis, so 0.55-0.5=0.05 for the theoretical point (0.5, 0.45) that could exist on the other side. Since this is closer than the distance to the current nearest point, it will descend the other side of that node and look for closer points. Does that make sense? --[[User:Voidious|Voidious]] 01:43, 14 March 2011 (UTC) | ||
| + | |||
| + | |||
| + | I think so. Basically, the tree only trims points in nodes whose boundries are farther away than the current closest point after first descending to a leaf, right? Has anyone tried using a voronoi diagram type aproach to eliminate this? (assuming two dimensions again) One couldn't do a simple less than greater than, but one could store the equation of a line f(x) and then given a point (a, b) trim based on whether f(a) > b. Do you think this is worth a try? -- [[User:AW|AW]] 02:30, 14 March 2011 (UTC) | ||
Revision as of 03:30, 14 March 2011
I was thinking about how to write a kd-tree and I think that none of the ones I have seen are 100% accurate. For example assume a 2 dimensional space which for convenience will be a the refered to by the cartesian coordinate system ({x | 0 < x < 1} {y | 0 < y < 1}). Suppose we had these points added in this order and the tree was partitioned with one point in each node (if you don't understand / I described this incorrectly, please see: Spatial Index Demos).
1) point one: (0.5, 0.8)
2) point two: (0.45, 0.5)
at this point the data is partitioned (ie. the graph is divided by the line x = 0.5)
3) point three: (0.55, 0.45)
point three is closer to point two than it is to point one, but the kd-tree will say the closest match is point one. The proper way to do partition this would look more like a voronoi diagram, but this would make the trees slower.
Am I right?
--AW 00:56, 14 March 2011 (UTC)
Nope, it will say the closest point is point two, but in this case it won't be any faster than a brute force search. It will descend to the right because 0.55 > 0.5, but on the way back up it will check if it's possible there are any points on the other side of each split that could be closer than the current closest point.
In this case - and I'm kind of mangling the algorithm here, but for the sake of argument - let's say it gets back to the root and the closest point so far is point one=(0.5, 0.8). It then checks: what is the shortest possible distance for any theoretical point ont he other side of the partition? This is just the distance on the splitting axis, so 0.55-0.5=0.05 for the theoretical point (0.5, 0.45) that could exist on the other side. Since this is closer than the distance to the current nearest point, it will descend the other side of that node and look for closer points. Does that make sense? --Voidious 01:43, 14 March 2011 (UTC)
I think so. Basically, the tree only trims points in nodes whose boundries are farther away than the current closest point after first descending to a leaf, right? Has anyone tried using a voronoi diagram type aproach to eliminate this? (assuming two dimensions again) One couldn't do a simple less than greater than, but one could store the equation of a line f(x) and then given a point (a, b) trim based on whether f(a) > b. Do you think this is worth a try? -- AW 02:30, 14 March 2011 (UTC)
