analizador lexico

Geometría Computacional
La geometr´ computacional es una rama de ciencia de la computaci´n que
ıa
o
estudia algoritmos para resolver problemas geom´tricos.
e
Nos concetraremos en la representaci´n y programaci´n de algunos objetos y
o
o
algoritmos en el plano cartesiano.
Un punto s´lo tiene posici´n y se representa con un par de coordenadas (x, y).
o
o
Una l´
ınea est´ definida portodos los puntos que satisfacen la ecuaci´n
a
o
ax + by + c = 0.
Formas alternativas de escribir la ecuaci´n:
o
y = mx + n,
donde m se conoce como la pendiente de la recta, y (0, n) es un punto de la
recta.
Jorge Baier Aranda, PUC

68

La misma ecuaci´n se puede escribir dado un punto (x1, y1) y la pendiente:
o
y − y1 = m(x − x1).
Dado dos puntos (x1, y1) y (x2, y2), la ecuaci´nes:
o
y1 − y2
(x − x1).
y − y1 =
x1 − x2
o
(y2 − y1)x + (x1 − x2)y + x2y1 − x1y2 = 0.
Tambi´n es frecuente escribir la ecuaci´n de la forma
e
o
x y
+ = 1,
a b
donde (a, 0) y (0, b) son puntos de la recta.
El punto de intersecci´n de dos rectas l1 : y = m1x + n1 y l2 : y = m2x + n2 es
o
n2 − n1
n2 − n1
, m1
+ n1
m1 − m2
m1 − m2
Jorge Baier Aranda, PUC

69

El ´ngulo queforman dos rectas no paralelas l1 : a1x + b1y + c1 y l2 : a2x +
a
b2y + c2 = 0 est´ dado por
a
a1b2 − a2b1
arctan
a1a2 + b1b2
en caso de usar rectas con pendientes, el ´ngulo es el siguiente:
a
1
Si m es la pendiente de una recta, entonces − m es la pendiente de una recta
perpendicular a ella.

Jorge Baier Aranda, PUC

70

Segmentos, vectores y producto cruz
Un segmento es unsubconjunto de una l´
ınea recta comprendido entre dos
puntos de ella.
Un vector es un segmento dirigido entre el origen y un punto del plano. Si
p0 = (0, 0) y p1 = (x, y), entonces usamos la notaci´n p1 (o simplemente p1)
o
para hablar del segmento dirigido − →.
p− 1
0p

Jorge Baier Aranda, PUC

71

El producto cruz entre dos vectores p1 = (x, y) y p2 se define por
x1 x2
y1 y2

p1 ×p2 =

y representa el ´rea (con signo) del paralel´gramo de la figura.
a
o
y
p1 + p2
p1

sentido
horario

p2
x

Si p1 est´ en sentido horario desde p2 con respecto al origen, entonces p1 × p2 >
a
0.
Si p1 × p2 = 0, entonces p1 y p2 son colineales con el origen.
Jorge Baier Aranda, PUC

72

Pregunta: ¿c´mo determinar si al recorrer los segmentos p0p1 y p1p2, desde p0
o
sedebe doblar a la izquierda o a la derecha?
p
a
p−
p
Respuesta: el giro ser´ a la izquierda ssi − → est´ en sentido horario desde − →,
a
p−
1 2

1 0

es decir, ssi
(p2 − p1) × (p0 − p1) > 0

Jorge Baier Aranda, PUC

73

Intersección de dos segmentos
Es muy sencillo usar el producto cruz para determinar si dos segmentos se
intersectan.
La prueba se realiza en dos fases. En laprimera (rechazo r´pido) se revisa si los
a
rect´ngulos m´s peque˜os que contienen a los segmentos se intersectan.
a
a
n
Si tenemos un segmento p1p2 (con p1 = (x1, y1), p2 = (x2, y2), entonces el
rect´ngulo m´s peque˜o que lo contiene es el de esquina inferior izquierda
a
a
n
pI = (xI , yI ),
donde xI = m´
ın{x1, x2} y yI = m´ 1, y2}, y de esquina superior derecha
ın{y
pS = (xS , yS),
donde xS = m´x{x1, x2} y yS = m´x{y1, y2}.
a
a
Jorge Baier Aranda, PUC

74

Dos rect´ngulos, representados por sus esquinas superior derecha e inferior
a
izquierda, (p1 , p1 ) y (p2 , p2 ), se intersectan ssi
I S
I S
1 2
(m´
ın{x1 , x2 } ≥ m´x{x1 , x2 }) ∧ (m´ S , yS } ≥ m´x{yI , yI })
a
ın{y 1 2
a
S
S
I
I

Jorge Baier Aranda, PUC

75

La segunda fase consiste endetermiar si los extremos del primer segmento quedan
a lados opuestos del primero y vice versa. Esto se puede hacer f´cilmente usando
a
el producto cruz.
Mirando la siguiente figura:
p3
p2

p4
p1

Sabemos que para que los extremos de p3p4 queden a lados diferentes de p1p2,
se tiene que dar que p3 − p1 y p4 − p1 est´n en sentidos horarios distintos con
e
respecto a p2 − p1.
As´...