Python - Intersección de polígonos

   
Vista:

Intersección de polígonos

Publicado por ANA (9 intervenciones) el 18/07/2017 11:17:39
Hola,

Por favor, necesito ayuda.
Dados 2 polígonos, con las intersecciones entre ellos,
tengo un programa que me devuelve el resultado si los polígonos tiene solo una intersección, pero para el caso de polígonos complejos (con mas de una intersección) no me va, no entiendo porque no encuentra algunos vértices.

También está la imagen con los polígonos, donde el verde es poly1 y el marrón es poly2.

He intendado añadir while: mientras la lista de intersecciones no esta vacía, que siga añadiendo los vértices, pero no me funciona.

Gracias.


Datos:

INTERSECTIONS: {(-9.53511, -2.04623, 0.0): (1808426762568[4], 1808426765768[1]), (11.8146, -11.7576, 0.0): (1808426765768[4], 1808426762568[1]), (-10.9031, -10.3098, 0.0): (1808426762568[3], 1808426765768[0]), (10.3785, -8.68544, 0.0): (1808426765768[4], 1808426762568[0]), (-12.1834, -7.09706, 0.0): (1808426762568[3], 1808426765768[1]), (15.6952, -9.10677, 0.0): (1808426765768[3], 1808426762568[1]), (-6.34428, -5.68024, 0.0): (1808426762568[4], 1808426765768[0]), (15.4657, -6.79997, 0.0): (1808426765768[3], 1808426762568[0])}

Poly1: [[(-10.9031, -10.3098, 0.0), (-6.34428, -5.68024, 0.0)], [(-9.53511, -2.04623, 0.0), (-12.1834, -7.09706, 0.0)], [], [(15.6952, -9.10677, 0.0), (15.4657, -6.79997, 0.0)], [(11.8146, -11.7576, 0.0), (10.3785, -8.68544, 0.0)]]

Poly2: [[(10.3785, -8.68544, 0.0), (15.4657, -6.79997, 0.0)], [(11.8146, -11.7576, 0.0), (15.6952, -9.10677, 0.0)], [], [(-10.9031, -10.3098, 0.0), (-12.1834, -7.09706, 0.0)], [(-9.53511, -2.04623, 0.0), (-6.34428, -5.68024, 0.0)]]

Poly1 con las intersecciones: Polygon( boundary=Polyline( vertices=[(4.0429, 4.86799, 0.0), (-6.34428, -5.68024, 0.0), (-10.9031, -10.3098, 0.0), (-17.2442, -16.7492, 0.0), (-12.1834, -7.09706, 0.0), (-9.53511, -2.04623, 0.0), (-1.23762, 13.7789, 0.0), (13.9439, 8.49835, 0.0), (15.4657, -6.79997, 0.0), (15.6952, -9.10677, 0.0), (17.0792, -23.0198, 0.0), (11.8146, -11.7576, 0.0), (10.3785, -8.68544, 0.0), (4.0429, 4.86799, 0.0)]) holes=[])

Poly2 con las intersecciones: Polygon( boundary=Polyline( vertices=[(-0.247525, -12.6238, 0.0), (10.3785, -8.68544, 0.0), (15.4657, -6.79997, 0.0), (23.3498, -3.87789, 0.0), (15.6952, -9.10677, 0.0), (11.8146, -11.7576, 0.0), (-0.0825083, -19.8845, 0.0), (-9.32343, -14.2739, 0.0), (-10.9031, -10.3098, 0.0), (-12.1834, -7.09706, 0.0), (-18.0693, 7.67327, 0.0), (-9.53511, -2.04623, 0.0), (-6.34428, -5.68024, 0.0), (-0.247525, -12.6238, 0.0)]) holes=[])





Aquí esta el código para una intersección:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
def next_v(curr_poly, last_v):
    n_v_idx = (curr_poly.boundary.vertices.index(last_v) + 1) % len(curr_poly.boundary)
    n_v = curr_poly.boundary[n_v_idx]
    return n_v_idx, n_v
 
# Ya podemos construir las intersecciones
 
    first_intersection = intersections.popitem()  # (point3, [segment_list, segment_list_idx])
    first_vertex = first_intersection[0]
    print("Start: add vertex " + str(first_vertex))
    intersection_vertices = [first_vertex]
 
 
    current_polygon, other_polygon = poly1, poly2 # Cambia los nombres
    next_vertex_idx, next_vertex = next_v(current_polygon, first_vertex) # Averigua el siguiente vertice y su lugar (idx)
 
 
    # Si el siguiente vertice es una interseccion y no esta dentro de otro poligono,
    # lo añade a la lista resultado y cambia los poligonos: Current es Other y Other es Current
 
    if next_vertex in intersections.keys() or not other_polygon.contains_point(next_vertex):
        # keys saca las coordenadas, pq en nuestro caso el formato es: INTERSECTIONS: {(-18, -10, 0): (1699656959880[2], 1699656923208[0]), (-28, -15, 0): (1699656959880[1], 1699656923208[0])} keys saca lo que va delante de dos puntos (:)
        intersection_vertices.append(Point3(next_vertex))
 
        current_polygon, other_polygon = other_polygon, current_polygon
        next_vertex_idx, next_vertex = next_v(current_polygon, next_vertex)
 
    # Mientras el siguiente vertice no es el inicial, comprueba y hace:
    # ¿Es una interseccion? -> Si, LO AÑADE A LA LISTA,
    #                              Cambia los poligonos current a other...
    #                              Elumina este vertice de la lista de las interseccones
    #                       -> No,
    # ¿Esta dentro de otro poligono? -> Si, LO AÑADE A LA LISTA,
    #                                -> No, Cambia los poligonos current a other...
 
    while next_vertex != intersection_vertices[0]:
        print("currently, the intersection vertices are " + str(intersection_vertices))
 
        print("\n\nConsidering vertex: " + str(next_vertex))
        print("on Polygon: " + str(current_polygon))
        if next_vertex in intersections.keys():  # Comprueba si es interseccion
            print("next vertex is an intersection point!")
            # append it to the union
            intersection_vertices.append(Point3(next_vertex))
 
            # switch to other polygon
            current_polygon, other_polygon = other_polygon, current_polygon
 
            # not strictly necessary, but improves search time for next iterations
            # as we have to search in a smaller dictionary
            intersections.pop(next_vertex, None)
        elif other_polygon.contains_point(next_vertex):
            print("next vertex is inside the other polygon!")
            intersection_vertices.append(Point3(next_vertex))
        else:
            print("next vertex is not an intersection point, neither is inside the other polygon!")
            current_polygon, other_polygon = other_polygon, current_polygon
 
        print("Let's take the next vertex of current polygon, which is: " + str(current_polygon))
        # go to next vertex
        next_vertex_idx, next_vertex = next_v(current_polygon, next_vertex)
    intersection_poly = Polygon(boundary=intersection_vertices)





Captura
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder