Pascal Lais
1dabb12a85
All checks were successful
continuous-integration/drone/push Build is passing
467 lines
21 KiB
Python
467 lines
21 KiB
Python
#!/usr/bin/python3
|
|
|
|
"""The sweep module defines a base class sweep for various sweep algorithms. It also contains a
|
|
child-class for each individual algorithm."""
|
|
|
|
import copy
|
|
|
|
import linesegment
|
|
import point
|
|
|
|
class Algorithm():
|
|
|
|
"The Algorithm class is the base class for each individual algorithm"
|
|
|
|
def __init__(self):
|
|
self._input = None # The input values
|
|
self._result = {} # The result of the sweep
|
|
self._ready = False # If the algorithm is ready to be executed
|
|
self._running = False # If the algorithm is currently running
|
|
self._section = "start" # A string that names the current section of the algorithm
|
|
self._num_steps = {} # The number of steps that were needed to solve the problem
|
|
|
|
def start(self):
|
|
"""Start the performing the algorithm. Return True if it was successful"""
|
|
if not self._ready:
|
|
print("Error: Sweep is not yet ready to be performed")
|
|
return False
|
|
self._running = True
|
|
return True
|
|
|
|
def step(self):
|
|
"""Perform a single step of the algorithm."""
|
|
if self._section:
|
|
if self._section in self._num_steps:
|
|
self._num_steps[self._section] += 1
|
|
else:
|
|
self._num_steps[self._section] = 1
|
|
|
|
def run(self):
|
|
"""Execute the sweep. Returns the result dict."""
|
|
if not self.start():
|
|
return False
|
|
while self._running:
|
|
self.step()
|
|
return self._result
|
|
|
|
def is_running(self):
|
|
"""Return if the algorithm is running."""
|
|
return self._running
|
|
def get_section(self):
|
|
"""Return the current section name of the algorithm."""
|
|
return self._section
|
|
def get_result(self):
|
|
"""Return the result of the algorithm."""
|
|
return self._result
|
|
|
|
def draw(self, canvas, width, height, max_x, max_y):
|
|
"""Dummy for draw method"""
|
|
|
|
class NearestNeighborsSweep(Algorithm):
|
|
|
|
"""Calculate the pair of points inside a set, that have the minimal distance between each
|
|
other inside this set"""
|
|
|
|
def __init__(self, point_set=None):
|
|
super().__init__()
|
|
if isinstance(point_set, list):
|
|
for pnt in point_set:
|
|
if not isinstance(pnt, point.Point):
|
|
raise Exception(self, "Inputs have to be of type point.Point!")
|
|
self._input = copy.deepcopy(point_set)
|
|
self._ready = True
|
|
elif point_set is not None:
|
|
raise Exception(self, "Wrong input type for point_set")
|
|
self._sss = {} # The sweep state structure
|
|
self._es = [] # The event queue
|
|
self._result = {"success": False, \
|
|
"distance": None, \
|
|
"points": [None, None]}
|
|
|
|
def start(self):
|
|
"""Start the performing the algorithm. Return True if it was successful"""
|
|
if not super().start():
|
|
return False
|
|
|
|
self._result["success"] = False
|
|
self._sss = {"mindist": None, \
|
|
"points": []}
|
|
# Populate event structure
|
|
self._es = copy.deepcopy(self._input)
|
|
# Sort the input elements
|
|
self._num_steps["sort"] = point.sort_set(self._es)
|
|
return True
|
|
|
|
def step(self):
|
|
"""Perform a single step of the algorithm."""
|
|
if not self._running:
|
|
return
|
|
|
|
self._section = "sweep"
|
|
|
|
event = self._es.pop(0)
|
|
|
|
if self._sss["mindist"] is not None:
|
|
while len(self._sss["points"]) > 0 and \
|
|
self._sss["points"][0].get_x() <= (event.get_x() - self._sss["mindist"]):
|
|
del self._sss["points"][0]
|
|
for pnt in self._sss["points"]:
|
|
if self._sss["mindist"] is None:
|
|
self._sss["mindist"] = linesegment.LineSegment(pnt, event).get_length()
|
|
self._result["points"][0] = pnt
|
|
self._result["points"][1] = event
|
|
elif (event.get_y() - self._sss["mindist"]) < \
|
|
pnt.get_y() < (event.get_y() + self._sss["mindist"]):
|
|
distance = linesegment.LineSegment(pnt, event).get_length()
|
|
if self._sss["mindist"] > distance > 0:
|
|
self._sss["mindist"] = distance
|
|
self._result["points"][0] = pnt
|
|
self._result["points"][1] = event
|
|
super().step()
|
|
|
|
self._sss["points"].append(event)
|
|
|
|
if len(self._es) == 0:
|
|
self._result["success"] = True
|
|
self._result["distance"] = self._sss["mindist"]
|
|
self._running = False
|
|
|
|
def get_result_string(self, print_result=False):
|
|
"""Pack the result into a string."""
|
|
result_string = ""
|
|
if self._running:
|
|
result_string = "Sweep is still running."
|
|
elif not self._result["success"]:
|
|
result_string = "Sweep was not successful."
|
|
else:
|
|
result_string = "Sweep successfully completed\n"
|
|
result_string += " Summary:\n"
|
|
result_string += " Number of Inputs:" + str(len(self._input)) + "\n"
|
|
result_string += " Inputs: ["
|
|
for i, pnt in enumerate(self._input):
|
|
if i:
|
|
result_string += ","
|
|
result_string += str(pnt)
|
|
result_string += "]\n"
|
|
result_string += " Nearest Neighbors: "
|
|
result_string += str(linesegment.LineSegment(self._result["points"][0], \
|
|
self._result["points"][1]))
|
|
result_string += "\n"
|
|
result_string += " Distance: " + str(self._result["distance"]) + "\n"
|
|
result_string += " Number of steps:\n"
|
|
result_string += " Sort:" + str(self._num_steps["sort"]) +"\n"
|
|
result_string += " Sweep:" + str(self._num_steps["sweep"]) +"\n"
|
|
|
|
if print_result:
|
|
print(result_string)
|
|
return result_string
|
|
|
|
def draw(self, canvas, width, height, max_x, max_y):
|
|
"""Draw the algorithm state on a canvas"""
|
|
canvas.delete("all")
|
|
if self._running:
|
|
for pnt in self._input:
|
|
if len(self._es) > 0 and pnt == self._es[0]:
|
|
cur_x, cur_y = self._es[0].draw(canvas, width, height, max_x, max_y, "#0000FF")
|
|
canvas.create_line(cur_x, 0, cur_x, height, fill="#0000FF")
|
|
if self._sss["mindist"]:
|
|
canvas.create_line(cur_x - (self._sss["mindist"] * width / max_x), 0, \
|
|
cur_x - (self._sss["mindist"] * width / max_x), height, fill="#0000FF")
|
|
canvas.create_line(cur_x - (self._sss["mindist"] * width / max_x), \
|
|
cur_y - (self._sss["mindist"] * height / max_y), \
|
|
cur_x, cur_y - (self._sss["mindist"] * height / max_y), fill="#0000FF")
|
|
canvas.create_line(cur_x - (self._sss["mindist"] * width / max_x), \
|
|
cur_y + (self._sss["mindist"] * height / max_y), \
|
|
cur_x, cur_y + (self._sss["mindist"] * height / max_y), fill="#0000FF")
|
|
else:
|
|
canvas.create_line(0, 0, 0, max_y, fill="#0000FF")
|
|
if pnt in self._result["points"]:
|
|
pnt.draw(canvas, width, height, max_x, max_y, "#FF0000")
|
|
else:
|
|
pnt.draw(canvas, width, height, max_x, max_y)
|
|
if self._result["points"][0]:
|
|
linesegment.LineSegment( \
|
|
self._result["points"][0], self._result["points"][1] \
|
|
).draw(canvas, width, height, max_x, max_y, "#FF0000")
|
|
else:
|
|
for pnt in self._input:
|
|
if pnt in self._result["points"]:
|
|
pnt.draw(canvas, width, height, max_x, max_y, "#FF3333")
|
|
else:
|
|
pnt.draw(canvas, width, height, max_x, max_y, "#222222")
|
|
if self._result["points"][0]:
|
|
linesegment.LineSegment( \
|
|
self._result["points"][0], self._result["points"][1] \
|
|
).draw(canvas, width, height, max_x, max_y, "#FF0000")
|
|
|
|
class ConvexHullIncremental(Algorithm):
|
|
|
|
"""This algorithm calculates the convex hull for a set of points"""
|
|
|
|
def __init__(self, point_set=None):
|
|
super().__init__()
|
|
if isinstance(point_set, list):
|
|
for pnt in point_set:
|
|
if not isinstance(pnt, point.Point):
|
|
raise Exception(self, "Inputs have to be of type point.Point!")
|
|
self._input = copy.deepcopy(point_set)
|
|
self._ready = True
|
|
elif point_set is not None:
|
|
raise Exception(self, "Wrong input type for point_set")
|
|
self._sss = {} # The sweep state structure
|
|
self._es = [] # The event queue
|
|
self._result = {"success": False, \
|
|
"lt": [], \
|
|
"lb": [], \
|
|
"rt": [], \
|
|
"rb": [], \
|
|
"hull": []}
|
|
def start(self):
|
|
"""Start the performing the algorithm. Return True if it was successful"""
|
|
if not super().start():
|
|
return False
|
|
|
|
self._result["success"] = False
|
|
self._sss = {"max": None, \
|
|
"min": None, \
|
|
"lt": [], \
|
|
"lb": [], \
|
|
"rt": [], \
|
|
"rb": []}
|
|
# Populate event structure
|
|
self._es = copy.deepcopy(self._input)
|
|
# Sort the input elements
|
|
self._num_steps["sort"] = point.sort_set(self._es)
|
|
self._section = "sweep-left-to-right"
|
|
return True
|
|
def step(self):
|
|
"""Perform a single step of the algorithm."""
|
|
if not self._running:
|
|
return
|
|
|
|
if self._section == "sweep-left-to-right":
|
|
event = self._es.pop(0)
|
|
if self._sss["min"] is None or self._sss["max"] is None:
|
|
self._sss["min"] = event
|
|
self._result["lb"].append(event)
|
|
self._sss["max"] = event
|
|
self._result["lt"].append(event)
|
|
elif event.get_y() < self._sss["min"].get_y():
|
|
self._result["lb"].append(event)
|
|
self._sss["min"] = event
|
|
elif event.get_y() > self._sss["max"].get_y():
|
|
self._result["lt"].append(event)
|
|
self._sss["max"] = event
|
|
|
|
super().step()
|
|
if len(self._es) == 0:
|
|
self._sss["min"] = None
|
|
self._sss["max"] = None
|
|
self._es = copy.deepcopy(self._input)
|
|
self._num_steps["sort"] = point.sort_set(self._es)
|
|
self._section = "sweep-right-to-left"
|
|
|
|
elif self._section == "sweep-right-to-left":
|
|
event = self._es.pop(-1)
|
|
if self._sss["min"] is None or self._sss["max"] is None:
|
|
self._sss["min"] = event
|
|
self._result["rb"].append(event)
|
|
self._sss["max"] = event
|
|
self._result["rt"].append(event)
|
|
elif event.get_y() < self._sss["min"].get_y():
|
|
self._result["rb"].append(event)
|
|
self._sss["min"] = event
|
|
elif event.get_y() > self._sss["max"].get_y():
|
|
self._result["rt"].append(event)
|
|
self._sss["max"] = event
|
|
|
|
super().step()
|
|
if len(self._es) == 0:
|
|
self._es = copy.deepcopy(self._result["lt"])
|
|
# self._result["lt"] = []
|
|
self._section = "sweep-left-to-top"
|
|
|
|
elif self._section == "sweep-left-to-top":
|
|
event = self._es.pop(0)
|
|
self._sss["lt"].append(event)
|
|
start_idx = len(self._sss["lt"]) - 1
|
|
for i in range(start_idx, 0, -1):
|
|
if len(self._es) > 0:
|
|
slope_a = linesegment.LineSegment( \
|
|
self._sss["lt"][i-1], self._sss["lt"][i]).get_slope()
|
|
slope_b = linesegment.LineSegment(self._sss["lt"][i], self._es[0]).get_slope()
|
|
super().step()
|
|
if slope_a < slope_b:
|
|
del self._sss["lt"][i]
|
|
else:
|
|
break
|
|
else:
|
|
break
|
|
if len(self._es) == 0:
|
|
self._result["lt"] = copy.deepcopy(self._sss["lt"])
|
|
self._es = copy.deepcopy(self._result["lb"])
|
|
# self._result["lb"] = []
|
|
self._section = "sweep-left-to-bottom"
|
|
|
|
elif self._section == "sweep-left-to-bottom":
|
|
event = self._es.pop(0)
|
|
self._sss["lb"].append(event)
|
|
start_idx = len(self._sss["lb"]) - 1
|
|
for i in range(start_idx, 0, -1):
|
|
if len(self._es) > 0:
|
|
slope_a = linesegment.LineSegment( \
|
|
self._sss["lb"][i-1], self._sss["lb"][i]).get_slope()
|
|
slope_b = linesegment.LineSegment(self._sss["lb"][i], self._es[0]).get_slope()
|
|
super().step()
|
|
if slope_a > slope_b:
|
|
del self._sss["lb"][i]
|
|
else:
|
|
break
|
|
else:
|
|
break
|
|
if len(self._es) == 0:
|
|
self._result["lb"] = copy.deepcopy(self._sss["lb"])
|
|
self._es = copy.deepcopy(self._result["rt"])
|
|
# self._result["rt"] = []
|
|
self._section = "sweep-right-to-top"
|
|
|
|
elif self._section == "sweep-right-to-top":
|
|
event = self._es.pop(0)
|
|
self._sss["rt"].append(event)
|
|
start_idx = len(self._sss["rt"]) - 1
|
|
for i in range(start_idx, 0, -1):
|
|
if len(self._es) > 0:
|
|
slope_a = linesegment.LineSegment( \
|
|
self._sss["rt"][i-1], self._sss["rt"][i]).get_slope()
|
|
slope_b = linesegment.LineSegment(self._sss["rt"][i], self._es[0]).get_slope()
|
|
super().step()
|
|
if slope_a > slope_b:
|
|
del self._sss["rt"][i]
|
|
else:
|
|
break
|
|
else:
|
|
break
|
|
if len(self._es) == 0:
|
|
self._result["rt"] = copy.deepcopy(self._sss["rt"])
|
|
self._es = copy.deepcopy(self._result["rb"])
|
|
# self._result["rb"] = []
|
|
self._section = "sweep-right-to-bottom"
|
|
|
|
elif self._section == "sweep-right-to-bottom":
|
|
event = self._es.pop(0)
|
|
self._sss["rb"].append(event)
|
|
start_idx = len(self._sss["rb"]) - 1
|
|
for i in range(start_idx, 0, -1):
|
|
if len(self._es) > 0:
|
|
slope_a = linesegment.LineSegment( \
|
|
self._sss["rb"][i-1], self._sss["rb"][i]).get_slope()
|
|
slope_b = linesegment.LineSegment(self._sss["rb"][i], self._es[0]).get_slope()
|
|
super().step()
|
|
if slope_a < slope_b:
|
|
del self._sss["rb"][i]
|
|
else:
|
|
break
|
|
else:
|
|
break
|
|
if len(self._es) == 0:
|
|
self._result["rb"] = copy.deepcopy(self._sss["rb"])
|
|
self._section = "report-hull"
|
|
|
|
elif self._section == "report-hull":
|
|
for i in range(len(self._result["lb"]) - 1):
|
|
self._result["hull"].append(self._result["lb"][i])
|
|
for i in range(len(self._result["rb"]) - 1, 0, -1):
|
|
self._result["hull"].append(self._result["rb"][i])
|
|
for i in range(len(self._result["rt"]) - 1):
|
|
self._result["hull"].append(self._result["rt"][i])
|
|
for i in range(len(self._result["lt"]) - 1, 0, -1):
|
|
self._result["hull"].append(self._result["lt"][i])
|
|
self._result["success"] = True
|
|
self._running = False
|
|
def draw(self, canvas, width, height, max_x, max_y):
|
|
"""Draw the algorithms state on the canvas."""
|
|
canvas.delete("all")
|
|
if self._running:
|
|
for i in range(len(self._result["lt"]) - 1):
|
|
linesegment.LineSegment(self._result["lt"][i], self._result["lt"][i+1])\
|
|
.draw(canvas, width, height, max_x, max_y, "#000000")
|
|
for i in range(len(self._result["lb"]) - 1):
|
|
linesegment.LineSegment(self._result["lb"][i], self._result["lb"][i+1])\
|
|
.draw(canvas, width, height, max_x, max_y, "#000000")
|
|
for i in range(len(self._result["rt"]) - 1):
|
|
linesegment.LineSegment(self._result["rt"][i], self._result["rt"][i+1])\
|
|
.draw(canvas, width, height, max_x, max_y, "#000000")
|
|
for i in range(len(self._result["rb"]) - 1):
|
|
linesegment.LineSegment(self._result["rb"][i], self._result["rb"][i+1])\
|
|
.draw(canvas, width, height, max_x, max_y, "#000000")
|
|
if self._section == "sweep-left-to-right" or \
|
|
self._section == "sweep-right-to-left":
|
|
if len(self._es) > 0:
|
|
if self._section == "sweep-left-to-right":
|
|
canvas.create_line(self._es[0].get_x() * width / max_x, 0, \
|
|
self._es[0].get_x() * width / max_x, height, fill="#0000FF")
|
|
else:
|
|
canvas.create_line(self._es[-1].get_x() * width / max_x, 0, \
|
|
self._es[-1].get_x() * width / max_x, height, fill="#0000FF")
|
|
for pnt in self._input:
|
|
if pnt in self._result["lt"] or \
|
|
pnt in self._result["lb"] or \
|
|
pnt in self._result["rt"] or \
|
|
pnt in self._result["rb"]:
|
|
pnt.draw(canvas, width, height, max_x, max_y, "#FF0000")
|
|
elif pnt in self._es:
|
|
pnt.draw(canvas, width, height, max_x, max_y, "#000000")
|
|
else:
|
|
pnt.draw(canvas, width, height, max_x, max_y, "#777777")
|
|
elif self._section == "sweep-left-to-top" or \
|
|
self._section == "sweep-left-to-bottom" or \
|
|
self._section == "sweep-right-to-top" or \
|
|
self._section == "sweep-right-to-bottom":
|
|
if len(self._es) > 0:
|
|
canvas.create_line(self._es[0].get_x() * width / max_x, 0, \
|
|
self._es[0].get_x() * width / max_x, height, fill="#0000FF")
|
|
for pnt in self._input:
|
|
if pnt in self._es:
|
|
pnt.draw(canvas, width, height, max_x, max_y, "#FF0000")
|
|
elif self._section == "sweep-left-to-top" and pnt in self._sss["lt"] or \
|
|
self._section == "sweep-left-to-bottom" and pnt in self._sss["lb"] or \
|
|
self._section == "sweep-right-to-top" and pnt in self._sss["rt"] or \
|
|
self._section == "sweep-right-to-bottom" and pnt in self._sss["rb"]:
|
|
pnt.draw(canvas, width, height, max_x, max_y, "#000000")
|
|
# elif pnt in self._result["lt"] or \
|
|
# pnt in self._result["lb"] or \
|
|
# pnt in self._result["rt"] or \
|
|
# pnt in self._result["rb"]:
|
|
# pnt.draw(canvas, width, height, max_x, max_y, "#000000")
|
|
else:
|
|
pnt.draw(canvas, width, height, max_x, max_y, "#777777")
|
|
if self._section == "sweep-left-to-top":
|
|
for i in range(len(self._sss["lt"]) - 1):
|
|
linesegment.LineSegment(self._sss["lt"][i], self._sss["lt"][i+1])\
|
|
.draw(canvas, width, height, max_x, max_y, "#FF0000")
|
|
elif self._section == "sweep-left-to-bottom":
|
|
for i in range(len(self._sss["lb"]) - 1):
|
|
linesegment.LineSegment(self._sss["lb"][i], self._sss["lb"][i+1])\
|
|
.draw(canvas, width, height, max_x, max_y, "#FF0000")
|
|
elif self._section == "sweep-right-to-top":
|
|
for i in range(len(self._sss["rt"]) - 1):
|
|
linesegment.LineSegment(self._sss["rt"][i], self._sss["rt"][i+1])\
|
|
.draw(canvas, width, height, max_x, max_y, "#FF0000")
|
|
elif self._section == "sweep-right-to-bottom":
|
|
for i in range(len(self._sss["rb"]) - 1):
|
|
linesegment.LineSegment(self._sss["rb"][i], self._sss["rb"][i+1])\
|
|
.draw(canvas, width, height, max_x, max_y, "#FF0000")
|
|
else:
|
|
for i in range(len(self._result["hull"]) - 1):
|
|
linesegment.LineSegment( \
|
|
self._result["hull"][i], self._result["hull"][i+1]) \
|
|
.draw(canvas, width, height, max_x, max_y, "#000000")
|
|
linesegment.LineSegment( \
|
|
self._result["hull"][-1], self._result["hull"][0]) \
|
|
.draw(canvas, width, height, max_x, max_y, "#000000")
|
|
for pnt in self._input:
|
|
if pnt in self._result["hull"]:
|
|
pnt.draw(canvas, width, height, max_x, max_y, "#000000")
|
|
else:
|
|
pnt.draw(canvas, width, height, max_x, max_y, "#777777")
|