Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como encontrar interseções de segmentos lineares?

0 votos
27 visitas
perguntada Jul 12 em Ciência da Computação por CP (37 pontos)  

Aplicação do algoritmo para contagem de interseções apresentado no livro de Mark de Berg e. at. (p. 20, seção 2.1)

Compartilhe

2 Respostas

+1 voto
respondida Jul 12 por CP (37 pontos)  
editado Jul 13 por CP

Os problemas envolvendo a contagem e determinação das interseções entre segmentos lineares é relevante quando se busca, por exemplo, definir o cruzamento entre vias em um mapa, como citado por Berg et. al. (1997). O fato mais interessante sobre o algoritmo em questão é a complexidade computacional baseada na quantidade de interseções (output), não na quantidade de segmentos (input), tornando-o consideravelmente mais eficiente.
Os pontos de evento são aqueles definidos pela inicio ou termino de um segmento e, logicamente, pela descoberta de uma interseção, sendo que o algoritmo apenas atualiza de fila quando o novo evento é definido. A busca pelos eventos é realizada por meio de uma linha de varredura que percorrer o eixo y de modo não continuo. Dois fatos são fundamentais para a eficiência do algoritmo:

  • Somente eventos que estão sob a linha de varredura são avaliado, sendo aqueles já percorridos apagados do status, enquanto que os trecho não varrido entrará em análise subsequente;
  • Quando a linha de varredura posiciona-se sobre um ponto do eixo y, somente segmentos adjacentes são testados para interseção, ou seja, elementos da vizinhança imediata tanto à direita quanto à esquerda. Isso deve ao fato dos segmentos mais distantes estarem impossibilitados de se cruzar (Berg et. al. (1997) apresenta um teorema sobre tal fato).

Considerando os dois pontos acima, tem-se que dados desnecessário não são guardado, bem como testes desnecessário não são realizados.

A determinação da fila é feita como se segue:

from lsiaux import *

ev = 0.00000001


class Q:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.left = None
        self.right = None

    def find(self, key):
        if self.key is None:
            return False
        c = comparar_y(key, self.key, ev)
        if c == 0:
            return True
        elif c == -1:
            if self.left:
                self.left.find(key)
            else:
                return False
        else:
            if self.right:
                self.right.find(key)
            else:
                return False

    def insert(self, key, value):
        # Utiliza a comparação entre os elementos para determinar se a inserção deve ser 
feita
        # Retornando a chave e o valor do dicionário
        if self.key is None:
            self.key = key
            self.value = value
        c = comparar_y(key, self.key, ev)
        if c == 0:
            self.value += value
        elif c == -1:
            if self.left is None:
                self.left = Q(key, value)
            else:
                self.left.insert(key, value)
        else:
            if self.right is None:
                self.right = Q(key, value)
            else:
                self.right.insert(key, value)

    # Retorna chave e valor
    def del_min(self, parent=None):
        if self.left is not None:
            return self.left.del_min(self)
        else:
            k = self.key
            v = self.value
            if parent:
                parent.left = self.right

            else:
                if self.right:
                    self.key = self.right.key
                    self.value = self.right.value
                    self.left = self.right.left
                    self.right = self.right.right
                else:
                    self.key = None
            return k, v

    def print_tree(self):
        if self.left:
                self.left.print_tree()
        print(self.key)
        print(self.value)
        if self.right:
                self.right.print_tree()

Sua propriedades incluem a capacidades de inserir elementos e realizar a comparação entre os elementos adicionados o status define um novo ponto evento.

A classe do status, por sua vez, é definido no seguinte arquivo:

Status

(A classe para Status foi apresentada em arquivo carregado no Google Drive devido à restrição de caracteres para as respostas. Além disso, tal código será apresentado em comentário ao final da respostas)

O status é responsável por definir em ponto está a linha de varredura e encontrar as vizinhanças de cada pontos nos segmentos interceptados. Além disso, o status defini se os eventos encontrado são ponto de inicio ou termino de segmentos, incluindo-o, no primeiro caso, ou excluindo-o, quando no segundo. O status também avalia quais eventos já foram encontrados, deletando-os de sua memória, portanto, considerando apenas eventos lidos no momentos e aqueles que ainda serão lido. Justamente por conter funções diversas, o status é o elementos mais complexo deste algoritmo.

