Intersección de polígonos
Publicado por ANA (11 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:
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)
Valora esta pregunta
0