![]() |
||||||
|
||||||
Punto interior de un triánguloEn muchas tareas de programación de gráficos, se necesita seleccionar y arrastrar un objeto geométrico. Para simplificar la discusión, supongamos que tenemos el siguiente problema: tenemos un triángulo (que se puede deformar arrastrando sus vértices) y queremos trasladarlo arrastrando el ratón sobre él. En el "programita" que sigue abajo, se puede arrastrar el triángulo con el ratón y también se puede deformar el triángulo arrastrando los vértices. Cada vez que hacemos clic dentro de la zona gris se despliega un punto rojo, excepto si hacemos clic en el interior del triángulo.
Para hacer la implementación necesitamos resolver tres problemas
Punto interior a un triánguloPara resolver el problema de decidir si el ratón esta sobre el triángulo, hacemos uso de algunas ideas del Algebra Lineal. Para esto consideremos un ángulo con un vértice v0, como se muestra en la figura que sigue.
v = v0 + a1v1 + a2v2
resolviendo para a1 y a2
obtenemos
donde
u Nota: La fórmula definida para vectores en dos dimensiones
u Es claro que si a1 > 0 y si a2 > 0, entonces v estará en el interior del ángulo con vértice en v0. De esta manera, v esta en el interior del triángulo si es interior a cada uno de los tres ángulos del triángulo. Por ejemplo, consideremos v0 = (0,0), v1 = (1,3) y v2 = (3,1). Si tomamos v = (1,1) entonces v = v0 + 0.25 v1 + 0.25 v2, así que como a1 = 0.25 > 0 y a2 = 0.25 > 0 entonces v está en el interior del ángulo Si tomamos w = (0,2) entonces w = v0 + 0.75 v1 - 0.25 v2, así que como a1 = 0.75 > 0 y a2 = - 0.25 < 0 entonces w está fuera del interior del ángulo
Este resultado se puede reformular en términos de orientación de
un triángulo. Este otro punto de vista nos permite formular un algoritmo sencillo
para resolver el primer problema. Orientación de tres puntosDecimos que tres puntos del plano tienen orientación nula si son colineales, en otro caso decimos que tres puntos A1, A2 ,A3 están orientados de manera positiva si para visitar estos tres puntos en el orden dado, nos movemos contra-reloj y que están orientados de manera negativa si para visitar estos tres puntos en el orden dado, nos movemos a favor del reloj.
La orientación del triángulo depende del
orden en que se especifican
u × v = (ux, uy, 0) × (vx, vy, 0) = (uxvy - uyvx)k La fórmula que resultó es natural ya que los tres puntos
están en el plano XY, por lo tanto el producto cruz es un vector en la
dirección del eje Z. Podemos usar el signo de la componente uxvy
- uyvx para definir la
orientación, así si
u entonces, la orientación es positiva si
u
Por ejemplo si A1 = (2,3), A2 = (3,5), A3 = (1,4) entonces Si u = A1 - A3 y v = A2
- A3 tendríamos u Si u = A3 - A1 y v = A2
- A1 tendríamos u Finalmente, decimos que el triángulo
|
||||||