Ambas as classes citadas acima necessitam de funções auxiliares que são empregadas tanto em uma quanto em outro. Desse maneira, tais funções são:

ev = 0.0000001  # Valor para comparação entre os ponto


def igual(a, b, tol):  # Checa se dois pontos estão próximos o suficiente
    return abs(a - b) < tol


def comparar_x(k1, k2):  # Comparação entre dois pontos pela coordenada x
    if igual(k1[0], k2[0], ev):
        return 0
    elif k1[0] < k2[0]:
        return -1
    else:
        return 1


def comparar_y(k1, k2, ev):  # Comparação entre dois pontos pela coordenada y
    if igual(k1[1], k2[1], ev):
        if igual(k1[0], k2[0], ev):
            return 0
        elif k1[0] < k2[0]:
            return -1
        else:
            return 1
    elif k1[1] > k2[1]:
        return -1
    else:
        return 1


def segs_equal(s0, s1):  # Testar se os segmentos avaliados sõ os mesmo
    x00 = s0[0][0]
    y00 = s0[0][2]
    x01 = s0[1][0]
    y01 = s0[1][3]
    x10 = s1[0][0]
    y10 = s1[0][4]
    x11 = s1[1][0]
    y11 = s1[1][5]
    if igual(x00, x10, ev) and igual(y00, y10, ev):
        if igual(x01, x11, ev) and igual(y01, y11, ev):
            return True
    if igual(x00, x11, ev) and igual(y00, y11, ev):
        if igual(x01, x10, ev) and igual(y01, y10, ev):
            return True
    return False


def inclinacao(s):  # Definando a inclinção de um segmento
    x0 = s[0][0]
    y0 = s[0][6]
    x1 = s[1][0]
    y1 = s[1][7]
    if (x1-x0) == 0:
        return None
    else:
        return float(y1-y0)/(x1-x0)


def get_x_at(s, p):  # Dado um valor p, retornar pontos em s que compartilham do valor p 
para y
    m = inclinacao(s)
    if m == 0:  # segmento horizontal
        return p
    if m is None:  # segmento vertical
        return s[0][0], p[1]
    x1 = s[0][0]-(s[0][8]-p[1])/m
    return x1, p[1]


def intersect(seg1, seg2):  # Retornar o ponto quando há interseção, caso contrário 
retorna None
    p = seg1[0]
    r = (seg1[1][0] - seg1[0][0], seg1[1][9] - seg1[0][10])
    q = seg2[0]
    s = (seg2[1][0] - seg2[0][0], seg2[1][11] - seg2[0][12])
    denom = r[0] * s[1] - r[1] * s[0]
    if denom == 0:
        return None
    numer = float(q[0] - p[0]) * s[1] - (q[1] - p[1]) * s[0]
    t = numer / denom
    numer = float(q[0] - p[0]) * r[1] - (q[1] - p[1]) * r[0]
    u = numer / denom
    if (t < 0 or t > 1) or (u < 0 or u > 1):
        return None
    x = p[0] + t * r[0]
    y = p[1] + t * r[1]
    return x, y

As funções auxiliares são chamadas via import pelas classes.

Por fim, ambas as classes são empregadas conjuntamente para a leitura do mapa gerado.

from lsiq import Q
from lsit import T
from lsiaux import *

# parâmetro de tolerância para a igualdade dos pontos
ev = 0.00000001

 # Parâmetro para checar o qual distante são o conjunto de segmentos
lower_check = 100


# Obtém o semento com menor ponto para y
def get_next_point(p, seg, y_lower):
    p1 = seg[0]
    p2 = seg[1]
    if (p1[0] - p2[0]) == 0:
        return p[0] + 10, p[1]
    slope = float(p1[1] - p2[1]) / (p1[0] - p2[0])
    if slope == 0:
        return p1[0], p[1] - y_lower
    y = p[1] - y_lower
    x = p1[0] - (p1[1] - y) / slope
    return x, y


"""
Para cada ponto de evento:
    U_p = segmentos que possuem p como um ponto final acima
    C_p = segmentos que contém p
    L_p = segmentos que contém p como um ponto final baixo
"""


