Пересекающиеся выровненные квадраты (горизонт)

Question

Я программирую что-то похожее на проблему слияния горизонта. В моем случае я должен пересечь горизонты и не могу найти, что не так с моим кодом, он возвращает неправильные точки. Я использую алгоритм «разделяй и властвуй».

(_ Точка - это именованный кортеж, который содержит x (где изменяется высота) и ah (высота)) (_points - это список, содержащий все точки, которые образуют линия горизонта)

Один из примеров ввода может быть:

p1 = Skyline([(1,11,5),(2,6,7),(3,13,15)])
p2 = Skyline([(12,7,16),(2,6,7),(14,3,25),(19,18,22)])

И вывод p1 * p2 должен быть:

[Point(x=2, h=6), Point(x=7, h=0), Point(x=12, h=7), Point(x=15,h=0)]

Вот код:

def __mul__(self,sky1):
        """Returns a list of points resulting from the intersection of two skylines"""
        sky = []
        sky.extend(self._points)
        sky.extend(sky1._points)
        sorted(sky, key=attrgetter('x'))
        print("Skyline: points =", self._intersect(sky))
        return self._intersect(sky)


    def _intersect(self,sky):
        sky.sort(key=lambda tup: tup[0])
        """From a list of tuples, prints a list of points which gives the x and the h, when the h changes"""

        if sky==[]:
            return []
        if len(sky)==1:
            if isinstance(sky[0], self._Point):
                return [self._Point(x = sky[0][0], h = sky[0][1])]
            if isinstance(sky[0], tuple):
                return [self._Point(x = sky[0][0], h = sky[0][1]), self._Point(x = sky[0][2], h= 0)]

        mid=(len(sky)-1)//2
        left=self._intersect(sky[0:mid+1])
        right=self._intersect(sky[mid+1:])
        return self._inter(left,right)
 def _inter(self, right, left):
        #altures
        h1, h2 = 0, 0
        i, j = 0, 0
        _points = []
        self._points = _points
        formerh = 0

        while i < len(left) and j < len(right):
            #the building in the first group starts before
            if left[i][0] < right[j][0]:
                h2 = right[j][1]
                h1 = left[i][1]
                inici = right[j][0]
                j += 1
            #the other way round
            elif right[j][0] < left[i][0]:
                h1 = left[i][1]
                h2 = right[j][1]
                inici = left[i][0]
                i += 1
            #they both start at once
            else:
                h1 = left[i][1]
                h2 = right[j][1]
                inici = right[j][0]
                i += 1
                j += 1
            #if the new height is different from the former one, we add the point to our list
            if min(h1, h2) != formerh:
                formerh = min(h1,h2)
                self._points.append(self._Point(x = inici, h = min(h1, h2)))
        return self._points