ingeniero

Geometría Computacional
La geometr´ıa computacional es una rama de ciencia de la computaci´
on que
estudia algoritmos para resolver problemas geom´etricos.
Nos concetraremos en la representaci´
on y programaci´
on de algunos objetos y
algoritmos en el plano cartesiano.
Un punto s´
olo tiene posici´
on y se representa con un par de coordenadas (x, y).
Una l´ınea est´a definida por todoslos puntos que satisfacen la ecuaci´
on
ax + by + c = 0.
Formas alternativas de escribir la ecuaci´
on:
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´
on se puede escribir dado un punto (x1, y1) y la pendiente:
y − y1 = m(x − x1).
Dado dos puntos (x1, y1) y (x2, y2), la ecuaci´
on es:y1 − y2
(x − x1).
y − y1 =
x1 − x2
o
(y2 − y1)x + (x1 − x2)y + x2y1 − x1y2 = 0.
Tambi´en es frecuente escribir la ecuaci´
on de la forma
x y
+ = 1,
a b
donde (a, 0) y (0, b) son puntos de la recta.
El punto de intersecci´
on de dos rectas l1 : y = m1x + n1 y l2 : y = m2x + n2 es
n2 − n1
n2 − n1
, m1
+ n1
m1 − m2
m1 − m2
Jorge Baier Aranda, PUC

69

El ´angulo que forman dosrectas no paralelas l1 : a1x + b1y + c1 y l2 : a2x +
b2y + c2 = 0 est´a dado por
a1b2 − a2b1
arctan
a1a2 + b1b2
en caso de usar rectas con pendientes, el ´angulo es el siguiente:
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 un subconjunto de unal´ı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´
on p1 (o simplemente p1)
→
para hablar del segmento dirigido −
p−
0 p1 .

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 =

yrepresenta el ´area (con signo) del paralel´
ogramo de la figura.
y
p1 + p2
p1

sentido
horario

p2
x

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

72

Pregunta: ¿c´
omo determinar si al recorrer los segmentos p0p1 y p1p2, desde p0
se debe doblar a laizquierda o a la derecha?
p est´a en sentido horario desde −
p−→
p ,
Respuesta: el giro ser´a a la izquierda ssi −
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 la primera (rechazor´apido) se revisa si los
rect´angulos m´as peque˜
nos que contienen a los segmentos se intersectan.
Si tenemos un segmento p1p2 (con p1 = (x1, y1), p2 = (x2, y2), entonces el
rect´angulo m´as peque˜
no que lo contiene es el de esquina inferior izquierda
pI = (xI , yI ),
donde xI = m´ın{x1, x2} y yI = m´ın{y1, y2}, y de esquina superior derecha
pS = (xS , yS ),
donde xS = m´
ax{x1, x2} y yS =m´
ax{y1, y2}.
Jorge Baier Aranda, PUC

74

Dos rect´angulos, representados por sus esquinas superior derecha e inferior
izquierda, (p1I , p1S ) y (p2I , p2S ), se intersectan ssi
(m´ın{x1S , x2S } ≥ m´
ax{x1I , x2I }) ∧ (m´ın{yS1 , yS2 } ≥ m´
ax{yI1, yI2})

Jorge Baier Aranda, PUC

75

La segunda fase consiste en determiar si los extremos del primer segmento quedan
a ladosopuestos del primero y vice versa. Esto se puede hacer f´acilmente usando
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´en en sentidos horarios distintos con
respecto a p2 − p1.
As´ı, basta con chequear que:
((p3 − p1) × (p2 − p1))((p4 − p1) × (p2 −...