triángulo más grande de un conjunto de puntos

Question

Duplicar posibles:
How to find largest triangle in convex hull aside from brute force search

Tengo un conjunto de puntos aleatorios de la que quiero encontrar el mayor triángulo por área que es vértices son cada en uno de esos puntos

Hasta ahora he descubierto que las verticies del triángulo más grande solo se encontrarán en los puntos exteriores de la nube de puntos (o el casco convexo) así que he programado una función para hacer eso (usando Graham scan in nlogn time)

Sin embargo, ahí es donde estoy atascado. La única manera en que puedo encontrar la manera de encontrar el triángulo más grande a partir de estos puntos es usar fuerza bruta en n^3 veces, lo cual es aceptable en un caso promedio ya que el algoritmo de casco convexo generalmente arroja la gran mayoría de los puntos. Sin embargo, en el peor de los casos en que los puntos están en un círculo, este método fallaría miserablemente.

Dosis ¿Alguien sabe un algoritmo para hacer esto de manera más eficiente?

Nota: Sé que CGAL tiene este algoritmo allí pero no entran en detalles sobre cómo se hace. No quiero usar bibliotecas, quiero aprender esto y programarlo yo mismo (y también permitirme modificarlo exactamente de la manera que quiero que funcione, al igual que el escaneo Graham en el que otras implementaciones recogen puntos colineales que no quiero).

Answer 1

En la parte superior de mi cabeza, ¿quizás podrías hacer algo que implique grillar/dividir la colección de puntos en grupos? Tal vez ... separar los puntos en tres grupos (aunque no estoy seguro de cuál sería la mejor manera de hacerlo en este caso), hacer algo para descartar esos puntos en cada grupo que están más cerca de los otros dos grupos que otros puntos en el mismo grupo, y luego usar los puntos restantes para encontrar el triángulo más grande que se puede hacer teniendo un vértice en cada grupo? Esto realmente haría que el caso de todos los puntos que están en un círculo sea mucho más simple, porque solo te centrarías en los puntos que están cerca del centro de los arcos contenidos dentro de cada grupo, ya que esos serían los de cada grupo más alejado de los otros dos grupos.

No estoy seguro si esto le daría el resultado correcto para ciertos triángulos/distribuciones de puntos, sin embargo. Puede haber situaciones en las que el triángulo resultante no sea del área óptima, ya sea porque la agrupación y/o la elección del vértice no son/no son óptimas. Algo como eso.

De todos modos, esos son mis pensamientos sobre el problema. Espero que al menos haya podido darte ideas sobre cómo trabajar en ello.

Answer 2

Aquí hay un pensamiento sobre cómo bajarlo a O (n log n). Realmente no sé nada sobre geometría computacional, así que lo marcaré wiki comunitario; Por favor, siéntete libre de mejorar esto.

Preprocesar el casco convexo encontrando para cada punto el rango de pendientes de las líneas a través de ese punto, de modo que el conjunto quede completamente en un lado de la línea. A continuación, invierta esta relación: construya un árbol de intervalos para pendientes con puntos en nodos hoja, de modo que al consultar con una pendiente encuentre los puntos de tal manera que haya una tangente a través de esos puntos.

Si no hay conjuntos de tres o más puntos colineales en el casco convexo, hay como máximo cuatro puntos para cada pendiente (dos en cada lado), pero en el caso de los puntos colineales podemos ignorar los puntos intermedios.

Ahora, recorra todos los pares de puntos (P, Q) en el casco convexo. Queremos encontrar el punto R tal que el triángulo PQR tenga el área máxima. Tomando PQ como la base del triángulo, queremos maximizar la altura encontrando R tan lejos de la línea PQ como sea posible. La línea que pasa por R paralela a PQ debe ser tal que todos los puntos estén en un lado de la línea, de modo que podamos encontrar un número limitado de candidatos en el tiempo O (log n) usando el árbol de intervalos preconstruido.

Para mejorar esto aún más en la práctica, realice una bifurcación en el conjunto de pares de puntos: encuentre un límite superior para la altura de cualquier triángulo (por ejemplo, la distancia máxima entre dos puntos) y descarte cualquier par de puntos cuya distancia multiplicada por este límite superior es menor que el triángulo más grande encontrado hasta ahora.

Answer 3

Creo que el método rotating calipers puede aplicar aquí.

Answer 4

¿Qué tal si cae un punto a la vez desde el casco convexo? Comenzando con el casco convexo, calcule el área del triángulo formado por cada triple de puntos adyacentes (p1p2p3, p2p3p4, etc.). Encuentra el triángulo con área mínima, luego suelta el medio de los tres puntos que formaron ese triángulo. (En otras palabras, si el triángulo de área más pequeño es p3p4p5, suelte P4.) Ahora tiene un polígono convexo con N-1 puntos. Repite el mismo procedimiento hasta que te queden tres puntos. Esto debería tomar O (N^2) tiempo.

No me sorprendería en absoluto si hay algún caso patológico donde esto no funcione, pero espero que funcione para la mayoría de los casos. (En otras palabras, no he probado esto, y no tengo ninguna fuente para citar.)

Answer 5

No sé si esta ayuda, pero si elige dos puntos del casco convexo y gira todos los puntos del casco de modo que la línea de conexión de los dos puntos es paralela al eje x, ya sea el punto con el máximo o el que tiene la coordenada y mínima forma el triángulo con el área más grande junto con los dos puntos elegidos primero.

Por supuesto, una vez que haya probado un punto para todas las líneas de base posibles, puede eliminarlo de la lista.