Python/data_structures/kd_tree/build_kdtree.py at master · ivan53/Python · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
# Created by: Ramy-Badr-Ahmed (https://github.com/Ramy-Badr-Ahmed)
# in Pull Request: #11532
# https://github.com/TheAlgorithms/Python/pull/11532
#
# Please mention me (@Ramy-Badr-Ahmed) in any issue or pull request
# addressing bugs/corrections to this file.
# Thank you!

fromdata_structures.kd_tree.kd_nodeimportKDNode


defbuild_kdtree(points: list[list[float]], depth: int=0) ->KDNode|None:
"""
 Builds a KD-Tree from a list of points.

 Args:
 points: The list of points to build the KD-Tree from.
 depth: The current depth in the tree
 (used to determine axis for splitting).

 Returns:
 The root node of the KD-Tree,
 or None if no points are provided.
 """
ifnotpoints:
returnNone

k=len(points[0]) # Dimensionality of the points
axis=depth%k

# Sort point list and choose median as pivot element
points.sort(key=lambdapoint: point[axis])
median_idx=len(points) //2

# Create node and construct subtrees
left_points=points[:median_idx]
right_points=points[median_idx+1 :]

returnKDNode(
point=points[median_idx],
left=build_kdtree(left_points, depth+1),
right=build_kdtree(right_points, depth+1),
 )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
# Created by: Ramy-Badr-Ahmed (https://github.com/Ramy-Badr-Ahmed)
# in Pull Request: #11532
# https://github.com/TheAlgorithms/Python/pull/11532
#
# Please mention me (@Ramy-Badr-Ahmed) in any issue or pull request
# addressing bugs/corrections to this file.
# Thank you!

fromdata_structures.kd_tree.kd_nodeimportKDNode


defbuild_kdtree(points: list[list[float]], depth: int=0) ->KDNode|None:
"""
 Builds a KD-Tree from a list of points.

 Args:
 points: The list of points to build the KD-Tree from.
 depth: The current depth in the tree
 (used to determine axis for splitting).

 Returns:
 The root node of the KD-Tree,
 or None if no points are provided.
 """
ifnotpoints:
returnNone

k=len(points[0]) # Dimensionality of the points
axis=depth%k

# Sort point list and choose median as pivot element
points.sort(key=lambdapoint: point[axis])
median_idx=len(points) //2

# Create node and construct subtrees
left_points=points[:median_idx]
right_points=points[median_idx+1 :]

returnKDNode(
point=points[median_idx],
left=build_kdtree(left_points, depth+1),
right=build_kdtree(right_points, depth+1),
 )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
# Created by: Ramy-Badr-Ahmed (https://github.com/Ramy-Badr-Ahmed)
# in Pull Request: #11532
# https://github.com/TheAlgorithms/Python/pull/11532
#
# Please mention me (@Ramy-Badr-Ahmed) in any issue or pull request
# addressing bugs/corrections to this file.
# Thank you!

fromdata_structures.kd_tree.kd_nodeimportKDNode


defbuild_kdtree(points: list[list[float]], depth: int=0) ->KDNode|None:
"""
 Builds a KD-Tree from a list of points.

 Args:
 points: The list of points to build the KD-Tree from.
 depth: The current depth in the tree
 (used to determine axis for splitting).

 Returns:
 The root node of the KD-Tree,
 or None if no points are provided.
 """
ifnotpoints:
returnNone

k=len(points[0]) # Dimensionality of the points
axis=depth%k

# Sort point list and choose median as pivot element
points.sort(key=lambdapoint: point[axis])
median_idx=len(points) //2

# Create node and construct subtrees
left_points=points[:median_idx]
right_points=points[median_idx+1 :]

returnKDNode(
point=points[median_idx],
left=build_kdtree(left_points, depth+1),
right=build_kdtree(right_points, depth+1),
 )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
# Created by: Ramy-Badr-Ahmed (https://github.com/Ramy-Badr-Ahmed)
# in Pull Request: #11532
# https://github.com/TheAlgorithms/Python/pull/11532
#
# Please mention me (@Ramy-Badr-Ahmed) in any issue or pull request
# addressing bugs/corrections to this file.
# Thank you!

fromdata_structures.kd_tree.kd_nodeimportKDNode


defbuild_kdtree(points: list[list[float]], depth: int=0) ->KDNode|None:
"""
 Builds a KD-Tree from a list of points.

 Args:
 points: The list of points to build the KD-Tree from.
 depth: The current depth in the tree
 (used to determine axis for splitting).

 Returns:
 The root node of the KD-Tree,
 or None if no points are provided.
 """
ifnotpoints:
returnNone

k=len(points[0]) # Dimensionality of the points
axis=depth%k

# Sort point list and choose median as pivot element
points.sort(key=lambdapoint: point[axis])
median_idx=len(points) //2

# Create node and construct subtrees
left_points=points[:median_idx]
right_points=points[median_idx+1 :]

returnKDNode(
point=points[median_idx],
left=build_kdtree(left_points, depth+1),
right=build_kdtree(right_points, depth+1),
 )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
