Triangulación simple

propuesto por josejuan

Dada una lista de coordenadas (x, y) en el plano; obtener una triangulación de la forma más sencilla (quizás no eficiente) posible.

Enunciado
La única condición que se impone a la triangulación es que no haya intersección de aristas y que los puntos queden identificados.

Por ejemplo, para una entrada como la siguiente:

1. (0, 0)
2. (1, 0)
3. (1, 1)
4. (0, 1)

Una triangulación válida podría ser la lista:

[(1, 2), (1, 3), (1, 4), (2, 3), (3, 4)]

El plano es real (las coordenadas son números reales).
Preguntas sobre el desafío
  • ¿En que consiste triangulizar una lista de coordenadas de tamaño variable?. He buscado en la wikipedia y algo mas y lo unico que he encontrado es el calculo de la posicion de un punto conociendo la situacion de otros dos.

    http://en.wikipedia.org/wiki/Delaunay_triangulation

Plantea tu pregunta

3 Soluciones

Dar mi solución

0votos
Triangulación simple en C++
por

Antonio Martinez

usando OpenCV hace 6 años

Es un poco una trampa, el código no es mio, es un ejemplo de los que viene con OpenCV, yo solo lo he adaptado para que funcione en Mac OSx. El objetivo es animar a otros a usar la librería y ayudar en el caso de que quieran usarlo en OSx. Además aporta un ejemplo visual de qué es la triangulación.

0votos
Triangulación simple en Haskell
por

josejuan

hace 6 años

Creí que alguien se animaría, es fácil (y creo que divertido). No se han impuesto restricciones a la triangulación conseguida. Mi solución únicamente necesita una función que indique si dos segmentos de recta intersectan, nada más.

Dar mi solución