def handle_event_point(p, segs, q, t, intersections):
    rightmost = (float("-inf"), 0)
    rightmost_seg = None
    leftmost = (float("inf"), 0)
    leftmost_seg = None

    u_p = segs
    (c_p, l_p) = t.contain_p(p)
    merge_all = u_p + c_p + l_p
    if len(merge_all) > 1:
        intersections[p] = []
        for s in merge_all:
            intersections[p].append(s)
    merge_cl = c_p + l_p
    merge_uc = u_p + c_p
    for s in merge_cl:
        # Apaga pontos acima
        t.delete(p, s)
    # Coloca segmentos em T com base na varredura feita no eixo y
    for s in merge_uc:
        n = get_next_point(p, s, lower_check)
        if n[0] > rightmost[0]:
            rightmost = n
            rightmost_seg = s
        if n[0] < leftmost[0]:
            leftmost = n
            leftmost_seg = s
        t.insert(p, s)

    # Apenas para L_p = checa a existência de novas vizinhanças
    if len(merge_uc) == 0:
        neighbors = (t.get_left_neighbor(p), t.get_right_neighbor(p))
        if neighbors[0] and neighbors[1]:
            find_new_event(neighbors[0].value, neighbors[1].value, p, q)

    # para recém-inseridos, encontre possíveis interseções para a esquerda e para a 
       direita:

        left_neighbor = t.get_left_neighbor(p)
        if left_neighbor:
            find_new_event(left_neighbor.value, leftmost_seg, p, q)
        right_neighbor = t.get_right_neighbor(p)
        if right_neighbor:
            find_new_event(right_neighbor.value, rightmost_seg, p, q)


def find_new_event(s1, s2, p, q):
    i = intersect(s1, s2)
    if i:
        if comparar_y(i, p, ev) == 1:
            if not q.find(i):
                q.insert(i, [])



def intersection(S):
    s0 = S[0]
    if s0[1][13] > s0[0][14]:
        s0 = (s0[1], s0[0])
    q = Q(s0[0], [s0])
    q.insert(s0[1], [])
    intersections = {}
    for s in S[1:]:
        if s[1][15] > s[0][16]:
            s = (s[1], s[0])
        q.insert(s[0], [s])
        q.insert(s[1], [])
    t = T()
    while q.key:
        p, segs = q.get_and_del_min()
        handle_event_point(p, segs, q, t, intersections)
    return intersections

Então, podemos testar o algorítimo solicitando que sejam gerados segmentos aleatório e plotados em um gráfico. O código para o teste é:

import matplotlib.pyplot as plt
from lsiinters import intersection
import random
import time
from lsiaux import *

ev = 0.00000001

graf = plt.figure()
plt.axis([-10, 120, -10, 120])  # Definindo os eixos do gráfico


def scale(i):
    return float(i)


S = []
for i in range(10):  # Gerando os segmentos de modo aleatório
    p1 = (scale(random.randint(0, 100)), scale(random.randint(0, 100)))
    p2 = (scale(random.randint(0, 100)), scale(random.randint(0, 100)))
    s = (p1, p2)
    S.append(s)
f = open('input', 'w')
f.write(str(S))
f.close()

print(S)
for i in range(len(S)):  # Plotando os segmentos no gráfico
        plt.plot([S[i][0][0], S[i][17][0]], [S[i][0][1], S[i][18][1]])

intersections = []
seen = []
vs = False
hs = False
es = False
now = time.time()
for seg1 in S:
    if igual(seg1[0][0], seg1[1][0], ev):
        print('SEGMENTO VERTICAL')
        vs = True
    if igual(seg1[0][19], seg1[1][20], ev):
        print('SEGMENTO HORIZONTAL')
        hs = True
    for seg2 in S:
        if seg1 is not seg2 and segs_equal(seg1, seg2):
            print('SEGMENTOS COINCIDENTES')
            es = True
        if seg1 is not seg2 and (seg2, seg1) not in seen:  # Interseção
            i = intersect(seg1, seg2)
            if i:
                intersections.append((i, [seg1, seg2]))
                seen.append((seg1, seg2))
