- Código:
k = 2
def build_kdtree(points, depth=0, parent_split=None):
n = len(points)
if n <= 0:
return None
axis = depth % k
sorted_points = sorted(points, key=lambda point: point[axis])
if n == 1:
return {
'point': sorted_points.pop()
}
else:
mid_point = int((n - 1) / 2)
split_value = sorted_points[mid_point][axis]
no = {
"split": split_value,
"left": build_kdtree(sorted_points[: mid_point+1], depth + 1),
"right": build_kdtree(sorted_points[mid_point+1 :], depth + 1),
# these are bottom-left point and top-right points
}
return no
segue um caso de exemplo:
- Código:
kdtree = build_kdtree([
(-13,8),
(-11,-7),
(-8,-1),
(-8,6),
(-5,-5),
(-2,2),
(2,7),
(4,-6),
(6,5),
(8,-3),
])
pprint.pprint(kdtree)
