Download - Geometría Computacional
-
Geometra para ICPC Producto vectorial Convex hull (cpsula convexa)
Polgonos cncavos y convexos Algoritmo de Graham
Superficie polgono Cncavos y convexos Teorema de Pick
Point in Poly (Es un punto interior a un pligono?) Par de puntos ms cercano Tcnicas de sweep line (barrido)
Mximo rectngulo sin puntos adentro Interseccin de segmentos Par de puntos mas cercano Unin de intervalos y rectngulos
-
Producto vectorial
u=ux , u y v=v x , v y
uv=uxv yu yv x=det ux u yv x v y =uvsen=vu Producto vectorial de 2
-
Producto vectorial
u=ux , u y v=v x , v y
uv=uxv yu yv x=det ux u yv x v y =uvsen=vu Producto vectorial de
El valor absoluto es el area del paralelogramo El signo es la orientacin de los vectores
2
-
Cncavo o convexo? Definicin: un polgono P es convexo sii
Convex hull
A ,BP ABP
-
Cncavo o convexo? Si hay dos giros distintos es cncavo
Convex hull
-
Convex hull Recorriendo los vrtices en orden:
Mismos sentidos de giro Es convexo
-
Convex hull La verificacin de convexidad es O(n)
booleanisConvex(intn,int[]x,int[]y){intpos=0,neg=0;for(inti=0;i
-
Convex hull Para practicar: The art gallery
http://acm.uva.es/problemset/v100/10078.html
Decidir si existe algn punto en un polgono desde el cual no se pueda ver el polgono completo
-
Convex hull
Problema: encontrar la cpsula convexa de un conjunto de puntos
Entrada: Un conjunto de puntos en el plano Salida: El pligono convexo mas pequeo que
los contiene a todos
-
Convex hull
Algoritmo de Graham http://en.wikipedia.org/wiki/Graham_scan El punto ms abajo (y ms a la izquierda)
seguro est en la convex hull Este punto se puede
encontrar en O(n)
-
Convex hull
Algoritmo de Graham http://en.wikipedia.org/wiki/Graham_scan Ordernar en sentido anti-horario (y por distancia)
respecto de este punto O(n.log(n)) Invariante: en el paso i, se tiene
la convex hull de los
primeros i puntos
arreglados en una pila
-
Convex hull
Algoritmo de Graham http://en.wikipedia.org/wiki/Graham_scan El prximo siempre est en la convex hull
parcial, as que lo agregamos a la pila Si la convex
hull parcial est
en la pila
uv0
-
Convex hull
Algoritmo de Graham http://en.wikipedia.org/wiki/Graham_scan Mientras se saca el ante-ltimo de la
pila Esta ltima parte
es O(n)
uv0
-
Convex hull
Para practicar Onion layers (sam06, live archive: 3655)
http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3655
Not too Convex hull (sam02, live archive: 2615) http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2615
-
Superficie de polgono
Dado un polgono, calcular su superficie Si es convexo Se triangula desde un vrtice cualquiera
Se suman los productos vectoriales y se divide por 2 el valor absoluto
S= v1v 2 v2v 3 v3 v4 v4v52
-
Superficie de polgono
Dado un polgono, calcular su superficie Y si es cncavo?
-
Superficie de polgono
Dado un polgono, calcular su superficie Y si es cncavo?
-
Superficie de polgono
Dado un polgono, calcular su superficie Es lo mismo!
-
Superficie de polgono
Para polgonos con coordenadas enterasI = puntos en el interior
B = puntos en el borde
S = superficie
Teorema de PickS = I + B 2 1I = S B 2 + 1(Se puede probar por induccin
en la superficie)
-
Superficie de polgono
Calcular el borde usando m.c.d. Algoritmo O(n)intborder(intn,int[]x,int[]y){intb=0;for(inti=0;i
-
Superficie de polgono
Para practicar Jacquard circuits (wf07, live archive: 2395)
http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2395
-
Point in Poly
Problema: Decidir si un punto es interior a un polgono
Entrada: Un punto y un polgono Salida: Si o no Complejidad: O(n)
-
Point in Poly
Idea: Contar la cantidad de veces que corta
al polgono un rayo que parte del punto Si es par: est afuera Si es impar: est adentro
-
Point in Poly Hay varios casos que tener en cuenta
-
Point in Poly Hay varios casos que tener en cuenta
As se deben considerar
-
Point in Poly Primer condicin: un vrtice tiene que estar
estrictamente arriba del rayo y el otro abajo o sobre l
-
Point in Poly Segunda condicin: el giro sobre el vrtice
inferior, desde el punto hasta el vrtice superior tiene que ser anti-horario
-
Point in Poly El cdigo no es tan largo como la explicacinT:int/double
boolpnpoly(intn,T[]xs,T[]ys,Tpx,Tpy){inti,c=0;for(inti=0;iys[sup])swap(inf,sup);if(ys[inf]
-
Par de puntos ms cercano
Entrada: Conjunto de puntos Salida: Par de puntos mas cercano
-
Par de puntos ms cercano
Idea: Divide & Conquer O(n.log(n)) Se necesitan ordenados vertical y horizontalmente Divide: a la mitad ordenados por x. En O(n') tambin
se calcula el orden vertical de cada parte
d = min(di, dd)
-
Par de puntos ms cercano
Conquer: un punto de cada lado, estn includos en la franja con distancia horizontal menor o igual a d del corte
Se calcula en O(n') ordenados verticalmente
-
Par de puntos ms cercano
Se chequea cada punto con los que estn a abajo a distancia vertical
-
Par de puntos ms cercano
doubleclosest_recursive(VPvx,VPvy){if(vx.size()==1)return1e20;//infinityif(vx.size()==2)returndist(vx[0],vx[1]);pointcut=vx[vx.size()/2];VPvxL=filter(vx:x
-
Barrido > Mayor rectngulo sin puntos adentro
Entrada: Ancho, alto, conjunto de puntos Salida: Rectngulo con lados paralelos a los
bordes, sin puntos adentro, con la mayor area posible
-
Barrido > Mayor rectngulo sin puntos adentro
Cada lado del rectngulo tiene un punto o est sobre el borde
En particular el lado izquierdo
-
Barrido > Mayor rectngulo sin puntos adentro
Para cada punto se busca el mejor rectngulo cuyo lado izquierdo est sobre l.
El lado derecho puede estar en otro punto a la derecha o sobre el borde derecho
Para cada punto, se
iteran los otros puntos
de izquierda a derecha Se calculan techo y
piso (en rojo) Un punto a la
misma altura parte
la bsqueda en dos
-
Barrido > Mayor rectngulo sin puntos adentro
Tambin se busca el mejor rectngulo que tenga el lado izquierdo sobre el borde izquierdo
Si la cantidad de puntos no es cero, algn otro lado del rectngulo tiene que contener un punto (x, y), entonces se puede encontrar con el
procedimiento anterior
sobre (0, y) Si no hay puntos
entonces el mejor
rectngulo es todo
el borde En total es O(n)
-
Barrido > Mayor rectngulo sin puntos adentro
Para practicar Secure Region (sam03, live archive: 2882)
http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2882
Chainsaw massacre (eur-sw00, live archive: 2204)http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2204
-
Barrido > Interseccin de segmentos
Entrada: Conjunto de segmentos Salida: Todas las intersecciones de segmentos Algoritmo de BentleyOttman: O(n.log(n+i))
-
Barrido > Interseccin de segmentos
Barrido: Cola de eventos en x: vrtices e intersecciones Los eventos de interseccin se van agregando (priority queue) Se mantiene la lista de segmentos que cruzan el barrido ordenados verticalmente,
esta lista se actualiza en cada evento Se necesita una funcin que calcule interseccin de segmentos
-
Barrido > Interseccin de segmentos
En los vrtices que comienzan: Se agrega el segmento en la lista. Considerando la posicin y de cada segmento en la lista sobre la x del evento. Se necesita una estructura eficiente que soporte esto.
En los vrtices que terminan: Se remueve el segmento de la lista
En las intersecciones: Se intercambian los segmentos de lugar en la lista
En todos los casos se chequan por nuevas intersecciones entre nuevos vecinos en la lista y se agregan a la cola de eventos si no estn presentes
-
Barrido > Interseccin de segmentos
Complicaciones a tener en cuenta Segmentos que se superponen: Considerarlos juntos en la lista de
segmentos Vrtices sobre otros segmentos: Agregar el vrtice y la interseccion a
la cola de eventos, para que luego queden en el orden correcto Segmentos verticales: puede ser un evento especial Multiples intersecciones en un mismo punto: hay que diferenciarlas en
la cola de eventos
-
Barrido > Interseccin de segmentos
Para practicar Painter (wf09, live archive: 4125)
http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4125
-
Barrido > Par de puntos ms cercano
Se barren los puntos en sentido horizontal
Durante el barrido se mantiene:
El par de puntos ms cercano encontrado y su distancia h
La franja de todos los puntos a distancia horizontal menor a h del barrido ordenados verticalmente
Por cada punto:
se agrega a la franja respetando el orden vertical O(log(n))
se chequea para abajo y arriba contra los otros puntos sobre la franja a distancia vertical menor a h. Es O(1) como en el D&C
se sacan los puntos que quedaron fuera de la nueva franja
En total es O(n.log(n))
-
Barrido > Unin de intervalos Unin de intervalos
Dada una lista de intervalos de la recta real [a,b] Calcular el tamao de su unin
Se recorren los extremos de los intervalos de izquierda a derecha calculando la cantidad de intervalos abiertos
intlength(intn,double[]a,double[]b){vectorv;for(inti=0;i
-
Barrido > Unin de rectngulos Dado un conjunto de rectngulos, calcular el area de su unin
El barrido se hace recorriendo los lados derecho e izquierdo de los rectngulos, en sentido horizontal
Durante el barrido se mantiene la lista de intervalos que representan a los rectngulos sobre esa linea vertical.
Los intervalos se mantienen ordenandos verticalmente Cada lado izquierdo agrega un intervalo y su lado derecho lo saca O(n.log(n))
En cada paso se calcula la unin de estos intervalos y se multiplica por la distancia entre eventos. Como estn ordenados es O(n)
En total es O(n.log(n)) y se puede lograr en O(n.log(n))
-
Fin!
;-)
Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47