Volviendo al asunto de determinar si un punto está dentro de un triangulo, ya sabemos que el área de los 3 triangulos que forman el punto con los lados del triangulo debe ser todos del mismo signo. El sentido antihorario de los vértices asegura el valor positivo.
Siendo estrictos diriamos que la suma de áreas de los 3 triángulos debe ser igual al área del triángulo que contiene al punto. Recalco que no es necesario calcular exactamente las áreas sino solo su signo.
En la figura siguiente se muestra las regiones en las que puede estar un punto respecto a un triángulo y nos sirve para entender lo que vamos a explicar:
Sea p el punto del cual queremos saber si está dentro del triangulo 0-1-2, la prueba requiere suponer que dicho punto está dentro del triangulo y por lo tanto se formarán los 3 triangulos siguientes:
- p-0-1
- p-1-2
- p-2-0
Si el punto está en la región B, el triángulo p-0-1 será negativo
Si el punto está en la región C, el triángulo p-1-2 será negativoPara comprobar lo dicho basta con verificar el cambio de sentido de los triangulos en cada una de las regiones, así se podrá ver que en las regiones intermedias AB, BC y CA son 2 los triángulos que cambian su sentido.
Por lo tanto, para los efectos que nos demanda el algoritmo es posible hacer el código de manera que podemos no solo saber si un punto está dentro de un triangulo sino que podemos saber de que lado del triangulo se encuentra.
Entonces esto justifica sostener que el registro de cada triangulo debe contener los vértices que lo conforman y tambien los triangulos que son vecinos a él. Por ejemplo en la siguiente figura se muestra con fondo ámbar la numeración de triángulos y con fondo transpartente la numeración de vértices.
Los indices que numeran los vértices son los que corresponden al arreglo o lista de puntos con sus coordenadas. Para los triangulos adoptamos la siguiente forma de describirlo: (para el triangulo 6)
( (10 9 8) 8 9 7)
esta es una lista de 4 elementos, el primer elemento: (10 9 8) es el triángulo principal descrito con los vértices 10, 9 y 8, y los otros tres números representan los indices de los triángulos vecinos ordenados de modo que, para el ejemplo: el triangulo 8 es opuesto al vértice 10, el triangulo 9 es opuesto al vértice 9 y el triángulo 7 es opuesto al vértice 8. Estos tres últimos triángulos sons vecinos y obviamente tienen como arista común los lados 8-9, 10-8 y 9-10 respectivamente.
De acuerdo a la forma adoptada para referirnos a cada triangulo, resulta mas sencillo extraer datos del triangulo principal desde CAR y los identificadores del "vecindario" desde CDR. El tipo de registro presentado es de 4 triangulos.
Con este escenario es posible escribir el código para mejorar el algoritmo de triangulación en los puntos más cruciales:
- hallar el triangulo que contiene un nuevo punto lo más rapido posible
- efectuar la legalización de los nuevos triángulos determinando inmediatamente los triángulos "vecinos" o los que tienen una arista común.
La siguiente figura ilustra el proceso que sigue la busqueda del triángulo que contiene a un punto p que se suministra al código.
Si el proceso de verificación se inicia en el triangulo 0, la verificación indica que el siguiente triángulo a revisar es el 1, la verificación en este indicará que debe evaluarse el triangulo 2, y así hasta llegar al triángulo de color verde en donde al verificar se encontrará que es el triangulo buscado.
Una vez hallado el triangulo contenedor se descompone en 3 triángulos "hijos" y se actualiza su relación con el "vecindario" del triangulo original. Esto quiere decir que debe registrarse en los triángulos vecinos a los nuevos hijos ("herederos" del espacio del triangulo original). Algo similar ocurre cuando se hace el "flip" que legaliza 2 triangulos, se produce un cambio en la relación de los "vecinos" con los triangulos "flipeados" que debe quedar registrado.
El mecanismo detallado para automatizar estas operaciones es algo engorroso de explicar. Es muy importante mantener algún patrón de numeración de vértices, hecho que facilitará algunas operaciones.
Este cuadro se muestra ejecutando el comando PUNTOS
De acuerdo a la forma adoptada para referirnos a cada triangulo, resulta mas sencillo extraer datos del triangulo principal desde CAR y los identificadores del "vecindario" desde CDR. El tipo de registro presentado es de 4 triangulos.
Con este escenario es posible escribir el código para mejorar el algoritmo de triangulación en los puntos más cruciales:
- hallar el triangulo que contiene un nuevo punto lo más rapido posible
- efectuar la legalización de los nuevos triángulos determinando inmediatamente los triángulos "vecinos" o los que tienen una arista común.
La siguiente figura ilustra el proceso que sigue la busqueda del triángulo que contiene a un punto p que se suministra al código.
Si el proceso de verificación se inicia en el triangulo 0, la verificación indica que el siguiente triángulo a revisar es el 1, la verificación en este indicará que debe evaluarse el triangulo 2, y así hasta llegar al triángulo de color verde en donde al verificar se encontrará que es el triangulo buscado.
Una vez hallado el triangulo contenedor se descompone en 3 triángulos "hijos" y se actualiza su relación con el "vecindario" del triangulo original. Esto quiere decir que debe registrarse en los triángulos vecinos a los nuevos hijos ("herederos" del espacio del triangulo original). Algo similar ocurre cuando se hace el "flip" que legaliza 2 triangulos, se produce un cambio en la relación de los "vecinos" con los triangulos "flipeados" que debe quedar registrado.
El mecanismo detallado para automatizar estas operaciones es algo engorroso de explicar. Es muy importante mantener algún patrón de numeración de vértices, hecho que facilitará algunas operaciones.
Utilidad
La triangulación de una nube de puntos tiene una aplicación práctica en la ingeniería civil para la determinación de un modelo digital del terreno (MDT). Los puntos del terreno resultan del levantamiento topográfico o de algun otro proceso. El MDT es la base sobre la que se automatizan algunas operaciones que asisten al diseño de ingeniería.
Hace no mucho compartí en algunos foros especializados un compilado de utilidades para operaciones de topografía en gabinete que contiene como elemento principal una implementación de la triangulación de la nube de puntos tal como fue expuesta aquí, una versión recompilada puede obtenerse en el siguiente enlace:
una vez cargado el archivo en el Autocad se tendrán disponibles unos comandos entre los que se destaca los siguientes:
- importar registros de puntos de txt
- generar la triangulación como 3dface y lineas tin
- dibujo de las curvas de nivel
algunas de sus interfaces se presentan con las siguientes vistas:
Este cuadro se muestra ejecutando el comando REUBIK
Este cuadro se muestra ejecutando el comando CONF-MDT
Una vez cargados los puntos se utiliza el comando TIN que pedirá seleccionar en pantalla el conjunto de puntos a triangular.
las curvas de nivel se dibujan como lineas rectas para cada triángulo, cuando sea necesario se puede usar el comando SUAVIZA para obtener un suavizado de las curvas de nivel, sobre las curvas maestras se escribirán las cotas en que se encuentran.
Con la triangulación ya es posible aplicar herramientas propias del diseño en ingeniería. Donde más se aprovecha es en el diseño vial de carreteras o caminos ya que se facilitan los cálculos de movimientos de tierras entre otras operaciones.
Tambien trataremos el desarrollado de un conjunto de herramientas para el diseño geométrico.
Tambien trataremos el desarrollado de un conjunto de herramientas para el diseño geométrico.