Como ya te lo han comentado, puedes tener infinitas soluciones, pero como te interesa tener solo una en particular, entonces podemos elegir una estrategia segura para encontrar las líneas de corte que nos aseguren la intersección con todas las líneas posibles. ¿Y que líneas nos aseguran de forma segura la intersección con cualquier otra recta? Respuesta: las dos diagonales, ambas rectas cortan cualquier línea posible tal como has definido que se construyen. Cualquier línea que "nazca" en alguno de los lados del rectángulo y "muera" en cualquier otro lado del mismo, se intersectará con al menos una de las dos diagonales.
Esto cambia un poco el sentido del problema, podemos decir que al menos con dos rectas (las diagonales) podremos cortar cualquier línea que has trazado, es decir 2 es nuestro número máximo y ya sabemos cuales son las coordenadas de estas rectas, sin embargo, de acuerdo a la configuración de los sensores, puede ocurrir que con una sola de las diagonales cortemos el camino de todos. De forma que ahora el problema se reduce a verificar cuantas lineas corta cada diagonal, si una sola corta el total de sensores, esa será nuestra solución única al problema.
Ésta sería una prueba de concepto:
import matplotlib.pyplot as plt
from random import randint
w,h = (3,9)
# Ejemplo con solución de una sola diagonal
sensores = [
[[0, w], [2, h]],
[[0, w], [4, 4]],
[[0, w], [8, 7]],
]
# Ejemplo con solución usando las dos diagonales
sensores = [
[[0, w], [2, h]],
[[0, w], [4, 4]],
[[0, w], [8, 7]],
[[1, w], [h, 3]],
[[2, w], [0, 2]],
]
diagonales = [
[[0, w], [0, h]],
[[0, w], [h, 0]]
]
cantidad_sensores = len(sensores)
# Dibujamos el camino de los sensores
for x,y in sensores:
plt.plot(x,y, marker = 'o', color='blue')
# Verificamos cada diagonal, si una sola corta el total de sensores
# esta será nuestra respuesta sino serán las dos diagonales
diag_ok = None
for xd,yd in diagonales:
corta = 0
for xs,ys in sensores:
print("diag: {0}:{1} sensor {2}:{3}".format(xd, yd, xs, ys))
if (xs[0] <= xd[0] and ys[1] > yd[1]) or (xs[0] >= xd[0] and ys[1]< yd[1]):
corta = corta + 1
if corta == cantidad_sensores:
diag_ok = [xd,yd]
break
if diag_ok is not None:
plt.plot(diag_ok[0], diag_ok[1], marker = 'o', color='red', linestyle = 'dashdot')
else:
for x,y in diagonales:
plt.plot(x,y, marker = 'o', color='red', linestyle = 'dashdot')
plt.axis([0,w,0,h])
plt.show()
Ejemplo con solución de una única diagonal
Ejemplo con solución con las dos diagonales
Una aclaración importante
@abulafia, me hizo notar algo importante, está solución resuelve con una mínima cantidad de rectas y con un mínimo de complejidad computacional la solución para cualquier cantidad de líneas de sensores, pero para un conjunto más pequeño de posibles combinaciones, no te garantiza el mínimo posible. Es decir, existe una combinación de sensores en la que este "algoritmo" te dará 2 rectas mínimas, cuando la realidad es que podrías resolverlo con una. Tomo el ejemplo de @abulafia: