Búsqueda de los segmentos de línea más próximos a un punto mediante shapely?

Question

Fondo

A partir de un Punto conocido, requiero establecer el "perímetro visible" circundante más cercano contra una tabla de MultiLineStrings, como se muestra en el diagrama.

He buscado en este sitio con una serie de términos (por ejemplo, borde mínimo, perímetro mínimo, vecino más cercano, clip, polígono que contiene, visibilidad, snap, nodos de corte, ray-trace, relleno de inundación, límite interior, enrutamiento, casco cóncavo), pero no puedo encontrar ninguna pregunta anterior que parece coincidir con este escenario.

Diagrama

• El círculo verde es el Punto conocido.
• Las líneas negras son las MultiLineStrings conocidas.
• Las líneas grises indican un barrido radial desde el Punto conocido.
• Los puntos rojos son la intersección más cercana del barrido radial y las MultiLineStrings.

Parámetros

• El punto nunca intersectará las MultiLineStrings.
• El Punto siempre estará centrado nominalmente dentro de las MultiLineStrings.
• Las MultiLineStrings nunca encerrarán completamente el Punto, por lo tanto el perímetro será una MultiLineString.
• Habrá una tabla que contendrá aproximadamente 1.000 MultiLineStrings (que normalmente contienen una sola línea de unos 100 puntos).

Metodología considerada

• Realice un barrido radial construyendo una serie de líneas a partir del Punto conocido (en incrementos de, por ejemplo, 1 grado).
• Establecer el punto de intersección más cercano de cada línea de barrido radial con las MultiLineStrings.
• Cuando una de las líneas de barrido radial no se cruza con ninguna de las MultiLineStrings, esto indicaría un hueco en el perímetro que se acomodaría en la construcción MultiLineString del perímetro.

Resumen

Aunque esta técnica encontrará las intersecciones más cercanas, no encontrará necesariamente todos los puntos de nodos perimetrales más próximos, dependiendo de la resolución del barrido radial. ¿Alguien puede recomendar un método alternativo para establecer todos los puntos del perímetro o complementar la técnica de barrido radial con alguna forma de amortiguación, sectorización o desplazamiento?

Software

Mi preferencia es utilizar SpatiaLite y/o Shapely para la solución, pero agradecería cualquier sugerencia que pudiera implementarse utilizando software de código abierto.

Edición: Solución funcional (basada en la respuesta de @gene)

from shapely.geometry import Point, LineString, mapping, shape
from shapely.ops import cascaded_union
from shapely import affinity
import fiona

sweep_res = 10  # sweep resolution (degrees)
focal_pt = Point(0, 0)  # radial sweep centre point
sweep_radius = 100.0  # sweep radius

# create the radial sweep lines
line = LineString([(focal_pt.x,focal_pt.y), \
                   (focal_pt.x, focal_pt.y + sweep_radius)])

sweep_lines = [affinity.rotate(line, i, (focal_pt.x, focal_pt.y)) \
               for i in range(0, 360, sweep_res)]

radial_sweep = cascaded_union(sweep_lines)

# load the input lines and combine them into one geometry
input_lines = fiona.open("input_lines.shp")
input_shapes = [shape(f['geometry']) for f in input_lines]
all_input_lines = cascaded_union(input_shapes)

perimeter = []
# traverse each radial sweep line and check for intersection with input lines
for radial_line in radial_sweep:
    inter = radial_line.intersection(all_input_lines)

    if inter.type == "MultiPoint":
       # radial line intersects at multiple points
       inter_dict = {}
       for inter_pt in inter:
           inter_dict[focal_pt.distance(inter_pt)] = inter_pt
       # save the nearest intersected point to the sweep centre point
       perimeter.append(inter_dict[min(inter_dict.keys())])

    if inter.type == "Point":
       # radial line intersects at one point only
       perimeter.append(inter)

    if inter.type == "GeometryCollection":
       # radial line doesn't intersect, so skip
       pass

# combine the nearest perimeter points into one geometry
solution = cascaded_union(perimeter)

# save the perimeter geometry
schema = {'geometry': 'MultiPoint', 'properties': {'test': 'int'}}
with fiona.open('perimeter.shp', 'w', 'ESRI Shapefile', schema) as e:
     e.write({'geometry':mapping(solution), 'properties':{'test':1}})

Answer 1

He reproducido tu ejemplo con shapefiles.

Puede utilizar Shapely y Fiona para resolver su problema.

1) Su problema (con un Point ):

2) partiendo de una línea arbitraria (con una longitud adecuada):

from shapely.geometry import Point, LineString
line = LineString([(point.x,point.y),(final_pt.x,final_pt.y)])

3) utilizando shapely.affinity.rotate para crear los radios (girando la línea desde el punto, mira también el Mike Toews La respuesta de Python, librería shapely: ¿es posible realizar una operación afín sobre un polígono shape? ):

from shapely import affinity
# Rotate i degrees CCW from origin at point (step 10°)
radii= [affinity.rotate(line, i, (point.x,point.y)) for i in range(0,360,10)]

4) ahora, utilizando shapely:unión_en_cascada (o shapely:unión_unaria ) para obtener una MultiLineString:

from shapely.ops import cascaded_union
mergedradii = cascaded_union(radii)
print mergedradii.type
MultiLineString

5) lo mismo con las líneas originales (shapefile)

import fiona
from shapely.geometry import shape
orlines = fiona.open("orlines.shp")
shapes = [shape(f['geometry']) for f in orlines]
mergedlines = cascaded_union(shapes)
print mergedlines.type
MultiLineString

6) se calcula la intersección entre las dos multigeometrías y el resultado se guarda en un shapefile:

 points =  mergedlines.intersection(mergedradii)
 print points.type
 MultiPoint
 from shapely.geometry import mapping
 schema = {'geometry': 'MultiPoint','properties': {'test': 'int'}}
 with fiona.open('intersect.shp','w','ESRI Shapefile', schema) as e:
      e.write({'geometry':mapping(points), 'properties':{'test':1}})

Resultado:

7) pero, problema, si se utiliza un radio más largo, el resultado es diferente:

8) Y si quieres obtener tu resultado, tienes que seleccionar sólo el punto con la distancia más corta desde el punto original en un radio:

points_ok = []
for line in mergeradii:
   if line.intersects(mergedlines):
       if line.intersection(mergedlines).type == "MultiPoint":
          # multiple points: select the point with the minimum distance
          a = {}
          for pt in line.intersection(merged):
              a[point.distance(pt)] = pt
          points_ok.append(a[min(a.keys())])
       if line.intersection(mergedlines).type == "Point":
          # ok, only one intersection
          points_ok.append(line.intersection(mergedlines))
solution = cascaded_union(points_ok)
schema = {'geometry': 'MultiPoint','properties': {'test': 'int'}}
with fiona.open('intersect3.shp','w','ESRI Shapefile', schema) as e:
     e.write({'geometry':mapping(solution), 'properties':{'test':1}})

Resultado final:

Espero que sea lo que desea.