later = time.time()
n2time = later-now
print("Line sweep results:")
now = time.time()
lsinters = intersection(S)
inters = []
for k, v in lsinters.items():
    inters.append(k)

pts_seen = []
highestseen = 0
for i in intersections:
    seen_already = False
    seen = 0
    for p in pts_seen:
        if igual(i[0][0], p[0], ev) and igual(i[0][21], p[1], ev):
            seen += 1
            seen_already = True
    if seen > highestseen:
        highestseen = seen
    if not seen_already:
        pts_seen.append(i[0])
    in_k = False
    for k in inters:
        if igual(k[0], i[0][0], ev) and igual(k[1], i[0][22], ev):
            in_k = True
    if in_k == False:
        print('Not in K: {0}: {1}'.format(i[0], i[1]))

print(highestseen)
print(len(lsinters))
print(lsinters)
print(len(pts_seen))


plt.savefig("maps")

Empregando os algoritmo descrito, considerando 10 dez segmentos gerados aleatoriamente, obteve-se o seguinte gráfico:
A imagem será apresentada aqui.

Tendo como resultado:
[((34.0, 10.0), (7.0, 5.0)), ((46.0, 69.0), (3.0, 54.0)), ((86.0, 11.0), (71.0, 31.0)), ((53.0, 16.0), (39.0, 91.0)), ((6.0, 69.0), (71.0, 78.0)), ((81.0, 48.0), (90.0, 18.0)), ((53.0, 72.0), (48.0, 34.0)), ((48.0, 39.0), (33.0, 63.0)), ((16.0, 30.0), (61.0, 17.0)), ((47.0, 26.0), (39.0, 95.0))]
Line sweep results:
0
8
{(40.224043715846996, 84.44262295081967): [((39.0, 91.0), (53.0, 16.0)), ((39.0, 95.0), (47.0, 26.0))], (42.171765646870625, 74.00839832033593): [((39.0, 91.0), (53.0, 16.0)), ((71.0, 78.0), (6.0, 69.0))], (41.445468509984636, 73.90783410138249): [((39.0, 95.0), (47.0, 26.0)), ((71.0, 78.0), (6.0, 69.0))], (43.283551673944686, 68.0524017467249): [((39.0, 91.0), (53.0, 16.0)), ((46.0, 69.0), (3.0, 54.0))], (42.169420149011984, 67.66375121477162): [((39.0, 95.0), (47.0, 26.0)), ((46.0, 69.0), (3.0, 54.0))], (44.92170818505338, 43.9252669039146): [((33.0, 63.0), (48.0, 39.0)), ((39.0, 95.0), (47.0, 26.0))], (48.67805953693495, 39.15325248070562): [((39.0, 91.0), (53.0, 16.0)), ((53.0, 72.0), (48.0, 34.0))], (52.34669589727529, 19.499843407453803): [((16.0, 30.0), (61.0, 17.0)), ((39.0, 91.0), (53.0, 16.0))]}
8

Determinando a ocorrência de 8 interseções, sendo a chave do dicionário o ponto de ocorrência.

Observações:
* Os arquivos completos podem ser encontrado na parta:
Pasta - Google Drive

  • Os arquivos devem ser salvos no mesmo project por segurança, pois serão lidos conjuntamente.

  • Uma boa abordagem do algoritmo empregado é feita em:
    Wikipedia

comentou Jul 12 por Adriana Molinari (111 pontos)  
Claudia, muito didática a sua resposta.
Sobre a complexidade do algoritmo,  vale destacar que se o algoritmo fizesse a comparação para cada segmento, seria O(n^2) sendo um algoritmo baseado no input. Como ele é baseado no número de interseções, ou seja, baseado no output, ele é OMEGA(n^2)
comentou Jul 13 por CP (37 pontos)  
Código para a classe do Status    