# Created by: Ramy-Badr-Ahmed (https://github.com/Ramy-Badr-Ahmed)
# in Pull Request: #11532
# https://github.com/TheAlgorithms/Python/pull/11532
#
# Please mention me (@Ramy-Badr-Ahmed) in any issue or pull request
# addressing bugs/corrections to this file.
# Thank you!

fromdata_structures.kd_tree.kd_nodeimportKDNode


defbuild_kdtree(points: list[list[float]], depth: int=0) ->KDNode|None:
"""
 Builds a KD-Tree from a list of points.

 Args:
 points: The list of points to build the KD-Tree from.
 depth: The current depth in the tree
 (used to determine axis for splitting).

 Returns:
 The root node of the KD-Tree,
 or None if no points are provided.
 """
ifnotpoints:
returnNone

k=len(points[0]) # Dimensionality of the points
axis=depth%k

# Sort point list and choose median as pivot element
points.sort(key=lambdapoint: point[axis])
median_idx=len(points) //2

# Create node and construct subtrees
left_points=points[:median_idx]
right_points=points[median_idx+1 :]

returnKDNode(
point=points[median_idx],
left=build_kdtree(left_points, depth+1),
right=build_kdtree(right_points, depth+1),
 )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
# Created by: Ramy-Badr-Ahmed (https://github.com/Ramy-Badr-Ahmed)
# in Pull Request: #11532
# https://github.com/TheAlgorithms/Python/pull/11532
#
# Please mention me (@Ramy-Badr-Ahmed) in any issue or pull request
# addressing bugs/corrections to this file.
# Thank you!

fromdata_structures.kd_tree.kd_nodeimportKDNode


defbuild_kdtree(points: list[list[float]], depth: int=0) ->KDNode|None:
"""
 Builds a KD-Tree from a list of points.

 Args:
 points: The list of points to build the KD-Tree from.
 depth: The current depth in the tree
 (used to determine axis for splitting).

 Returns:
 The root node of the KD-Tree,
 or None if no points are provided.
 """
ifnotpoints:
returnNone

k=len(points[0]) # Dimensionality of the points
axis=depth%k

# Sort point list and choose median as pivot element
points.sort(key=lambdapoint: point[axis])
median_idx=len(points) //2

# Create node and construct subtrees
left_points=points[:median_idx]
right_points=points[median_idx+1 :]

returnKDNode(
point=points[median_idx],
left=build_kdtree(left_points, depth+1),
right=build_kdtree(right_points, depth+1),
 )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
# Created by: Ramy-Badr-Ahmed (https://github.com/Ramy-Badr-Ahmed)
# in Pull Request: #11532
# https://github.com/TheAlgorithms/Python/pull/11532
#
# Please mention me (@Ramy-Badr-Ahmed) in any issue or pull request
# addressing bugs/corrections to this file.
# Thank you!

fromdata_structures.kd_tree.kd_nodeimportKDNode


defbuild_kdtree(points: list[list[float]], depth: int=0) ->KDNode|None:
"""
 Builds a KD-Tree from a list of points.

 Args:
 points: The list of points to build the KD-Tree from.
 depth: The current depth in the tree
 (used to determine axis for splitting).

 Returns:
 The root node of the KD-Tree,
 or None if no points are provided.
 """
ifnotpoints:
returnNone

k=len(points[0]) # Dimensionality of the points
axis=depth%k

# Sort point list and choose median as pivot element
points.sort(key=lambdapoint: point[axis])
median_idx=len(points) //2

# Create node and construct subtrees
left_points=points[:median_idx]
right_points=points[median_idx+1 :]

returnKDNode(
point=points[median_idx],
left=build_kdtree(left_points, depth+1),
right=build_kdtree(right_points, depth+1),
 )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
# Created by: Ramy-Badr-Ahmed (https://github.com/Ramy-Badr-Ahmed)
# in Pull Request: #11532
# https://github.com/TheAlgorithms/Python/pull/11532
#
# Please mention me (@Ramy-Badr-Ahmed) in any issue or pull request
# addressing bugs/corrections to this file.
# Thank you!

fromdata_structures.kd_tree.kd_nodeimportKDNode


defbuild_kdtree(points: list[list[float]], depth: int=0) ->KDNode|None:
"""
 Builds a KD-Tree from a list of points.

 Args:
 points: The list of points to build the KD-Tree from.
 depth: The current depth in the tree
 (used to determine axis for splitting).

 Returns:
 The root node of the KD-Tree,
 or None if no points are provided.
 """
ifnotpoints:
returnNone

k=len(points[0]) # Dimensionality of the points
axis=depth%k

# Sort point list and choose median as pivot element
points.sort(key=lambdapoint: point[axis])
median_idx=len(points) //2

# Create node and construct subtrees
left_points=points[:median_idx]
right_points=points[median_idx+1 :]

returnKDNode(
point=points[median_idx],
left=build_kdtree(left_points, depth+1),
right=build_kdtree(right_points, depth+1),
 )