Estoy buscando una manera de detectar si un conjunto de puntos / coordenadas tiene líneas que se intersectan.
Un poco de configuración, estoy dibujando un polígono usandoUIBezierPath en una superposición a un mapa. Todo esto funciona. Soy capaz de reducir los puntos del mapa hacia abajo utilizando un algoritmo de reducción de puntos, y me quedo con un polígono de aspecto simple que se ve bien en mi mapa. FWIW, estoy usando el SDK de Google Maps.
Mi problema es que es posible que el usuario dibuje un polígono con líneas que se intersectan por sí mismas (lo cual es un problema para lo que estoy haciendo). Necesito poder hacer una de 3 cosas.
- Eliminar los puntos de intersección en la matriz. (Cortar las piezas de la pajarita)
- Detectar si mis puntos tienen esta corbata de lazo (solo les diré que vuelvan a dibujar un nuevo polígono)
- Si es posible (lo cual no creo que sea), evite que el camino dibuje la pajarita en primer lugar.
Principalmente veo la pajarita cuando el polígono mismose cierra y el punto final está ligeramente por debajo del punto inicial. Entonces, cuando el polígono se cierra y se convierte en coordenadas del mapa en el mapa, obtengo una pequeña corbata de lazo que ensucia con una API interna.
¿Hay algo por ahí que funcione usandocoordenadas del mapa? He visto algunas correcciones para los CGPoints regulares, pero nada que tome las coordenadas del mapa. Preferiría hacer esta verificación en mi polígono después de que haya pasado por mi reductor, ya que deja muchos menos puntos por revisar. El rendimiento es un problema, y preferiría no recorrer cientos de puntos directamente provenientes de UIBezierPath. Cualquier ayuda sería apreciada.
Respuestas
1 para la respuesta № 1No conozco el SDK de Google Maps o elUIBezierPath. Supongo que se le da un polígono en el plano 2D y le gustaría detectar automáticamente dónde se interseca el polígono (si lo hace).
Quizás la forma más fácil de hacer esto es comprobando todas Parejas de aristas ya sea que se crucen o no. Puede comprobar esto en O (n2) tiempo donde n es el número de bordes, ya que hay n * (n-1) / 2 pares de bordes. Para un par de bordes dados, aquí están los detalles de cómo hacerlo:
Nada extraordinario pero los detalles requieren atención.
Un algoritmo más sofisticado es el algoritmo de barrido de plano:
Intersección de segmento de línea, comenzando en la diapositiva 25
Intersección de segmento de línea usando un algoritmo de línea de barrido