from lsiaux import *

    ev = 0.00000001


    class T:
         def __init__(self):
            self.root = Node(None, None, None, None)

         def contain_p(self, p):
             if self.root.value is None:
                 return [[], []]
             lists = [[], []]
             self.root.contain_p(p, lists)
            return lists[0], lists[1]

         def get_left_neighbor(self, p):
            if self.root.value is None:
                return None
            return self.root.get_left_neighbor(p)
 
        def get_right_neighbor(self, p):
            if self.root.value is None:
                return None
            return self.root.get_right_neighbor(p)

        def insert(self, key, s):
            if self.root.value is None:
                self.root.left = Node(s, None, None, self.root)
                self.root.value = s
                self.root.m = inclinacao(s)
            else:
                (node, path) = self.root.find_insert_pt(key, s)
                if path == 'r':
                    node.right = Node(s, None, None, node)
                    node.right.adjust()
                elif path == 'l':
                    node.left = Node(s, None, None, node)
                else:
                
                    if node.compare_to_key(key) < 0 or (node.compare_to_key(key) == 0 and
                  node.compare_lower(key, s) < 1):
                        new_internal = Node(s, None, node, node.parent)
                        new_leaf = Node(s, None, None, new_internal)
                        new_internal.left = new_leaf
                        if node is node.parent.left:
                            node.parent.left = new_internal
                            node.adjust()
                        else:
                            node.parent.right = new_internal
                    else:
                        new_internal = Node(node.value, node, None, node.parent)
                        new_leaf = Node(s, None, None, new_internal)
                        new_internal.right = new_leaf
                        if node is node.parent.left:
                            node.parent.left = new_internal
                            new_leaf.adjust()
                        else:
                            node.parent.right = new_internal
                    node.parent = new_internal

        def delete(self, p, s):
            key = p
            node = self.root.find_delete_pt(key, s)
            val = node.value
            if node is node.parent.left:
                parent = node.parent.parent
                if parent is None:
                    if self.root.right is not None:
                        if self.root.right.left or self.root.right.right:
                            self.root = self.root.right
                            self.root.parent = None
                        else:
                            self.root.left = self.root.right
                            self.root.value = self.root.right.value
                            self.root.m = self.root.right.m
                            self.root.right = None
                    else:
                        self.root.left = None
                       self.root.value = None
                elif node.parent is parent.left:
                    parent.left = node.parent.right
                    node.parent.right.parent = parent
                else:
                    parent.right = node.parent.right
                    node.parent.right.parent = parent
            else:
                parent = node.parent.parent
                if parent is None:
                    if self.root.left:
                        if self.root.left.right or self.root.left.left:
                            self.root = self.root.left
                            self.root.parent = None
                        else:
                            self.root.right = None
                    else:
                        self.root.right = None
                        self.root.value = None
                elif node.parent is parent.left:
                    parent.left = node.parent.left
                    node.parent.left.parent = parent
                    farright = node.parent.left
                    while farright.right is not None:
                        farright = farright.right
                    farright.adjust()
                else:
                    parent.right = node.parent.left
                    node.parent.left.parent = parent
                    farright = node.parent.left
                    while farright.right is not None:
                        farright = farright.right
                    farright.adjust()
            return val

        def print_tree(self):
            self.root.print_tree()


    class Node:
        def __init__(self, value, left, right, parent):
            self.value = value  
            self.left = left
            self.right = right
            self.parent = parent
            self.m = None
            if value is not None:
                self.m = inclinacao(value)

    
        def compare_to_key(self, p):
            x0 = self.value[0][0]
            y0 = self.value[0][1]
            y1 = p[1]
            if self.m != 0 and self.m is not None:
                x1 = x0 - float(y0 - y1) / self.m
                return comparar_x(p, (x1, y1))
            else:
                x1 = p[0]
                return 0

        def get_left_neighbor(self, p):
            neighbor = None
            n = self
            if n.left is None and n.right is None:
                return neighbor
            last_right = None
            found = False
            while not found:
                c = n.compare_to_key(p)
                if c < 1 and n.left:
                    n = n.left
                 elif c == 1 and n.right:
                    n = n.right
                    last_right = n.parent
                else:
                    found = True
             c = n.compare_to_key(p)
            if c == 0:
                if n is n.parent.right:
                    return n.parent
                else:
                    goright = None
                    if last_right:
                        goright = last_right.left
                    return self.get_lr(None, goright)[0]
        
            if c == -1:
                goright = None
                if last_right:
                    goright = last_right.left
                return self.get_lr(None, goright)[0]
            if c == 1:
                neighbor = n
            return neighbor

        def get_right_neighbor(self, p):
            neighbor = None
            n = self
            if n.left is None and n.right is None:
                return neighbor
            last_left = None
            found = False
            while not found:
                c = n.compare_to_key(p)
                if c == 0 and n.right:
                    n = n.right
                elif c < 0 and n.left:
                    n = n.left
                    last_left = n.parent
                elif c == 1 and n.right:
                    n = n.right
                else:
                    found = True
             c = n.compare_to_key(p)
        
            if c == 0:
                if n.parent is None:
                    return None
                if n is n.parent.right:
                    goleft = None
                    if last_left:
                        goleft = last_left.right
                    return self.get_lr(goleft, None)[1]
                else:
                    return self.get_lr(n.parent.right, None)[1]
            if c == 1:
                goleft = None
                if last_left:
                    goleft = last_left.right
                return self.get_lr(goleft, None)[1]
            if c == -1:
                return n
            return neighbor

    
        def get_lr(self, left, right):
            lr = [None, None]
            if left:
                while left.left:
                    left = left.left
                lr[1] = left
            if right:
                while right.right:
                    right = right.right
                lr[0] = right
            return lr

        def contain_p(self, p, lists):
            c = self.compare_to_key(p)
            if c == 0:
                if self.left is None and self.right is None:
                    if comparar_x(p, self.value[1]) == 0:
                        lists[1].append(self.value)
                    else:
                        lists[0].append(self.value)
                if self.left:
                    self.left.contain_p(p, lists)
                if self.right:
                    self.right.contain_p(p, lists)
            elif c < 0:
                if self.left:
                    self.left.contain_p(p, lists)
            else:
                if self.right:
                    self.right.contain_p(p, lists)

        def find_insert_pt(self, key, seg):
            if self.left and self.right:
                if self.compare_to_key(key) == 0 and self.compare_lower(key, seg) == 1:
                    return self.right.find_insert_pt(key, seg)
                elif self.compare_to_key(key) < 1:
                    return self.left.find_insert_pt(key, seg)
                else:
                    return self.right.find_insert_pt(key, seg)
        
            elif self.left:
                if self.compare_to_key(key) == 0 and self.compare_lower(key, seg) == 1:
                    return self, 'r'
                elif self.compare_to_key(key) < 1:
                    return self.left.find_insert_pt(key, seg)
                else:
                    return self, 'r'
            else:
                return self, 'n'

    
        def adjust(self):
            value = self.value
            m = self.m
            parent = self.parent
            node = self
            while parent and node is parent.right:
                node = parent
                parent = node.parent
            if parent and node is parent.left:
                parent.value = value
                parent.m = m

        def compare_lower(self, p, s2):
            y = p[1] - 10
            key = get_x_at(s2, (p[0], y))
            return self.compare_to_key(key)

    
        def find_delete_pt(self, key, value):
            if self.left and self.right:
                if self.compare_to_key(key) == 0 and self.compare_lower(key, value) == -1:
                    return self.right.find_delete_pt(key, value)
                if self.compare_to_key(key) < 1:
                    return self.left.find_delete_pt(key, value)
                else:
                    return self.right.find_delete_pt(key, value)
            elif self.left:
                if self.compare_to_key(key) < 1:
                    return self.left.find_delete_pt(key, value)
                else:
                    return None
        
            else:
                if self.compare_to_key(key) == 0 and segs_equal(self.value, value):
                    return self
                else:
                    return None

    
        def print_tree(self, l=0):
            l += 1
            if self.left:
                self.left.print_tree(l)
            if self.left or self.right:
                print(f'INTERNAL: {0}'.format(l))
            else:
                print(f'LEAF: {0}'.format(l))
            print(self)
            print(self.value)
            if self.right:
                self.right.print_tree(l)
