Tengo que hacer 2d triángulos de una lista de 2d puntos con una condición: la longitud de cualquier borde no puede ser más larga que una constante predefinida.Crear 2d triángulos a partir de 2d puntos
Algo como esto: 
¿Conoce cualquier algoritmo que puede hacer esto? O cualquier consejo?
Gracias!
Pruebe Delaunay triangulation, luego elimine los bordes demasiado largos.
Del artículo de arriba, ves un enlace a CGAL's 2D triangulation page.
Primero, genere todos los bordes posibles (es decir, conectando un par de vértices que están más cerca que la constante). Luego, cuando dos de ellos se cruzan, elimine uno de ellos. Repita este paso hasta que no haya intersecciones.
Esta solución es bastante primitiva, probablemente sea posible hacerlo más rápido.
me gusta la respuesta de svick -
en la aplicación que lo haría el siguiente
+1 para la triangulación de Delaunay. Esto forma intrínsecamente triángulos bien "equilibrados". Esto debería hacer un trabajo razonable de minimizar las posibilidades de bordes demasiado largos, pero no garantiza las longitudes de borde específicas. No creo que puedas eliminar bordes excesivamente largos, pero si hay un problema, parece poco probable (aunque no imposible) que haya una triangulación alternativa que funcione. El problema es que, incluso si es posible (no estoy seguro - mi geometría de cálculo está oxidada) probablemente sea difícil de encontrar. Puede ser una especie de triangulación de try-all-possible-thing. – Steve314