Línea horizontal más rápida < - > algoritmo de intersección de polígono convexo?

Question

Necesito resolver algo relativamente simple: tengo un polígono 2D convexo n-vértices y una línea horizontal (!) con alguna coordenada 'y'. Solo necesito una cosa: verificar si el polígono se cruza con esta línea (es decir, tiene 2 intersecciones) o no.

El más rápido que se me ocurre es encontrar coordenadas mín. / máx. y dentro de un polígono (bucle repetido n veces con dos comparaciones y dos almacenes) y luego comparar si min y < = y < max y.

De alguna manera siento que esto podría resolverse más "matemáticamente" pero siempre termino con un código más lento (por ejemplo, en forma de vector: necesito calcular las diferencias para n [i] yn [i + 1], luego multiplicarlas, agregar etc., mucho más lento que 2 cmps + tiendas).

Answer 1

Solo necesita verificar si su polígono tiene un punto con y1 < y y uno con y2 > y. Tan pronto como haya encontrado esos dos puntos, habrá terminado. Si puede indexar sus puntos por la coordenada y, debería ser una búsqueda rápida.

Answer 2

Si es una línea 2d horizontal, entonces sí, el método que ha descrito es probablemente el más rápido. También podría provocar un cortocircuito, como si llegara a la mitad del cheque y tuviera un min + max que son > y < su valor y entonces tiene una intersección.

Answer 3

Si tiene que hacerlo en bruto cada vez, entonces probablemente no encontrará ningún truco para hacerlo más rápido que eso.

Si puede almacenar en caché el valor Y mínimo / máximo con el polígono, puede ahorrar tiempo al no recorrer cada vértice cada vez que realiza la prueba.

Si su polígono tiene asociado un cuadro delimitador alineado, puede probarlo contra las extensiones del cuadro en lugar del polígono y obtener el mismo resultado más rápido.

Answer 4

Otro enfoque, se describe aquí: algoritmo óptimo si la línea intersecta el polígono convexo . Pero debido a que está manejando con líneas ortogonales, puede simplificarlo un poco :). Por lo tanto, la complejidad total es log N sin almacenar valores.