Algoritmo para encontrar si un conjunto de puntos describe un enveloppe convexa

Question

me gustaría comprobar si un conjunto de N puntos describir un polígono convexo o no

Me preguntaba si hay un buen algoritmo para eso?

Aquí es algunos enfoques que pensé:

algoritmo

---

1.Convex casco:

Si el conjunto es igual a su casco convexo entonces es convexa. La complejidad de dicho algoritmo es O (n * LN (N)). Pero tuve la sensación de que era como romper una mariposa en una rueda.

---

3.Looking en los ángulos:

Entonces pensé de comprobar si los ángulos de 2 vectores consecutivos nunca exceden de 180 °. Pero desde mis puntos no están ordenados Tengo que comprobar todas las combinaciones de 3 puntos consecutivos y eso hace como un O complejidad (n3). (No debe haber una manera de hacerlo mejor que eso)

Intento seleccionar puntos de derecha a izquierda, por ejemplo, pero los resultados no son siempre el esperado:

por ejemplo, en este caso me parece una forma convexa si tomo de izquierda a derecha:

Así, por esta Solución Necesitaré un buen algoritmo para seleccionar los puntos.

---

3. mirando el baricentro:

pienso que comprobar si el baricentro de todo el punto 3 es consecutivos dentro de la forma me dirá si la forma es convexa del no.

Aquí es lo que quiero decir (G es el baricentro de cada triángulo):

para esta solución que puede seleccionar los puntos de izquierda a derecha sin problemas. si la complejidad de verificar si G tiene la forma es O (N), entonces la complejidad global sería algo así como O (N2).

¿Me podría aconsejar sobre un buen algoritmo para resolver este problema o mejorar las soluciones que estoy pensando

Gracias de antemano

Answer 1

Si su entrada es un polígono simple, puede hacerlo en tiempo lineal, pero no es del todo obvio. Hay una larga historia de soluciones incorrectas a este problema que se puede leer en la página web:

http://cgm.cs.mcgill.ca/~athens/cs601/

Hoy en día, está ampliamente aceptado que la mejor manera simple/de resolver este problema es utilizar Melkman de algoritmo:

http://softsurfer.com/Archive/algorithm_0203/algorithm_0203.htm#Melkman%20Algorithm

Si usted no tiene un polígono simple, a continuación, en el peor de los casos es tan duro como el casco convexo regular (ya que sólo se puede tomar cualquier problema ordinaria casco convexo y conectar los puntos arbitrariamente para obtener un polígono sin sentido).

Answer 2

yo estaba pensando a partir de Wikipedia sobre Grahams Scan:

Do todo hasta e incluyendo "ordenar puntos por ángulo polar con puntos [1]".

a continuación:

for i = 3 to N: 
    if ccw(points[i-2], points[i-1], points[i]) < 0: # Note this inequality might need checking 
     return NotConvex 
return Convex 

Tanto la clasificación y el control de la convexidad se prestan bien a la paralelización y se podrían fusionar aún más para acelerar si es necesario.