0 votos
respondida Jul 13 por danielcajueiro (5,641 pontos)  
from lsiaux import *



ev = 0.00000001




class T:
    def __init__(self):
        self.root = Node(None, None, None, None)

    def contain_p(self, p):
        if self.root.value is None:
            return [[], []]
        lists = [[], []]
        self.root.contain_p(p, lists)
        return lists[0], lists[1]

    def get_left_neighbor(self, p):
        if self.root.value is None:
            return None
        return self.root.get_left_neighbor(p)

    def get_right_neighbor(self, p):
        if self.root.value is None:
            return None
        return self.root.get_right_neighbor(p)

    def insert(self, key, s):
        if self.root.value is None:
            self.root.left = Node(s, None, None, self.root)
            self.root.value = s
            self.root.m = inclinacao(s)
        else:
            (node, path) = self.root.find_insert_pt(key, s)
            if path == 'r':
                node.right = Node(s, None, None, node)
                node.right.adjust()
            elif path == 'l':
                node.left = Node(s, None, None, node)
            else:
                # this means matching Node was a leaf
                # need to make a new internal Node
                if node.compare_to_key(key) < 0 or (node.compare_to_key(key) == 0 and node.compare_lower(key, s) < 1):
                    new_internal = Node(s, None, node, node.parent)
                    new_leaf = Node(s, None, None, new_internal)
                    new_internal.left = new_leaf
                    if node is node.parent.left:
                        node.parent.left = new_internal
                        node.adjust()
                    else:
                        node.parent.right = new_internal
                else:
                    new_internal = Node(node.value, node, None, node.parent)
                    new_leaf = Node(s, None, None, new_internal)
                    new_internal.right = new_leaf
                    if node is node.parent.left:
                        node.parent.left = new_internal
                        new_leaf.adjust()
                    else:
                        node.parent.right = new_internal
                node.parent = new_internal

    def delete(self, p, s):
        key = p
        node = self.root.find_delete_pt(key, s)
        val = node.value
        if node is node.parent.left:
            parent = node.parent.parent
            if parent is None:
                if self.root.right is not None:
                    if self.root.right.left or self.root.right.right:
                        self.root = self.root.right
                        self.root.parent = None
                    else:
                        self.root.left = self.root.right
                        self.root.value = self.root.right.value
                        self.root.m = self.root.right.m
                        self.root.right = None
                else:
                    self.root.left = None
                    self.root.value = None
            elif node.parent is parent.left:
                parent.left = node.parent.right
                node.parent.right.parent = parent
            else:
                parent.right = node.parent.right
                node.parent.right.parent = parent
        else:
            parent = node.parent.parent
            if parent is None:
                if self.root.left:
                    # switch properties
                    if self.root.left.right or self.root.left.left:
                        self.root = self.root.left
                        self.root.parent = None
                    else:
                        self.root.right = None
                else:
                    self.root.right = None
                    self.root.value = None
            elif node.parent is parent.left:
                parent.left = node.parent.left
                node.parent.left.parent = parent
                farright = node.parent.left
                while farright.right is not None:
                    farright = farright.right
                farright.adjust()
            else:
                parent.right = node.parent.left
                node.parent.left.parent = parent
                farright = node.parent.left
                while farright.right is not None:
                    farright = farright.right
                farright.adjust()
        return val

    def print_tree(self):
        self.root.print_tree()


