graphs - prim''s algorithm

¿Cómo creo una ruta aleatoria?

Question

Estoy buscando un algoritmo que pueda generar algo como lo que está en esta imagen:

He leído acerca de los algoritmos de paseo borracho, pero no parecen encajar lo que necesito. No estoy seguro si puedo lograr lo que estoy buscando con un algoritmo de caminata borracho muy modificado o si debería buscar algún otro algoritmo con el que meterme.

Answer 1

Como quiere evitar la autointersección, una caminata aleatoria será difícil de hacer correctamente. Podrías fácilmente arrinconarte en una esquina. Sugeriría comenzar con un único segmento de línea que cruza el área, luego dividir este segmento de línea en algún lugar en el medio y desplazar el punto medio en una cantidad aleatoria proporcional a la longitud del segmento de línea. Repita este proceso recursivamente para los dos nuevos segmentos de línea. Si termina con un punto medio que hace que uno de los dos nuevos segmentos de línea crucen un segmento de línea existente, intente con un punto medio diferente. Detenga la recursión cuando los segmentos de su línea son cortos (como quiera que quiera definir eso).