Create a data structure program that does the following... Implement a spatial i

Question

Create a data structure program that does the following...

Implement a spatial index using quadtrees. Use the quadtrees to find the nearest point to a given point. You can do a brute force approach and compare it with performance of quadtrees algorithm.

Main aim is to find the nearest point to a given point.

Data structure that will be used is quadtrees. Quadtrees will keep a track of the cost to different nodes from the given node.

User will need to provide the nodes and cost of travelling to other nodes.

Explanation / Answer

program quadtree_map = {
'a': {(0, 0): (0, 'd'), (0, 1): (1, 'a'), (1, 0): (3, 'b'), (1, 1): (2, 'a')},
'b': {(0, 0): (2, 'b'), (0, 1): (1, 'b'), (1, 0): (3, 'a'), (1, 1): (0, 'c')},
'c': {(0, 0): (2, 'c'), (0, 1): (3, 'd'), (1, 0): (1, 'c'), (1, 1): (0, 'b')},
'd': {(0, 0): (0, 'a'), (0, 1): (3, 'c'), (1, 0): (1, 'd'), (1, 1): (2, 'd')},
}
def point_to_quadtree(x, y, order=16):
current_square = 'a'
position = 0
for i in range(order - 1, -1, -1):
position <<= 2
quad_x = 1 if x & (1 << i) else 0
quad_y = 1 if y & (1 << i) else 0
quad_position, current_square = hilbert_map[current_square][(quad_x, quad_y)]
position |= quad_position
return position
>>> point_to_quadtree(5,2,3)
55
>>> points = [(x, y) for x in range(8) for y in range(8)]
>>> sorted_points = sorted(points, key=lambda k: point_to_hilbert(k[0], k[1], 3))
>>> print ' '.join('%s,%s' % x for x in sorted_points)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.