Dados los puntos a y by un conjunto de puntos P, ¿cómo se puede encontrar el triángulo más grande con vértices a, byp que no contenga ningún punto en P?

Answer 1

Puede obtener un método bastante eficiente al examinar los ángulos de cada punto.

Suponga que a = (0,0) yb = (1,0). Para cada punto [matemática] p = (x, y) [/ matemática] calcule [matemática] p_ \ theta = atan2 (y, x) [/ matemática] y [matemática] p_ \ phi = atan2 (x, 1-y )[/matemáticas]. Estos son los dos ángulos base del triángulo.

Defina un buen triángulo con vértice p , para que sea uno que no contenga ningún otro punto. La condición para esto es que no hay otro punto q tal que [matemática] q_ \ theta <p_ \ theta [/ matemática] y [matemática] q_ \ phi <p_ \ phi [/ matemática]. Nuestra solución será el buen triángulo con el valor y más alto. Si trazas θ y φ obtienes un gráfico como

Los triángulos buenos están marcados en verde, los malos en rojo. Tenga en cuenta que para cada triángulo bueno no hay ningún punto a la izquierda del punto y debajo del punto. A medida que nos movemos de izquierda a derecha, todos los triángulos buenos tienen valores de lower más bajos.

Podemos encontrar los triángulos buenos ordenando primero los puntos por el valor θ. El triángulo con el lowest más bajo debe ser un triángulo bueno y este se convierte en nuestro triángulo bueno actual C y también en el triángulo máximo M. Ahora recorra los puntos ordenados:

• si la coordenada point del punto es mayor que la del triángulo bueno actual, contendrá C.
• si la coordenada point del punto es menor que la del triángulo bueno actual, se convierte en el triángulo bueno actual. Registre el valor y de esto y si es mayor que para M, el triángulo se convierte en nuestra nueva M.

Esto puede ser simplemente codificado

// Ordenar los puntos por su valor th
points.sort (function (p, q) {return p.th – q.th;});
maxindex = 0; // índice del triángulo más grande
maxy = 0; // valor y del triángulo más grande
lastphi = 10; // valor phi del último triángulo bueno

for (var j = 0; j <n; ++ j) {// recorrer puntos
if (puntos [j] .phi <lastphi) {// valor phi más bajo
lastphi = puntos [j] .phi; // se convierte en el nuevo triángulo bueno actual
puntos [j] .bueno = verdadero; // marca como un buen triángulo
if (puntos [j] .y> maxy) {// es este el triángulo máximo
maxy = puntos [j] .y;
maxindex = j;
}
} else {// no es un buen triángulo
puntos [j] .bueno = falso;
}
console.log (puntos [j]);
}

Una carrera típica dará resultados como

con buenos triángulos marcados con vértices verdes y el más grande de estos triángulos rellenos.

Puede pensar en el algoritmo como barrer un rayo en sentido antihorario alrededor del vértice inferior izquierdo. cada vez que llegue a un punto, encuentre su valor φ y compárelo con el último valor bueno.

Puedes ver una versión interactiva en el triángulo máximo – JSFiddle

Creo que esta solución es básicamente la misma que la de Tadeusz Panda y la complejidad es O (n log n) la del algoritmo de clasificación.

Answer 2

Ese es un ejercicio interesante, ¿lo resolviste resolviendo algún problema tuyo o es de alguna fuente?

La suposición básica en la explicación será que hemos realizado los puntos 1 a 3 de la respuesta de Dave Consiglio, pero tenga cuidado de no hacerlos al codificar la solución, ya que los errores de redondeo de los valores reales después de la traducción pueden matarlo, si es un punto estaba exactamente en el borde del triángulo, después de la rotación, será aleatoriamente dentro o fuera, cambiando la respuesta correcta tanto como desee. La segunda suposición básica es que después de las rotaciones todos los puntos tienen y> 0, por supuesto, no cambia nada.

Entonces, ¿qué significa que a, b, p es un triángulo permitido? Esto significa que no debe haber más o menos que cada punto q en P debe estar a la izquierda de p en la lista de puntos en P, ordenados en ángulo por el punto a, o a la derecha de p en la lista de puntos en P, ordenados en ángulo por punto b , o ambos. Genial, entonces, ¿cómo verificar qué puntos están permitidos (obviamente, encontrar la respuesta será tiempo lineal)? Cree una matriz que esté indexada por el número del punto cuando P se ordena en ángulo por a y el valor es el número del punto en la clasificación por ángulo por b (por ejemplo, “matriz [5] = 3” significa que a el punto que se encuentra en la quinta posición cuando los puntos se ordenan por a es tercero cuando se clasifica por b). Y cuente el mínimo en los sufijos.

Entonces, ¿cómo sabemos si el punto responsable de la entrada de la matriz [i] está permitido? Sabemos que todos los puntos de la matriz [0] – matriz [i-1] no caen dentro del triángulo ya que quedan a la izquierda de nuestro punto cuando se ordenan por a. Y sabemos que la matriz [i] = k, por lo que este punto tiene el número k cuando se ordena por b. Entonces, si el mínimo en el sufijo i + 1 … n es menor que k, entonces hay un punto que estaba justo desde nuestro punto en la lista a (causa su índice> i) y se fue desde nuestro punto en la lista b (causa su valor es menor que k), de lo contrario no existe tal punto. Conclusión, el punto puede formar un triángulo si y solo si array [i]

Answer 3

No estoy seguro, pero aquí está mi proceso de pensamiento:

1. Defina el eje x como que contiene los puntos ay b.
2. Defina el eje y como que contiene el punto medio del segmento de línea ab.
3. Traduce todas tus coordenadas antiguas al nuevo sistema.
4. Cree una lista de puntos en P, ordenados de mayor a menor por la distancia perpendicular desde el punto prospectivo, p ‘, hasta la línea ab. Motivación: Esto está motivado por el hecho de que múltiples puntos p ‘podrían vivir a lo largo de una línea paralela a la línea ab. Cada uno de estos puntos forma un triángulo de igual área ya que todos comparten la misma base y tienen la misma altura. Si no vamos en orden desde la línea paralela más alejada, podríamos pasar por alto un punto p ‘que está más lejos del punto medio, pero tiene una altura menor que un punto que está más cerca del punto medio pero tiene una altura mayor.
5. Use este método Triangle Interior para determinar si todos los puntos posteriores en la lista ordenada están fuera del triángulo que contiene sus tres puntos.

Este algoritmo parece realmente ineficiente, pero debería funcionar. Si P es relativamente pequeño, lo analizará en poco tiempo.