La determinación de si un punto está en una calle

Question

Si tengo una línea poligonal que describe un camino y sé que el ancho de la vía a todas las partes, es que hay un algoritmo que puede utilizar para determinar si un punto está en el camino? No estoy del todo seguro de cómo hacer esto ya que la línea en sí tiene una anchura de 1 píxel.

Gracias,

Jeff

Answer 1

Encontrar la distancia mínima del punto a la línea (que será un vector perpendicular a la línea). cálculo real donde P0 es el primer punto del segmento de carretera, v es el vector de segmento de carretera y w es el vector de P0 al punto en cuestión. Tendrá que iterar sobre cada borde de la polilínea. Si la distancia es menor que la anchura de ese segmento, entonces es "on" la carretera.

d = |v x w| / |v|

Las esquinas pueden ser complicado dependiendo de si los trata como redondeada (radio constante) o angular.

Answer 2

Tal vez usted podría tomar cada segmento de línea, construir el rectángulo del segmento de línea + su anchura, y el uso de algoritmos de colisión rectángulo / punto para determinar si el rectángulo contiene el punto. Un buen algoritmo en cuenta la anchura = 1 escenario, que debe simplemente tratar de construir la función inversa del segmento de línea y determinar si y-1 (Punto.y) es una X entre line_segment.x1 y line_segment.x2