class Node:
    def __init__(self, value, left, right, parent):
        self.value = value  # associated line segment
        self.left = left
        self.right = right
        self.parent = parent
        self.m = None
        if value is not None:
            self.m = inclinacao(value)

    # compares line segment at y-val of p to p
    # TODO: remove this and replace with get_x_at
    def compare_to_key(self, p):
        x0 = self.value[0][0]
        y0 = self.value[0][1]
        y1 = p[1]
        if self.m != 0 and self.m is not None:
            x1 = x0 - float(y0 - y1) / self.m
            return comparar_x(p, (x1, y1))
        else:
            x1 = p[0]
            return 0

    def get_left_neighbor(self, p):
        neighbor = None
        n = self
        if n.left is None and n.right is None:
            return neighbor
        last_right = None
        found = False
        while not found:
            c = n.compare_to_key(p)
            if c < 1 and n.left:
                n = n.left
            elif c == 1 and n.right:
                n = n.right
                last_right = n.parent
            else:
                found = True
        c = n.compare_to_key(p)
        if c == 0:
            if n is n.parent.right:
                return n.parent
            else:
                goright = None
                if last_right:
                    goright = last_right.left
                return self.get_lr(None, goright)[0]
        # n stores the highest-value in the left subtree
        if c == -1:
            goright = None
            if last_right:
                goright = last_right.left
            return self.get_lr(None, goright)[0]
        if c == 1:
            neighbor = n
        return neighbor

    def get_right_neighbor(self, p):
        neighbor = None
        n = self
        if n.left is None and n.right is None:
            return neighbor
        last_left = None
        found = False
        while not found:
            c = n.compare_to_key(p)
            if c == 0 and n.right:
                n = n.right
            elif c < 0 and n.left:
                n = n.left
                last_left = n.parent
            elif c == 1 and n.right:
                n = n.right
            else:
                found = True
        c = n.compare_to_key(p)
        # can be c==0 and n.left if at root node
        if c == 0:
            if n.parent is None:
                return None
            if n is n.parent.right:
                goleft = None
                if last_left:
                    goleft = last_left.right
                return self.get_lr(goleft, None)[1]
            else:
                return self.get_lr(n.parent.right, None)[1]
        if c == 1:
            goleft = None
            if last_left:
                goleft = last_left.right
            return self.get_lr(goleft, None)[1]
        if c == -1:
            return n
        return neighbor

    # travels down a single direction to get neighbors
    def get_lr(self, left, right):
        lr = [None, None]
        if left:
            while left.left:
                left = left.left
            lr[1] = left
        if right:
            while right.right:
                right = right.right
            lr[0] = right
        return lr

    def contain_p(self, p, lists):
        c = self.compare_to_key(p)
        if c == 0:
            if self.left is None and self.right is None:
                if comparar_x(p, self.value[1]) == 0:
                    lists[1].append(self.value)
                else:
                    lists[0].append(self.value)
            if self.left:
                self.left.contain_p(p, lists)
            if self.right:
                self.right.contain_p(p, lists)
        elif c < 0:
            if self.left:
                self.left.contain_p(p, lists)
        else:
            if self.right:
                self.right.contain_p(p, lists)

    def find_insert_pt(self, key, seg):
        if self.left and self.right:
            if self.compare_to_key(key) == 0 and self.compare_lower(key, seg) == 1:
                return self.right.find_insert_pt(key, seg)
            elif self.compare_to_key(key) < 1:
                return self.left.find_insert_pt(key, seg)
            else:
                return self.right.find_insert_pt(key, seg)
        # this case only happens at root
        elif self.left:
            if self.compare_to_key(key) == 0 and self.compare_lower(key, seg) == 1:
                return self, 'r'
            elif self.compare_to_key(key) < 1:
                return self.left.find_insert_pt(key, seg)
            else:
                return self, 'r'
        else:
            return self, 'n'

    # adjusts stored segments in inner nodes
    def adjust(self):
        value = self.value
        m = self.m
        parent = self.parent
        node = self
        # go up left as much as possible
        while parent and node is parent.right:
            node = parent
            parent = node.parent
        # parent to adjust will be on the immediate right
        if parent and node is parent.left:
            parent.value = value
            parent.m = m

    def compare_lower(self, p, s2):
        y = p[1] - 10
        key = get_x_at(s2, (p[0], y))
        return self.compare_to_key(key)

    # returns matching leaf node, or None if no match
    # when deleting, you don't delete below--you delete above! so compare lower = -1.
    def find_delete_pt(self, key, value):
        if self.left and self.right:
            # if equal at this pt, and this node's value is less than the seg's slightly above this pt
            if self.compare_to_key(key) == 0 and self.compare_lower(key, value) == -1:
                return self.right.find_delete_pt(key, value)
            if self.compare_to_key(key) < 1:
                return self.left.find_delete_pt(key, value)
            else:
                return self.right.find_delete_pt(key, value)
        elif self.left:
            if self.compare_to_key(key) < 1:
                return self.left.find_delete_pt(key, value)
            else:
                return None
        # is leaf
        else:
            if self.compare_to_key(key) == 0 and segs_equal(self.value, value):
                return self
            else:
                return None

    # also prints depth of each node
    def print_tree(self, l=0):
        l += 1
        if self.left:
            self.left.print_tree(l)
        if self.left or self.right:
            print(f'INTERNAL: {0}'.format(l))
        else:
            print(f'LEAF: {0}'.format(l))
        print(self)
        print(self.value)
        if self.right:
            self.right.print_tree(l)
...