Great Deal! Get Instant \$25 FREE in Account on First Order + 10% Cashback on Every Order Order Now

# This is an individual coding assignment. The objective is to implement the R-tree. Each submission will be graded based on correctness. The rest of the document explains the details. How Your...

## Solution

Kshitij answered on Oct 13 2021
Functions.txt
import pandas as pd
import sys
import math
B = 4
class NodeManager(object):
def __init__(self):
self.id = 0
self.child_nodes = []
self.data_points = []
self.parent = None
self.MBR = {
'x_min': -1,
'y_min': -1,
'x_max': -1,
'y_max': -1,
}
def calculate_perimeter(self):
return (self.MBR['x_max'] - self.MBR['x_min']) + (self.MBR['y_max'] - self.MBR['y_min'])
def check_underflow(self):
if self.check_leaf():
if self.data_points.__len__() < math.ceil(B / 2):
return True
else:
return False
else:
if self.child_nodes.__len__() < math.ceil(B / 2):
return True
else:
return False
def check_overflow(self):
if self.check_leaf():
if self.data_points.__len__() > B:
return True
else:
return False
else:
if self.child_nodes.__len__() > B:
return True
else:
return False
def check_root(self):
if self.parent is None:
return True
else:
return False
def check_leaf(self):
if self.child_nodes.__len__() == 0:
return True
else:
return False
def __init__(self):
pass
self.rt = RTree()
points = open(points_path, "r")
lines = lines[1:]
x = []
y = []
for i in range(len(lines)):
# for i in range(100):
x.append(int(lines[i].split()[1]))
y.append(int(lines[i].split()[2]))
points = pd.DataFrame({'x': x, 'y': y})
return points
query_points = open(queries_path, "r")
x_min = []
x_max = []
y_min = []
y_max = []
for i in range(len(query_coordinates)):
# for i in range(100):
x_min.append(int(query_coordinates[i].split()[0]))
x_max.append(int(query_coordinates[i].split()[1]))
y_min.append(int(query_coordinates[i].split()[2]))
y_max.append(int(query_coordinates[i].split()[3]))
queries = pd.DataFrame({'x_min': x_min, 'x_max': x_max, 'y_min': y_min, 'y_max': y_max, })
return queries

class RTree(object):
def __init__(self):
self.root = NodeManager()
def query(self, node, query):
num = 0
if node.check_leaf():
for point in node.data_points:
if self.is_covered(point, query):
num = num + 1
return num
else:
for child in node.child_nodes:
if self.is_intersect(child, query):
num = num + self.query(child, query)
return num
def is_intersect(self, node, query):
center1_x = (node.MBR['x_max'] + node.MBR['x_min']) / 2
center1_y = (node.MBR['y_max'] + node.MBR['y_min']) / 2
length1 = node.MBR['x_max'] - node.MBR['x_min']
width1 = node.MBR['y_max'] - node.MBR['y_min']
center2_x = (query['x_max'] + query['x_min']) / 2
center2_y = (query['y_max'] + query['y_min']) / 2
length2 = query['x_max'] - query['x_min']
width2 = query['y_max'] - query['y_min']
if abs(center1_x - center2_x) <= length1 / 2 + length2 / 2 and\
abs(center1_y - center2_y) <= width1 / 2 + width2 / 2:
return True
else:
return False
def is_covered(self, point, query):
x_min, x_max, y_min, y_max = query['x_min'], query['x_max'], query['y_min'], query['y_max']
if x_min <= point['x'] <= x_max and y_min <= point['y'] <= y_max:
return True
else:
return False
def insert(self, u, p):
if u.check_leaf():
if u.check_overflow():
self.handle_overflow(u)
else:
v = self.choose_subtree(u, p)
self.insert(v, p)
self.update_m
(v)
def choose_subtree(self, u, p):
if u.check_leaf():
return u
else:
min_increase = sys.maxsize
best_child = None
for child in u.child_nodes:
if min_increase >...
SOLUTION.PDF