geometría computacional libro1

49
UNIVERSIDAD CENTRAL DEL ECUADOR Facultad de Ingeniería Ciencias Físicas y Matemáticas Geometría Computacional Integrantes: María José Cordero Oscar Viana Miriam Sánchez 2009-2010

Upload: geometriacomputacional

Post on 20-Jun-2015

1.644 views

Category:

Documents


4 download

DESCRIPTION

Tópicos de Geometría Computacional

TRANSCRIPT

Page 1: Geometría Computacional libro1

UNIVERSIDAD CENTRAL DEL ECUADOR

Facultad de Ingeniería Ciencias Físicas y Matemáticas

Geometría Computacional

Integrantes:

María José Cordero Oscar Viana

Miriam Sánchez

2009-2010

Page 2: Geometría Computacional libro1

Universidad Central del Ecuador

Geo

met

ría

Com

puta

cional

2

INDICE DE CONTENIDO

1 Introducción a la Geometría Computacional

1.1 ¿Qué es la Geometría Computacional?

1.2 Algunas Aplicaciones de la Geometría Computacional

1.3 Terminología

1.3.1.1 Recta

1.3.1.2 Rayo

1.3.1.3 Segmento

1.4 Familias Notables de Polígonos

1.4.1.1 Cadena Poligonal

1.4.1.2 Poligonal simple

1.4.1.3 Poligonal Cerrada

1.4.1.4 Curva de Jordán

1.4.1.5 Polígono Convexo

1.4.1.6 Polígono Estrellado

1.4.1.7 Núcleo de un Polígono

1.4.1.8 Polígono Débilmente Visible de un lado

1.4.1.9 Polígono Débilmente Visible desde el exterior

1.4.1.10 Polígono Monótono

1.5 Área Signada de un Triángulo

1.5.1.1 Aplicaciones del Área Signada

1.6 Área de un Polígono

2 Triangulación de Polígonos

2.1 Conjetura de Kleen

2.2 Tree Coloring 2.3 Diagonales y Triangulación 2.4 Triangulación Dual 2.5 Intersección entre Segmentos

3 Conjuntos Convexos

3.1 Cierre Convexo CH(S) 3.2 Soporte de S 3.3 Caracterizaciones para determinar la Envolvente Convexa 3.4 Marcha de Jarvis

3.4.1 Descripción Geométrica 3.4.2 Estudio de Complejidad 3.5 Scan Graham 3.5.1 Algoritmo de Graham

3.5.2 Análisis de Complejidad

Page 3: Geometría Computacional libro1

Universidad Central del Ecuador

Geo

met

ría

Com

puta

cional

3

1.1 Geometría Computacional

La Geometría Computacional es una disciplina que se ocupa del diseño y análisis de algoritmos que resuelven problemas geométricos.

La complejidad de un algoritmo no es sino una medida del coste que supone su ejecución tanto en tiempo (o número de operaciones “elementales” que ha de realizar) como en espacio (o unidades de memoria requeridas para almacenar y manipular los datos a lo largo de la ejecución) y vendrá dada en función del número de datos de entrada.

El estudio de la complejidad de un algoritmo puede llevarse a cabo principalmente

bajo dos puntos de vista:

Complejidad en el peor de los casos.

Complejidad en media (o esperada). La primera consiste en medir la complejidad del algoritmo atendiendo a su

ejecución cuando trata los datos del problema en el caso más desfavorable, entendiéndose por desfavorable el más costoso.

La segunda consiste en medir la complejidad haciendo un promedio entre todos

los casos (favorables y no favorables) atendiendo a la probabilidad de que aparezcan como entrada.

Para ello se supone que los datos de entrada vienen dados conforme a cierta

distribución de probabilidad y se estudia cual es el tiempo esperado de ejecución. 1.2 Aplicaciones de la Geometría Computacional

La primera generación va a ser la de los cálculos numéricos, aplicados sobre

todo a problemas científicos y técnicos. La segunda necesidad comercial y administrativa, incorporaba largas listas de datos (por ejemplo alfabéticos), con vistas a como leer, almacenar, modificar, seleccionar, e imprimir esos datos.

Todo esto naturalmente pervive, y con fuerza, pero vivimos una tercera generación de aplicaciones dominada por el procesamiento de información geométrica y gráfica, presente en áreas tan diversas como son la medicina, la cartografía, el control de robots o el diseño artístico. La Geometría Computacional ha emergido,

ciertamente, por la necesidad de dar respuesta a esta nueva y creciente demanda.

Dentro de los campos de aplicación más directamente relacionados con la disciplina destacaremos la Informática Gráfica, el Diseño y Fabricación Asistida por Ordenador (CAD/ CAM), la Caracterización y Reconocimiento Automático de Formas (Pattern Recognition), el Diseño VLSI, la visión Artificial, la Cartografía y la Robótica. 1.3 Terminología

El elemento geométrico más sencillo es el punto, que en el plano vendrá dado por un par ordenado de números reales, generalmente sus coordenadas cartesianas.

1.3.1 La recta que pasa por dos puntos, p; q, es el lugar geométrico de los puntos.

Page 4: Geometría Computacional libro1

Universidad Central del Ecuador

Geo

met

ría

Com

puta

cional

4

1.3.2 El rayo que emana de p y pasa por q es la semirrecta de puntos

1.3.3 El segmento de extremos p y q es el conjunto

Código en Matlab %función que dibuja un segmento entre 2 puntos

function seg = segmento2(A,B)

t = 0:0.01:1;

AB = B-A;

X1 = A(1)+t*AB(1);

Y1 = A(2)+t*AB(2);

hold on

plot(X1,Y1,'.');

end

1.4 Familias notables de polígonos

En la práctica se ha comprobado que determinados algoritmos que se ejecutan

sobre polígonos tienen un mejor rendimiento, en cuanto a velocidad, si el polígono de entrada tiene ciertas “buenas propiedades”. Otras veces, los problemas reales involucran polígonos con características especiales y resulta más fácil encontrar algoritmos que resuelvan esos problemas para dichos polígonos que para polígonos generales.

1.4.1 Cadena Poligonal

Un conjunto ordenado de n puntos distintos en el plano

determina una (cadena) poligonal que es la unión de los segmentos

. A estos segmentos se les llama lados y a sus extremos vértices de la poligonal. Lados adyacentes en una poligonal son aquéllos que son consecutivos en la lista ordenada de segmentos anterior.

1.4.2 Una poligonal simple es aquélla en la que dos lados, si se cortan, lo

hacen exactamente en uno de sus extremos y además son adyacentes.

1.4.3 Una poligonal cerrada determinada por es la unión de segmentos

.

Page 5: Geometría Computacional libro1

Universidad Central del Ecuador

Geo

met

ría

Com

puta

cional

5

1.4.4 Una poligonal cerrada simple determina una Curva de Jordan que divide

al plano en tres regiones:

1.- Interior a la curva 2.- Exterior a la curva 3.- La propia curva

Al conjunto de puntos de la región interior junto con los puntos de la poligonal

cerrada. El interior del polígono P, , es el conjunto de puntos de la región interior.

La frontera del polígono, ´o ∂P, es el conjunto de puntos de la poligonal cerrada simple. Y el exterior del polígono, , es el conjunto de puntos de la región exterior.

Código 1 de la poligonal en Matlab %función que dibuja una poligonal que recibe un Punto representado por

un vector

function pol = Poligonal(m)

n = input('ingrese número de puntos: ');

for i = 1: n

v = input('ingrese P(x,y): ');

for j = 1: 2

m (i,j) = v(j)

end

end

for k = 2: n

for j = 1: 2

p(j) = m(k-1,j);

q(j) = m(k,j) ;

r(j) = m(n,j);

s(j) = m(1,j);

end

segmento(p,q)

segmento(r,s)

end

end

Page 6: Geometría Computacional libro1

Universidad Central del Ecuador

Geo

met

ría

Com

puta

cional

6

Código 2 de la poligonal en Matlab

%función que dibuja una Poligonal cerrada.

function cadena = cadenaPol(a,nr)

%se ingresa una matriz (nrow,2)

for i = 2: nr

for j = 1: 2

d(j) = a(i-1,j);

e(j) = a(i,j) ;

f(j) = a(nr,j);

g(j) = a(1,j);

if j == 2

% se llama a la función segmento que lo grafica

segmento2(d,e)

segmento2(f,g)

text(d(1),d(2),'P')

text(e(1),e(2),'P')

end

end

end

end

Código en C#

//dibujamos las líneas del polígono con el mouse private void panel_screen_MouseUp(object sender, MouseEventArgs e)

{

if (e.Button == MouseButtons.Left)

{

Point p = new Point(e.X, e.Y);

puntos.Add(p);

status = prosess_status.DIBUJANDO;

}

else if (e.Button == MouseButtons.Right)

{

if (puntos.Count < 3)

{

MessageBox.Show("Debe seleccionar al menos 3

puntos");

return;

}

polygon = new Point[puntos.Count];

for (int i = 0; i < puntos.Count; i++)

polygon[i] = (Point)puntos[i];

Graphics g = panel_screen.CreateGraphics();

g.Clear(Color.White);

dibujarPoligono();

status = prosess_status.POLIGONOLISTO;

btnTriangular.Enabled = true;

}

}

//en este metodo dibujaremos

private void panel_screen_MouseMove(object sender,

MouseEventArgs e)

{

if (status == prosess_status.DIBUJANDO)

{

Point inicio, fin;

Graphics g = panel_screen.CreateGraphics();

Page 7: Geometría Computacional libro1

Universidad Central del Ecuador

Geo

met

ría

Com

puta

cional

7

g.Clear(Color.White);

inicio = (Point)puntos[0];

g.DrawLine(new Pen(Color.Yellow, 2), inicio.X - 6,

inicio.Y, inicio.X + 6, inicio.Y);

g.DrawLine(new Pen(Color.Yellow, 2), inicio.X,

inicio.Y - 6, inicio.X, inicio.Y + 6);

for (int i = 0; i < puntos.Count - 1; i++)

{

inicio = (Point)puntos[i];

g.DrawLine(new Pen(Color.Yellow, 2), inicio.X - 6,

inicio.Y, inicio.X + 6, inicio.Y);

g.DrawLine(new Pen(Color.Yellow, 2), inicio.X,

inicio.Y - 6, inicio.X, inicio.Y + 6);

fin = (Point)puntos[i + 1];

g.DrawLine(new Pen(Color.Yellow, 2), fin.X - 6,

fin.Y, fin.X + 6, fin.Y);

g.DrawLine(new Pen(Color.Yellow, 2), fin.X, fin.Y

- 6, fin.X, fin.Y + 6);

g.DrawLine(new Pen(Color.Blue, 2), inicio, fin);

}

inicio = (Point)puntos[puntos.Count - 1];

fin = new Point(e.X, e.Y);

g.DrawLine(new Pen(Color.Blue, 2), inicio, fin);

g.DrawLine(new Pen(Color.Yellow, 2), fin.X - 6, fin.Y,

fin.X + 6, fin.Y);

g.DrawLine(new Pen(Color.Yellow, 2), fin.X, fin.Y - 6,

fin.X, fin.Y + 6);

}

lbCoordenadas.Text = "X:" + e.X + " , Y:" + e.Y;

}

private void area()

{

int n = puntos.Count;

float area = 0;

for (int i = 1; i < n - 1; i++)

area = area + (((Point)puntos[i]).Y - ((Point)puntos[i

+ 1]).Y) * (((Point)puntos[i]).Y - ((Point)puntos[i + 1]).Y);

area = Math.Abs(area);

MessageBox.Show("El area es:" + area);

}

private void btnTriangular_Click(object sender, EventArgs e)

{

area();

}

private void btnLimpiar_Click(object sender, EventArgs e)

{

puntos.Clear();

polygon = null;

Graphics g = panel_screen.CreateGraphics();

g.Clear(Color.White);

btnTriangular.Enabled = false;

status = prosess_status.ESPERANDO;

}

public void dibujarPoligono()

Page 8: Geometría Computacional libro1

Universidad Central del Ecuador

Geo

met

ría

Com

puta

cional

8

{

if (polygon != null)

{

Graphics g = panel_screen.CreateGraphics();

for (int i = 0; i < polygon.Length; i++)

{

g.DrawLine(new Pen(Color.Yellow, 2), polygon[i].X

- 8, polygon[i].Y, polygon[i].X + 8, polygon[i].Y);

g.DrawLine(new Pen(Color.Yellow, 2), polygon[i].X,

polygon[i].Y - 8, polygon[i].X, polygon[i].Y + 8);

}

g.DrawPolygon(polygon_pen, polygon);

}

}

private void panel_screen_Paint(object sender, PaintEventArgs

e)

{

switch (status)

{

case prosess_status.ESPERANDO:

break;

case prosess_status.POLIGONOLISTO:

dibujarPoligono();

break;

default:

break;

}

}

Un polígono queda perfectamente determinado por el conjunto de sus vértices ordenados según aparecen al recorrer su frontera, y una orientación que nos permita conocer dónde queda su interior al recorrer su frontera. Así, si recorremos la frontera en sentido horario dejaremos el interior a nuestra derecha, en cambio si la recorremos en sentido anti horario lo dejaremos a la izquierda. Caben pues dos orientaciones posibles para recorrer la frontera: la negativa (horaria) y la positiva (anti horaria).

Salvo que se indique lo contrario, supondremos siempre que un polígono viene dado por una lista cíclica con sus vértices ordenados con orientación positiva. Y la

notaremos Simplemente , entendiendo que el siguiente a es . La estructura de datos más adecuada para representarla es la lista circular doblemente enlazada.

1.4.5 Un polígono P es convexo si para todo el segmento .

Polígono convexo Polígono no convexo: x e y no se ven

Esta propiedad de contener al segmento que une dos puntos admite una

interpretación curiosa en términos de visibilidad: se “ven interiormente” si

Page 9: Geometría Computacional libro1

Universidad Central del Ecuador

Geo

met

ría

Com

puta

cional

9

, o lo que es lo mismo . Análogamente se dice que se “ven

exteriormente” si .

1.4.6 Un polígono P es estrellado si existe un punto tal que para todo

el segmento . Es decir, existe un punto en P que ve interiormente a todo el polígono.

Polígonos estrellados Polígonos no estrellados

1.4.7 El núcleo de un polígono P , es el conjunto de puntos de P que

ven interiormente a P. Teorema

P es convexo si, y sólo si, , y

P es estrellado si, y sólo si, .

Si uno de los vértices del polígono está en el núcleo, entonces se dice que es un

abanico.

Estrellados y sus respectivos núcleos

1.4.8 Débilmente Visible desde un Lado (DVL)

Un polígono débilmente visible desde un lado es aquel en el que hay un lado l

del polígono tal que para cada punto y del polígono existe un punto que ve anteriormente a y.

Todo punto de P se ve desde algún punto de l, en particular desde x, x’, x’’ En términos de iluminación se interpreta de la siguiente manera. Para iluminar

el interior de un polígono estrellado basta colocar una bombilla en un punto de su núcleo, y para un débilmente visible desde un lado, bastaría con colocar una barra fluorescente a lo largo del lado l.

Page 10: Geometría Computacional libro1

Universidad Central del Ecuador

Geo

met

ría

Com

puta

cional

1

0

1.4.9 Débilmente Visible desde el Exterior (DVE)

Un polígono P débilmente visible desde el exterior, se abreviará DVE, es aquél

en el que para todo existe un rayo r que emana de x tal que r .

La interpretación en términos de visibilidad o vigilancia es la siguiente.

Supongamos que el polígono representa una fortaleza y un guardia patrulla a lo largo del muro exterior (la frontera). Ser DVE significa que en cada posición de su recorrido siempre hay una dirección en la que se ve el horizonte.

Polígono DVE Polígono no DVE: no se ve el horizonte en ninguna dirección

En términos de iluminación, consideremos una circunferencia suficientemente

grande para que contenga totalmente al polígono. Para iluminar el muro exterior de la fortaleza (o edificio de interés turístico) basta con colocar un fluorescente circular sobre la circunferencia anterior.

1.4.10 Polígono Monótono Un polígono P se dice que es monótono respecto de una dirección D si toda

recta r ortogonal a la recta D verifica que

P monótono respecto a D

P no monótono con respecto a D

Page 11: Geometría Computacional libro1

Universidad Central del Ecuador

Geo

met

ría

Com

puta

cional

1

1

Se dice que P es monótono, si lo es respecto de alguna dirección.

También puede darse una definición alternativa atendiendo sólo a la frontera de P: un polígono es monótono cuando su frontera se puede descomponer en dos

cadenas monótonas respecto a la misma dirección. Entendiendo por cadena poligonal monótona respecto a D si cualquier recta ortogonal a D que interseca a la cadena lo hace en un punto o en un lado.

Cadena monótona respecto a D Cadena no monótona respecto a D

1.5 Área signada de un triángulo

Consideremos tres puntos en el plano . El área del triangulo que determinan viene dado por

Ahora bien, , es decir, es el módulo

del producto vectorial de y Recordando que, si y son los vectores de la base canoníca en el espacio entonces

Y usando de nuevo las propiedades de los determinantes

Por Tanto

Page 12: Geometría Computacional libro1

Universidad Central del Ecuador

Geo

met

ría

Com

puta

cional

1

2

Y el área del triángulo:

Sin embargo, nos vamos a fijar en el determinante Su signo es el

del vector y por tanto se rige por la conocida “regla del sacacorchos”.

Aquí nos va a servir para determinar la orientación del triángulo . Regla de la mano derecha

, significa que describe la frontera con orientación positiva.

, significa que describe la frontera con orientación negativo. 1.5.1 Aplicaciones del área signada

Localización de un punto respecto de una recta

Si consideramos la recta que pasa por los puntos y y queremos saber dónde se encuentra un tercer punto q basta calcular el área signada . Si es positiva, q está en el semiplano izquierdo determinado por la recta orientada según

. Si es negativa, está en el derecho, y si es cero está en la recta.

- Si El punto que está a la izquierda de la recta

- Si El punto que está a la derecha de la recta

- Si El punto que está en la recta Ejemplo

Page 13: Geometría Computacional libro1

Universidad Central del Ecuador

Geo

met

ría

Com

puta

cional

1

3

Ejercicio

Page 14: Geometría Computacional libro1

Universidad Central del Ecuador

Geo

met

ría

Com

puta

cional

1

4

Entonces

Código 1 en Matlab

%indica la posición de un punto de acuerdo a una recta

function mensaje = apArSig()

a = input('ingrese p1 ');

b = input('ingrese p2 ');

c = input('ingrese punto a verificar: ');

f1 = [1;a];

f2 = [1;b];

f3 = [1;c];

segmento(a', b');

segmento2(c', c');

M = [f1,f2,f3];

longAC = sqrt((a(1)-c(1))^2 + (a(2)-c(2))^2);

longBC = sqrt((b(1)-c(1))^2 + (b(2)-c(2))^2);

apSig = det(M);

if(apSig > 0)

mensaje=('El punto está a la izquierda');

else if(apSig < 0)

mensaje=('El punto esta a la derecha');

else if(apSig == 0)

if (a(1)< c(1) && c(1)< b(1))

mensaje=('El punto está en la recta');

end

if longAC < longBC

mensaje=('El punto esta atrás');

end

if longBC < longAC

mensaje=('El punto está delante');

end

end

end

end

end

Código 2 en Matlab %Función que indica la posición de un punto de acuerdo a la una recta

function areaSig = AreaSig(p1,p2,q)

f1 = [1;p1];

f2 = [1;p2];

f3 = [1;q];

segmento2(q', q');

A = [f1,f2,f3];

Page 15: Geometría Computacional libro1

Universidad Central del Ecuador

Geo

met

ría

Com

puta

cional

1

5

areaSig = det(A);

dac = sqrt((p1(1)-q(1))^2 + (p1(2)-q(2))^2);

dbc = sqrt((p2(1)-q(1))^2 + (p2(2)-q(2))^2);

if(areaSig > 0)

text(q(1)+ 0.2,q(2),'izquierda')

else if(areaSig < 0)

text(q(1)+ 0.2,q(2),'derecha')

else if(areaSig == 0)

if (q(1)>p1(1) && q(1)<p2(1))

text(q(1)+ 0.2,q(2),'en la recta')

else if dac < dbc

text(q(1)+ 0.2,q(2),'atras')

else if dbc < dac

text(q(1)+ 0.2,q(2),'adelante')

end

end

end

end

end

end

end

Código en C# //Dibuja los elementos del área signada bool presiona = false;

Graphics g;

PointF puntoI;

PointF puntoF;

Pen p = new Pen(Color.Blue);

SolidBrush b = new SolidBrush(Color.AntiqueWhite);

ArrayList lineas = new ArrayList();

ArrayList puntos = new ArrayList();

int contador = 0;

#region seleccion de puntos

private void panel_screen_MouseDown(object sender,

MouseEventArgs e)

{

presiona = true;

puntoI = new PointF(e.X, e.Y);

puntos.Add(puntoI);

}

private void panel_screen_MouseUp(object sender,

MouseEventArgs e)

{

presiona = false;

puntoF = new PointF(e.X, e.Y);

Linea linea = new Linea(puntoI, puntoF);

lineas.Add(linea);

contador = 1;

Linea2 linea2 = new Linea2(puntoI, puntoF,

panel_screen.Height);

MessageBox.Show(linea2.angulo.ToString());

}

private void panel_screen_MouseMove(object sender,

MouseEventArgs e)

{

if (presiona && contador == 0)

Page 16: Geometría Computacional libro1

Universidad Central del Ecuador

Geo

met

ría

Com

puta

cional

1

6

{

g.Clear(Color.White);

g.DrawLine(new Pen(Color.Blue), puntoI, new Point(e.X,

e.Y));

}

if (contador == 1)

posicionPuntoRecta((Linea)lineas[0], new Point(e.X,

e.Y));

}

#endregion

private void insertar()

{

Linea linea = new Linea(puntoI, puntoF);

lineas.Add(linea);

graficar(linea);

}

private void graficar(Linea l)

{

g.DrawLine(p, l.puntoInicial, l.puntoFinal);

}

//calcular el determinante para determinar la posicion del mouse

comparando si es mayor o menor

private float calcularDeterminante(Linea l, PointF pun)

{

float vdeterminante = (l.puntoFinal.X * pun.Y) - (pun.X *

l.puntoFinal.Y) - (l.puntoInicial.X * pun.Y) + (pun.X *

l.puntoInicial.Y) +

(l.puntoInicial.X * l.puntoFinal.Y) -

(l.puntoInicial.Y * l.puntoFinal.X);

return vdeterminante;

}

private void posicionPuntoRecta(Linea l, PointF pun)

{

float determinante = calcularDeterminante(l, pun);

if (determinante > 0)

txtPosicion.Text = "El punto(" + pun.X + "," + pun.Y +

")esta a la izquierda de la recta";

else

if (determinante < 0)

txtPosicion.Text = "El punto(" + pun.X + "," +

pun.Y + ")esta a la derecha de la recta";

else

{

PointF vDirector = new PointF(l.puntoFinal.X -

l.puntoInicial.X, l.puntoFinal.Y - l.puntoInicial.Y);

double t = (pun.X - l.puntoInicial.X) /

vDirector.X;

if (vDirector.X > 0 && vDirector.Y > 0)

if (t < 0)

txtPosicion.Text = "El punto(" + pun.X +

"," + pun.Y + ")esta atras de la recta";

else

if (t > 0 && t < 1)

txtPosicion.Text = "El punto(" + pun.X

+ "," + pun.Y + ")esta en la recta";

else

Page 17: Geometría Computacional libro1

Universidad Central del Ecuador

Geo

met

ría

Com

puta

cional

1

7

txtPosicion.Text = "El punto(" + pun.X

+ "," + pun.Y + ")esta adelante de la recta";

else

if (t < 0)

txtPosicion.Text = "El punto(" + pun.X +

"," + pun.Y + ")esta adelante de la recta";

else

if (t > 0 && t < 1)

txtPosicion.Text = "El punto(" + pun.X

+ "," + pun.Y + ")esta en la recta";

else

//MessageBox.Show("El punto(" + pun.X

+ "," + pun.Y + ")esta atras de la recta");

txtPosicion.Text = "El punto(" + pun.X

+ "," + pun.Y + ")esta atras de la recta";

}

}

2. Triangularización de Polígonos

Entonces

2.1 Conjetura de KLEEN

Sea

= El número de guardias que recubre el polígono

Page 18: Geometría Computacional libro1

Universidad Central del Ecuador

Geo

met

ría

Com

puta

cional

1

8

= Conjunto de puntos (vértices del polígono)

I I = Cardinalidad de

Sea un polígono de vértices

Ciertamente (1 es una cota inferior)

Al menos debe haber un guardia

Además , esto significa que puedo recubrir todo el polígono con guardias al poner cada guardia en cada vértice.

La conjetura de Kleen dice que , donde [ ] representa la función parte

entera de .

Definición.-

Una poligonal de un polígono es un segmento entre 2 vértices e que son claramente visibles el uno del otro.

Esto significa que la intersección del segmento cerrado con la es

exactamente el punto

1

2

3

6

5

11

12

8

9

Page 19: Geometría Computacional libro1

Universidad Central del Ecuador

Geo

met

ría

Com

puta

cional

1

9

[Escriba una cita

del documento o

del resumen de

un punto

interesante.

Puede situar el

cuadro de texto

en cualquier

lugar del

documento.

Utilice la ficha

Herramientas de

cuadro de texto

para cambiar el

formato del

cuadro de texto

de la cita.]

Llamamos diagonales concurrentes si su intersección entre ellos es un subconjunto de sus puntos extremos.

Si nosotros agregamos diagonales concurrentes e internas a un polígono

tantas veces como sean posibles, el interior del polígono es particionado en triángulos.

Una partición se llama triangularización del polígono . Observación.- Las diagonales se agregan en orden aleatorio. 2.2 TREE COLORING Primer paso.-

Consiste en triangularizar el polígono con el concepto tree coloring. Sea el grafo asociado a la triangularización y cuyos nodos son los vértices del polígono.

12 vértices

Necesito 3 guardias

Segundo paso.- Definición.-

El k-coloreo es la asignación de k-colores diferentes en los nodos del grafo asociado al polígono P.

Un Grafo siempre puede ser coloreado con 3 colores. Tree Coloring.

1) Verde

2) Amarillo

3) Rojo

Diagonales

externas

Page 20: Geometría Computacional libro1

Universidad Central del Ecuador

Geo

met

ría

Com

puta

cional

2

0

Observación:

El tree Coloring determina el número máximo de guardias pero no el número óptimo de guardias Tercer paso.-

Consiste en ubicar los guardias en el color que produce el número óptimo de guardias, los guardias son ubicados en los vértices. Cuarto paso.-

Usar el principio del Palomar. Principio de PALOMAR.-

Si n objetos son puestos en k huecos es palomar, entonces al menos un hueco

debe contener n objetos.

2.3 Diagonales y Triangularización

LEMA 1.2.1.- Cada polígono debe tener al menos un vértice estrictamente convexo. Definición.-

Se dice que un vértice de un polígono es convexo cuando el ángulo interior que determina los lados concurrentes en él es menor o igual a .

Page 21: Geometría Computacional libro1

Universidad Central del Ecuador

Geo

met

ría

Com

puta

cional

2

1

Si los lados del polígono tienen orientación positiva. Si un caminante recorre la frontera en algún momento debe virar a la izquierda

y el interior del polígono está siempre a su izquierda.

Sea una recta que pasa por un vértice (el más bajo) → (el que tiene la menor ordenada), y el más a la derecha, como es orientación positiva el siguiente vértice está encima de y elángulo es menor a y por tanto se obtiene el vértice convexo.

LEMA 1.2.2 (MEISTERS).- Cada polígono de vértices tiene una diagonal (al memos) (un triangulo no tiene diagonales). Demostración

Sea un vértice convexo, sean los vértices adyacentes a .

Si es diagonal, termina.

Si no es diagonal ( sea exterior o corte en la frontera) entonces construimos el triángulo.

y consideramos un vértice X que este en el triángulo para determinar el

vértice .

Se traza paralelo el segmento que está en el triángulo y se puede terminar 2

diagonales y repito el proceso, si es diagonal y no es diagonal termina porque encontré que cada polígono tiene al menos una diagonal.

LEMA1.2.3.- Cada polígono de vértices puede ser particionado en triángulos por una o más diagonales. Demostración

Usamos inducción matemática.

Si . El polígono es un triangulo y el teorema es trivial.

Si Sea , una diagonal del polígono (El teorema de Meisters garantiza la existencia). Por definición la diagonal corta en con y ésta

diagonal particiona el polígono en 2 poligonos cada uno de lso cuales tiene a .

Como cada uno de los polígonos tiene el número de vértices menos a , y luego aplica recursividad a cada polígono hasta obtener el número de vértices de mi polígono.

Page 22: Geometría Computacional libro1

Universidad Central del Ecuador

Geo

met

ría

Com

puta

cional

2

2

Propiedades

LEMA 1.2.4.- Cada triangularización de un polígono de vértices tiene diagonales y triángulos. Demostración

Si

Si

Por hipótesis de Inducción

Sea el polígono con vértices y diagonales y triángulos.

Creamos una partición del polígono con una diagonal y obtenemos

→ (porque a y b están en P1 y P2)

Aplicando el principio de inducción a los sub-polígonos para:

De n vértices

Page 23: Geometría Computacional libro1

Universidad Central del Ecuador

Geo

met

ría

Com

puta

cional

2

3

Para el número de triángulos

COROLARIO 1.2.5.-

La suma de los ángulos internos de un polígono de n-vértices es .

Demostración

La suma de los ángulos interiores en un triángulo es y como hay triángulos entonces la suma de los ángulos del polígono es

Código en C# //este método nos hace dibujar cada una de las líneas de la

poligonal determinando en el punto que empieza y termina la

recta para comenzar otra

public partial class frmTriangular : Form

{

private ArrayList puntos = new ArrayList();

private Point[] polygon;

private miFormaPoligonal m;

private prosess_status status;

private Pen polygon_pen = new Pen(Color.Black, 2);

public frmTriangular()

{

InitializeComponent();

}

private void panel_screen_MouseUp(object sender,

MouseEventArgs e)

{

if (e.Button == MouseButtons.Left)

{

Point p = new Point(e.X, e.Y);

puntos.Add(p);

status = prosess_status.DIBUJANDO;

}

else if (e.Button == MouseButtons.Right)

{

if (puntos.Count < 3) {

MessageBox.Show("Debe seleccionar al menos 3

puntos");

return;

}

polygon = new Point[puntos.Count];

for (int i = 0; i < puntos.Count; i++)

polygon[i] = (Point)puntos[i];

Graphics g = panel_screen.CreateGraphics();

g.Clear(Color.White);

dibujarPoligono();

Page 24: Geometría Computacional libro1

Universidad Central del Ecuador

Geo

met

ría

Com

puta

cional

2

4

status = prosess_status.POLIGONOLISTO;

btnTriangular.Enabled = true;

}

}

//en este método dibujaremos

private void panel_screen_MouseMove(object sender,

MouseEventArgs e)

{

if (status== prosess_status.DIBUJANDO)

{

Point inicio, fin;

Graphics g = panel_screen.CreateGraphics();

g.Clear(Color.White);

inicio = (Point)puntos[0];

g.DrawLine(new Pen(Color.Yellow, 2), inicio.X - 6,

inicio.Y, inicio.X + 6, inicio.Y);

g.DrawLine(new Pen(Color.Yellow, 2), inicio.X,

inicio.Y - 6, inicio.X, inicio.Y + 6);

for (int i = 0; i < puntos.Count - 1; i++)

{

inicio = (Point)puntos[i];

g.DrawLine(new Pen(Color.Yellow, 2), inicio.X - 6,

inicio.Y, inicio.X + 6, inicio.Y);

g.DrawLine(new Pen(Color.Yellow, 2), inicio.X,

inicio.Y - 6, inicio.X, inicio.Y + 6);

fin = (Point)puntos[i + 1];

g.DrawLine(new Pen(Color.Yellow, 2), fin.X - 6,

fin.Y, fin.X + 6, fin.Y);

g.DrawLine(new Pen(Color.Yellow, 2), fin.X, fin.Y

- 6, fin.X, fin.Y + 6);

g.DrawLine(new Pen(Color.Blue, 2), inicio, fin);

}

inicio = (Point)puntos[puntos.Count - 1];

fin = new Point(e.X, e.Y);

g.DrawLine(new Pen(Color.Blue, 2), inicio, fin);

g.DrawLine(new Pen(Color.Yellow, 2), fin.X - 6, fin.Y,

fin.X + 6, fin.Y);

g.DrawLine(new Pen(Color.Yellow, 2), fin.X, fin.Y - 6,

fin.X, fin.Y + 6);

}

lbCoordenadas.Text = "X:" + e.X + " , Y:" + e.Y;

}

//dibuja las diagonales de la poligonal

private void btnTriangular_Click(object sender, EventArgs e)

{

if (polygon == null | status!=

prosess_status.POLIGONOLISTO)

return;

if (polygon.Length < 3)

return;

m = new miFormaPoligonal(polygon);

m.triangular();

Graphics g = panel_screen.CreateGraphics();

g.Clear(Color.White);

Page 25: Geometría Computacional libro1

Universidad Central del Ecuador

Geo

met

ría

Com

puta

cional

2

5

draw_ears(false);

dibujarPoligono();

status = prosess_status.TRIANGULACIONCOMPLETA;

}

private void btnLimpiar_Click(object sender, EventArgs e)

{

puntos.Clear();

polygon = null;

m = null;

Graphics g = panel_screen.CreateGraphics();

g.Clear(Color.White);

btnTriangular.Enabled = false;

status = prosess_status.ESPERANDO;

}

public void dibujarPoligono()

{

if (polygon!=null) // if we'r not animating

{

Graphics g = panel_screen.CreateGraphics();

for (int i = 0; i< polygon.Length ; i++)

{

g.DrawLine(new Pen(Color.Yellow, 2), polygon[i].X

- 8, polygon[i].Y, polygon[i].X + 8, polygon[i].Y);

g.DrawLine(new Pen(Color.Yellow, 2), polygon[i].X,

polygon[i].Y - 8, polygon[i].X, polygon[i].Y + 8);

}

g.DrawPolygon(polygon_pen, polygon); // draw it

}

}

private void draw_ears(Boolean wireframe_only) // draws

tringulated polygons

{

if (m == null) // if m has been processed

return;

Graphics g = panel_screen.CreateGraphics();

for (int i = 0; i < m.poligonos.Length; i++)

{

g.DrawPolygon(new Pen(Color.Black, 1),

m.poligonos[i]); // draw polygon

Invalidate(); // update screen

}

g.DrawPolygon(polygon_pen, polygon);

}

private void panel_screen_Paint(object sender, PaintEventArgs

e)

{

switch (status)

{

case prosess_status.ESPERANDO:

break;

case prosess_status.POLIGONOLISTO:

dibujarPoligono();

break;

case prosess_status.TRIANGULACIONCOMPLETA:

draw_ears(false);

Page 26: Geometría Computacional libro1

Universidad Central del Ecuador

Geo

met

ría

Com

puta

cional

2

6

break;

default:

break;

}

}

2.4 Triangularización Dual

Un importante concepto en la teoría de los grafos es el grafo dual, utilizaremos este concepto para definir el dual de una triangularización. Definición.-

El dual T* de una triangularización T de un polígono es un grafo con un nodo

asociado a cada triángulo y un arco entre 2 nodos si y solo sí su triángulos comparten una misma diagonal.

Page 27: Geometría Computacional libro1

Universidad Central del Ecuador

Geo

met

ría

Com

puta

cional

2

7

Observación:

En el grafo no se unen con porque no comparten una misma diagonal.

LEMA1.2.6.- El dual T* de una triangularización es un árbol.

Es evidente que cada nodo tiene grado a lo más 3, porque cada triángulo en nuestra triangularización puede compartir a lo más 3 lados.

Los nodos de grado (1) son hojas del árbol , los nodos de grado (2) son

los caminos del árbol. y los nodos de grado (3) son puntos de

ramificación .

Note que el dual es un árbol binario cuando cualquier nodo tiene grado 1 o 2

(hijos). 2.5 Intersección de Segmentos

Para que ad y cd se intersequen

Aplicamos la regla de Cramer

a

d

d

d

a

b

c

a

a

b

s,t

c

d

Page 28: Geometría Computacional libro1

Universidad Central del Ecuador

Geo

met

ría

Com

puta

cional

2

8

Si existe solución s y t deben estar entre 0 y 1 y luego reemplazo. Código 1 en Matlab

function p = Interseccion()

a = input('ingrese el punto A: ');

b = input('ingrese el punto B: ');

c = input('ingrese el punto C: ');

d = input('ingrese el punto D: ');

detDen = (b(1)-a(1))*(d(2)-c(2)) - (d(1)-c(1))*(b(2)-a(2));

segmento(a,b);

segmento(c,d);

if ( detDen ~=0 )

s =((c(1)-a(1))*(d(2)-c(2))-(d(1)-c(1))*(c(2)-a(2)))/detDen;

t =((c(1)-a(1))*(b(2)-a(2))-(b(1)-a(1))*(c(2)-a(2)))/detDen;

if(((s>=0)&&(s<=1))&&((t>=0)&&(t<=1)))

p(1) = c(1)+t*(d(1)-c(1));

p(2) = c(2)+t*(d(2)-c(2));

segmento2(p,p)

fprintf('los segmentos se intersecan en: ')

p

else

fprintf('los segmentos no se intersecan: ')

end

end

end

Código 2 en Matlab

function P = Interseccion(A,B,C,D)

% calculamos el determinante

da = (B(1)-A(1))*(D(2)-C(2)) - (D(1)-C(1))*(B(2)-A(2));

% if el determinante que es el el denominador es <> 0

if (da~=0)

s =((C(1)-A(1))*(D(2)-C(2))-(D(1)-C(1))*(C(2)-A(2)))/da;

t =((C(1)-A(1))*(B(2)-A(2))-(B(1)-A(1))*(C(2)-A(2)))/da;

%se verifica que s y t esten entre 0 y 1

if(((s>=0)&&(s<=1))&&((t>=0)&&(t<=1)))

P(1)=A(1)+s*(B(1)-A(1));

P(2)=A(2)+s*(B(2)-A(2));

P

segmento2(P,P)

else

P = [str2num('no punto'),str2num('no punto')];

end

end

end

Código en C#

//determinar la posición de la recta , calculando la pendiente, luego

de ello graficamos al interseccion de las rectas

Page 29: Geometría Computacional libro1

Universidad Central del Ecuador

Geo

met

ría

Com

puta

cional

2

9

private PointF interseccion(Linea l1, Linea l2)

{

float xc, yc;

if (l1.pendiente == l2.pendiente)

return PointF.Empty;

else

{

xc = (l2.k - l1.k) / (l1.pendiente - l2.pendiente);

yc = (l2.k * l1.pendiente - l1.k * l2.pendiente) /

(l1.pendiente - l2.pendiente);

return new PointF(xc, yc);

}

}

private void graficaInterseccion()

{

for (int i = 0; i < lineas.Count; i++)

{

for (int j = 0; j < lineas.Count; j++)

{

Linea l1 = (Linea)lineas[i];

Linea l2 = (Linea)lineas[j];

if (i != j)

{

PointF punto = interseccion(l1, l2);

if (punto == PointF.Empty)

MessageBox.Show("No hay intersección");

else

{

float yy = panel_screen.Height - punto.Y;

}

PointF punto2 = new PointF(punto.X - 2,

punto.Y - 2);

g.FillEllipse(Brushes.Red, new

RectangleF(punto2, new SizeF(4, 4)));

}

}

}

}

3. Conjuntos Convexos

Page 30: Geometría Computacional libro1

Universidad Central del Ecuador

Geo

met

ría

Com

puta

cional

3

0

Definición.-

Un conjunto de puntos A se dice convexo, si , el segmento

EJEMPLO:

Sea verificar si es conjunto convexo.

1) cumple con x² + y² ≤ a²

2) cumple con x² + y² ≤ a²

PDQ

+ ) B

PDQ

Ahora

También

Por lo tanto el conjunto B es un conjunto convexo Proposición.-

A y B son conjuntos convexos, entonces es convexo. Y en general la intersección de una familia finita o no convexa es convexa Demostración

Page 31: Geometría Computacional libro1

Universidad Central del Ecuador

Geo

met

ría

Com

puta

cional

3

1

PDQ

PDQ

3.1 Cierre Convexo Definición.-

El cierre convexo de un conjunto S es el menor convexo que contiene a S. Lo notaremos CH (convex hull).

3.2 Soporte de S

Definición.-

Dado un conjunto S en el plano y un punto se dice que una recta que

pasa por es soporte de si queda en uno de los semiplanos cerrados que determina.

Observación:

Si el conjunto se dice que es un semiplano

Page 32: Geometría Computacional libro1

Universidad Central del Ecuador

Geo

met

ría

Com

puta

cional

3

2

L1 es soporte de

L2 es soporte de

L3 no es soporte porque hay tres puntos de que están en los dos semiplanos.

Proposición:

Si es un polígono convexo cuyos vértices están en , entonces

Demostración

Sean los vértices de , como , qi [CH(S) es un

subconjunto más pequeño convexo que contiene al mismo conjunto] y como CH(S) es un conjunto convexo todos los lados de P están contenidos en CH(S).

Es decir, . Para comprobar finalmente que todo punto , está en

CH(S) basta observar, consideramos el segmento

Como

x

Como

Lo que demuestra que , es decir el polígono es siempre subconjunto del

polígono convexo

Page 33: Geometría Computacional libro1

Universidad Central del Ecuador

Geo

met

ría

Com

puta

cional

3

3

Proposición.-

Si S es un conjunto de n puntos en el plano entonces CH(S) es el polígono convexo que contiene a S y cuyos vértices en puntos de S. Este puede generar en un punto si o en un segmento si todos son coliniales.

En la practica un polígono convexo viene determinado por su frontera en el caso de cierre convexo de S a su frontera se le denomina envolvente convexo abusando de la notación se le representa CH (S).

Teorema: 3.3 Características para determinar la envolvente convexa.

1. P es convexo toda recta que pase por dos vértices consecutivos, deja a P en el semiplano de la izquierda (con la orientación inducida en la recta por

P).

2. P es convexo Toda recta que pasa por 2 vértices consecutivos, deja al

siguiente vértice en el semiplano de la izquierda.

3. P es convexo Todo ángulo interior en cada vértice de P es menor o igual

a , es decir todos los vértices son convexos.

4. P es convexo todo vértice admite una recta soporte de P que pasa por

él.

Page 34: Geometría Computacional libro1

Universidad Central del Ecuador

Geo

met

ría

Com

puta

cional

3

4

Algoritmos para determinar envolventes convexas 3.4 Marcha de Jarvis.

Algoritmo que se basa en la localización de puntos de S que admiten rectas soportes del conjunto. La búsqueda está organizada de tal manera que en cada paso trata de conociendo un vértice de la envolvente, encontrar otro vértice que con él determine una recta soporte de S. 3.4.1 Descripción geométrica del algoritmo.

1. Tomar un punto de S con mínima abscisa y marcarle como , la recta vertical

que pasa por es soporte de S y la llamamos r1. Observación: Otra opción es tomar un punto con mínima ordenada, en caso de repetirse tomar el punto con mínima ordenada y mínima abscisa, la recta

horizontal que pasa por es soporte de S y la llamamos r1.

2. Girar en torno a la recta r1 en sentido positivo hasta que toque el primer punto de S que encuentre en su recorrido será el siguiente vértice de la

envolvente ( ). A la recta soporte que pasa por y le llamamos r2.

Page 35: Geometría Computacional libro1

Universidad Central del Ecuador

Geo

met

ría

Com

puta

cional

3

5

3. Paso i: Girar en torno a vi la recta ri en sentido positivo hasta que toque el 1er

punto de S que encuentre en su recorrido, llamamos +1, y la recta que pasa por y se le llama ri+1. Observación:

El bucle termina cuando = .

4. Final: Con la Marcha de Jarvis obtenemos … que es la envolvente convexa.

Tenemos los siguientes hechos:

En cada paso i (i = 1,2,3,…,k) se mantiene invariante que el vértice vi es un vértice de la envolvente convexa, y que la recta ri es soporte de S.

La lista cíclica resultante C = ( , ,..., ) satisface que la recta orientada que pasa por 2 vértices consecutivos vi,vi+1 que no es otra cosa que ri+1, deja a S a su izquierda.

En consecuencia C es la frontera de un polígono convexo son vértices en S y que contiene a S, por el Teorema anterior C = CH(S).

Descripción del algorítmo: Entrada: Lista de puntos (P1,…,Pn)

Salida: Lista cíclica de vértices de CH, C = ( , ,…, ), con k n

Page 36: Geometría Computacional libro1

Universidad Central del Ecuador

Geo

met

ría

Com

puta

cional

3

6

1. Encontrar el punto de S con abscisa mínima, si hubiera más de un punto, se escoge el de menor ordenada, llamamos v1 e insertamos a la lista cíclica C inicialmente vacía.

2. Paso i: Localizamos en S el punto de menor ángulo positivo respecto a y el

rayo que emana de en la dirección - . A este punto se marca que si insertamos en C y continuamos el paso i, y en caso contrario ( =

) hemos terminado.

Para encontrar el mínimo angular no es necesario hallar ningún ángulo, el cálculo se hace solo con áreas signadas. En efecto como la recta ri es soporte en , todos los puntos de S están a la izquierda y el ángulo que forma cada punto está en

(0, ), por tanto para comprar 2 ángulos los determinamos por Pj y Pk respectivamente.

Observación:

Si en el paso i-ésimo hay varios puntos alineados que dan el menor angular,

selecciono aquel que está más alejado del vértice vi. 3.4.2 Estudio de complejidad

Localizar el mínimo entre n valores puede hacerse en tiempo O(n) “# de

operaciones para determinar mi objetivo”.

Para cada i localizar el menor angular entre un total de n-1, también puede hacerse en tiempo O(n), por tanto en tiempo total requerido es O(n.k)

Page 37: Geometría Computacional libro1

Universidad Central del Ecuador

Geo

met

ría

Com

puta

cional

3

7

O(f(x)) O(g(x)) = O(f(x)g(x)), donde k es el numero de vértices en la envolvente convexa, que en el peor de los caso k es n, y por tanto la complejidad del algoritmo será:

O(k.n) = 1 O( )

Sin embargo, si el número de vértices en la envolvente es relativamente pequeño respecto de n, el algoritmo es interesante, ya que se puede generalizar para el espacio tridimensional, lo que no puede hacerse con otros algoritmos como el de Graham, cuya complejidad es O(nlogn). Implementación del algoritmo en MATLAB % función que me elimina un punto de un conjunto de puntos

function B = QuitarPunto(A,vector)

[n m] = size(A);

k = 1;

i = 1;

l = 1;

while i <= n

for j= 1: 2

a(j) = A(i,j);

end

if vector == a

i = n;

else

k = k+1;

end

i = i+1;

end

for i = 1:n-1

for j = 1: 2

if l == k

l = k+1;

end

B(i,j) = A(l,j);

end

l = l+1;

end

%B

end

%función que devuelve el punto con menor abscisa de un conjunto de puntos function min = MenorAbcisa(A)

[n col] = size(A);

aux = A(1,1);

j = 0;

l = 1;

m = 1;

for i = 1: n

if aux >= A(i,1);

aux = A(i,1);

end

end

Page 38: Geometría Computacional libro1

Universidad Central del Ecuador

Geo

met

ría

Com

puta

cional

3

8

while m <= n

if aux ~= A(m,1)

l = l+1;

else

m = n;

end

m = m+1;

end

for k =1:2

min(1,k) = A(l,k);

end

end

%función que devuelve el punto con menor Ordenada y Menor

abscisa

function minOminA = MinOminA(A)

[n c] = size(A);

aux = A(1,2);

l = 0;

m = 1;

for i = 1: n

if aux >= A(i,2)

aux = A(i,2);

end

end

while m <= n

if aux == A(m,2)

l = l+1;

for j = 1: 2

minOminA(l,j) = A(m,j);

end

end

m = m+1;

end

minOminA = MenorAbcisa(minOminA);

end

% dado un punto me devuelve el siguiente respecto a la recta r

que gira en sentido positivo, recibe la matriz de puntos A, y el

punto po

function sig = Siguiente(A,Po)

[n col] = size(A);

if n >= 3

A = QuitarPunto(A,Po);

ab(1) = Po(1);

ab(2) = Po(2)-5;

MAB = ab-Po;

nAB = norm(MAB);

for j = 1:2

P1(j)=A(1,j);

P2(j)=A(2,j);

end

v1 = P1-Po;

alfa1 = acos((MAB*v1')/(nAB*norm(v1)))*(180/pi);

Page 39: Geometría Computacional libro1

Universidad Central del Ecuador

Geo

met

ría

Com

puta

cional

3

9

v2 = P2-Po;

alfa2 = acos((MAB*v2')/(nAB*norm(v2)))*(180/pi);

if alfa1 < alfa2

vert2 = P1;

ang = alfa1;

else

vert2 = P2;

ang = alfa2;

end

for i = 3: length(A)

for j = 1: 2

P(j) = A(i,j);

end

v = P-Po;

alfa2 = acos((MAB*v')/(nAB*norm(v)))*(180/pi);

if ang > alfa2

ang = alfa2;

vert2 = P;

end

end

else

for j = 1: 2

vert2(j) = A(n-1,j);

end

end

sig = vert2;

end

%función que devuelve la envolvente convexa y la grafica.

Recibe la Matriz de puntos A, el punto po, el segundo punto de la

envolvente, k que es una variable de ayuda, en mat se ingresa los

punto de la envolvente convexa y pc=po, para terminar la búsqueda de

un siguiente punto.

function sig = BuscarSiguiente2(A,po,ps,k,mat,pc)

n = length(A);

if n >= 2

for i= 1: length(A)

x(i) = A(i,1);

y(i) = A(i,2);

end

plot(x,y,'*'); %muestra la nube de puntos

for kk=1:15

segmento3(po,ps) %va graficando paso a paso la envolvente

convexa

M(k)=getframe;

end

if pc ~= ps

if k==1

A = QuitarPunto(A,ps); %se elimina el 2do punto de la lista

end

pops = ps - po;

pq = po +3*pops; %obtenemos el rayo entre 2 puntos

v1 = po-ps;

v2 = v1;

Page 40: Geometría Computacional libro1

Universidad Central del Ecuador

Geo

met

ría

Com

puta

cional

4

0

v3 = pq-ps;

alfa1 = acos((v3*v1')/(norm(v3)*norm(v1)))*(180/pi);

alfa2 = acos((v3*v2')/(norm(v3)*norm(v2)))*(180/pi);

if alfa1 <= alfa2

sig = po;

ang = alfa1;

else

sig = po;

ang = alfa2;

end

for i = 1: length(A)

for j = 1: 2

P(j) = A(i,j);

end

v = P-ps;

alfa2 = acos((v3*v')/(norm(v3)*norm(v)))*(180/pi);

if ang > alfa2

ang = alfa2;

sig = P;

end

end

sig;

O = [mat;sig];

BuscarSiguiente2(A,ps,sig,2,O,pc);

end

end

end

% reúne las funciones anteriores para obtener la envolvente convexa.

function jarvis = Jarvis(m)

po = MinOminA(m);

ps = Siguiente(m,po);

BuscarSiguiente2(m,po,ps,1,[po;ps],po);

end

Código Jarvis en c#

//Determina los puntos máximos, mínimos y los ángulos máximos de los

segmentos

private void jarvis()

{

int maxAngulo = 0, minAngulo = 0;

maxPunto = 0;

for (int k = 1; k < numeroPuntos; k++)

{

if (puntos[k].Y > puntos[maxPunto].Y)

maxPunto = k;

}

minPunto = 0;

for (int k = 1; k < numeroPuntos; k++)

{

if (puntos[k].Y < puntos[minPunto].Y)

minPunto = k;

}

Page 41: Geometría Computacional libro1

Universidad Central del Ecuador

Geo

met

ría

Com

puta

cional

4

1

puntosUsados.Add(minPunto);

puntoActual = minPunto;

while (puntoActual != maxPunto)

{

maxAngulo = puntoActual;

for (int k = 0; k < numeroPuntos; k++)

{

g.DrawLine(p,puntos[puntoActual],puntos[k]);

if (calcularAngulo(puntos[puntoActual].X,

puntos[puntoActual].Y, puntos[minAngulo].X, puntos[minAngulo].Y)

>= calcularAngulo(puntos[puntoActual].X,

puntos[puntoActual].Y, puntos[k].X, puntos[k].Y)

&& (noUsado(k) || k == maxPunto) &&

calcularAngulo(puntos[puntoActual].X, puntos[puntoActual].Y,

puntos[k].X, puntos[k].Y) >= 90)

{

minAngulo = k;

}

puntoActual = minAngulo;

puntosUsados.Add(puntoActual);

}

}

drawPermeter();

}

private double calcularAngulo(double x1, double y1, double x2,

double y2)

{

double deltaX = x2 - x1;

double deltaY = y2 - y1;

if (deltaX == 0 && deltaY == 0)

return 0;

double angle = Math.Atan(deltaY / deltaX) * (180.0 /

Math.PI);

if (deltaX >= 0 && deltaY >= 0)

angle = 90 + angle;

else if (deltaX >= 0 && deltaY < 0)

angle = 90 + angle;

else if (deltaX < 0 && deltaY > 0)

angle = 270 + angle;

else if (deltaX < 0 && deltaY <= 0)

angle = 270 + angle;

return angle;

}

Graphics g;

Pen p = Pens.Blue;

private void frmJarvis_Load(object sender, EventArgs e)

{

g = this.CreateGraphics();

}

bool noUsado(int n)

{

for (int i = 0; i < puntosUsados.Count; i++)

if (n == (int)puntosUsados[i])

return false;

Page 42: Geometría Computacional libro1

Universidad Central del Ecuador

Geo

met

ría

Com

puta

cional

4

2

return true;

}

3.5 Scan de Graham

El siguiente algoritmo, así como todas sus variantes, está basado fundamentalmente en dos ideas acerca de un polígono convexo.

La primera tiene que ver con la secuencia de los vértices que describen su frontera, las condiciones para que un polígono sea convexo son tan fuertes que supone que esa secuencia tenga propiedades muy importantes.

Por ejemplo, un polígono convexo en particular es un polígono estrellado y por tanto respecto a un punto del núcleo (que puede ser cualquiera del polígono) los vértices aparecen ordenados angularmente en la secuencia. O también como el polígono es monótono respecto de cualquier dirección, en particular respecto del eje OX, su frontera puede descomponerse en dos cadenas monótonas respecto de OX y en cada una de ellas la secuencia de vértices que las determina está ordenada por abscisas.

La segunda idea simplemente es que todos los vértices de un polígono convexo son convexos. Así en los siguientes algoritmos se pueden apreciar dos pasos.

1. Ordenación

Consiste en ordenar los puntos de S de modo que se obtenga una lista cíclica L con todos los puntos de S de manera que describe un polígono especial: estrellado o monótono.

2. Scan

Consiste en comprobar que en L cada punto forme con sus dos adyacentes en

L un ángulo menor que . Si alguno no lo cumple se elimina y así se va depurando hasta que la lista resultante satisfaga esa condición.

3.5.1 Algoritmo de Graham.

Entrada: Lista con los puntos en posición general de S: S = (P1,…,Pn)

Salida: Lista cíclica con los vértices de la envolvente convexa de S : C = ( , ,…, )

1. Encontrar el punto de S con abscisa mínima, si hubiera más de uno el de

menor ordenada: será .

2. Ordenar angularmente el resto de puntos de S respecto a y en sentido

positivo respecto al rayo vertical que emana de él en dirección a - . Sea L =

( , ,…, )el resultado, con pegado a posteriori.

Page 43: Geometría Computacional libro1

Universidad Central del Ecuador

Geo

met

ría

Com

puta

cional

4

3

3. Insertar en C originalmente vacía y . Hacer q = .

4. Scan: Desde i = 3 hasta n, hacer 1. P = ant(q) (anterior en C) 2. Mientras ,

a) Borrar q de C b) Actualizar q = p y p = ant(q)

3. Insertar en C y actualizar q =

Nota:

Conviene observar que en la ordenación angular respecto de , tanto como son vértices de la envolvente. Esto se ha tenido en cuenta en esta descripción del

algoritmo, concretamente para que la función ant(q) en C este siempre bien definida y

para ahorrarnos la comprobación de que el ángulo formado en con su anterior en C

y con es menor que . La ventaja que esto supone es de limpieza de código. 3.5.2 Análisis de Complejidad

El paso 1 cuesta O(n) y el 2, O (nlogn). En cuanto al Scan, podemos analizarlo de la siguiente manera: partiendo de la lista ( , ,…, ) a cada vértice, , (i > 1), se

Page 44: Geometría Computacional libro1

Universidad Central del Ecuador

Geo

met

ría

Com

puta

cional

4

4

le aplica un test de área signada con sus vecinos para averiguar si las tres forman en

un ángulo menor que . Luego por lo pronto tenemos n-1 cálculos de áreas

signadas, sin embargo puede que sobre el mismo vértice tengamos que aplicar de nuevo el mismo test porque sus vecinos han cambiado. Esto sucede cada vez que se borra un vértice de la lista porque el test de área signada aplicado sobre el salió negativo y aparecen ahora en la lista consecutivos vértices que antes no lo eran.

En definitiva se revisita de nuevo el vértice para aplicarle de nuevo el test, si y solo si ha sido previamente borrado otro, y por tanto, globalmente el número de revisitaciones de vértices esta acotado superiormente por el número de vértices que se han borrado. Como mucho se pueden borrar n-3, luego el número máximo de test de áreas signadas que se aplica a lo largo del algoritmo es 2n-4. Por tanto el coste total de las operaciones aritméticas es O(n).

Las otras operaciones sobre estructuras de datos puede realizarse cada una en tiempo constante, por ejemplo si se utiliza una pila para representar C, además cada

vez que se trata un punto se realiza un número constante de operaciones.

El número total de veces que se tratan vértices es O(n), luego el coste total del Scan es O(n) y del algoritmo es O (nlogn). Implementación del algoritmo de Matlab %función que devuelve 2 veces el área de un triángulo

function area2 = Area2(a,b,c)

area2 = (b(1)-a(1))*(c(2)-a(2))- (c(1)-a(1))*(b(2)-a(2));

end

%función que ordena aleatoriamente los puntos ingresados

inicialmente,

%recibe como parámetro la matriz de puntos A, el punto mínimos

una k te de ayuda K, y mat que es la matriz que contiene al

primer punto de la

%envolvente convexa

%Observación: La función QuitarPunto está ubicada en Jarvis, min

se obtiene con MinOminA

function M = OrdenarAngularmente(A,min,k,mat)

[n col] = size(A);

if k ==1

A = QuitarPunto(A,min);

end

if n >= 2

ab(1) = min(1)+5;

ab(2) = min(2);

v3 = ab-min;

P1(1) = min(1)-5;

P1(2) = min(2);

P2 = P1;

v1 = P1-min;

v2 = v1;

alfa1 = acos((v3*v1')/(norm(v3)*norm(v1)))*(180/pi);

alfa2 = acos((v3*v2')/(norm(v3)*norm(v2)))*(180/pi);

if alfa1 <= alfa2

vert2 = P1;

ang = alfa1;

Page 45: Geometría Computacional libro1

Universidad Central del Ecuador

Geo

met

ría

Com

puta

cional

4

5

else

vert2 = P2;

ang = alfa2;

end

for i = 1: length(A)

for j = 1: 2

P(j) = A(i,j);

end

v = P-min;

alfa2 = acos((v3*v')/(norm(v3)*norm(v)))*(180/pi);

if ang >= alfa2

ang = alfa2;

vert2 = P;

end

end

else

for j = 1: 2

vert2(j) = A(n,j);

end

end

set(gca,'nextplot','replacechildren');

axis([-50 50 -50 50]);

for kk=1:15

segmento3(min,vert2);

M(k)=getframe;

end

O = [mat;vert2];

if n < 2

M = O;

Comprobar(M)

end

if n>=2

A = QuitarPunto(A,vert2);

OrdenarAngularmente(A,min,2,O);

end

end

%función que verifica que los vértices de la envolvente convexa

sean menor

%o igual a Pi, realiza el Scan de Graham

%recibe la matriz Ordenada

function Mf = Comprobar(MO)

[n m]= size(MO);

for p = 1: n

x(p) = MO(p,1);

y(p) = MO(p,2);

end

plot(x,y,'*','MarkerEdgeColor','r')

hold on

i = 1;

while i <= n-2

for j=1:2

Pi(1,j)=MO(i,j);

Page 46: Geometría Computacional libro1

Universidad Central del Ecuador

Geo

met

ría

Com

puta

cional

4

6

Pi1(1,j)=MO(i+1,j);

Pi2(1,j)=MO(i+2,j);

end

if (Area2(Pi,Pi1,Pi2)<=0)

MO = QuitarPunto(MO,Pi1)

Comprobar(MO)

end

i = i+1;

end

Mf = MO

cadenaPolGraham(Mf)

end

%funcion que dibuja una Poligonal cerrada.

function cadena = cadenaPolGraham(a)

%se ingresa una matriz (nrow,2)

[nr nc] = size(a);

for i = 2: nr

for j = 1: 2

d(j) = a(i-1,j);

e(j) = a(i,j) ;

f(j) = a(nr,j);

g(j) = a(1,j);

if j == 2

% se llama a la funcion segmento que lo grafica

Gsegmento(d,e)

Gsegmento(f,g)

text(d(1),d(2),'P')

text(e(1),e(2),'P')

end

end

end

end

%función que hace la llamada a las funciones anteriores y me

entrega en pantalla la envolvente cerrada con el uso del

algoritmo de Graham

function g = Graham(M,n)

min = MinOminA(M);

MO = OrdenarAngularmente(M,min,1,min);

end

Código Graham en c# //inicializa dibujando puntos randómicos en distinto orden private void frmGraham_Load(object sender, EventArgs e)

{

g = panel_screen.CreateGraphics();

}

funciones f = new funciones();

private void generarGraham(int numeroPuntos)

{

puntosRandom = new Point[numeroPuntos];

puntosRandom = f.generarNubePuntos(numeroPuntos,

panel_screen.Size);

Page 47: Geometría Computacional libro1

Universidad Central del Ecuador

Geo

met

ría

Com

puta

cional

4

7

lineas.Clear();

int yMin = 0, indiceX = 0;

for (int i = 0; i < numeroPuntos; i++)

{

if (puntosRandom[i].Y > yMin)

{

yMin = puntosRandom[i].Y;

indiceX = i;

}

}

for (int i = 0; i < numeroPuntos; i++)

{

if (i != indiceX)

insertar(puntosRandom[indiceX], puntosRandom[i]);

}

graficarTodo();

lineasOrdenar = (ArrayList)lineas.Clone();

lineasTmp = new ArrayList();

for (int i = 0; i < numeroPuntos-1; i++)

ordenaPorAngulo();

//g.Clear(Color.White);

cont = 0;

//graficarTodo();

}

ArrayList lineasOrdenar;

ArrayList lineasTmp = new ArrayList();

private void ordenaPorAngulo()

{

int indiceJ = 0;

double angulo = 99999999;

for (int j = 0; j < lineasOrdenar.Count; j++)

{

if (angulo > ((Linea2)lineasOrdenar[j]).angulo)

{

angulo = ((Linea2)lineasOrdenar[j]).angulo;

indiceJ = j;

}

}

lineasTmp.Add(lineasOrdenar[indiceJ]);

lineasOrdenar.Remove(lineasOrdenar[indiceJ]);

}

//limpia o retira los vectores que no deben estar en la lista cíclica

int cont;

private void btnLimpiar_Click(object sender, EventArgs e)

{

try

{

PointF p1 = ((Linea2)lineasTmp[cont]).puntoFinal;

PointF p2 = ((Linea2)lineasTmp[cont + 1]).puntoFinal;

PointF p3 = ((Linea2)lineasTmp[cont + 2]).puntoFinal;

double ang = calcularAngulo(p1, p2, p3);

if (ang > 180)

{

lineasTmp.Remove(lineasTmp[cont + 1]);

cont = cont - 1;

}

else

{

graficar(new Linea2(p1, p2, 0));

Page 48: Geometría Computacional libro1

Universidad Central del Ecuador

Geo

met

ría

Com

puta

cional

4

8

graficar(new Linea2(p2, p3, 0));

textBox1.Text = ang.ToString();

}

cont++;

}

catch { lineas = (ArrayList)lineasTmp.Clone(); }

}

//calcula el ángulo de los segmento

private double calcularAngulo(PointF a, PointF b, PointF c)

{

double angulo;

PointF v1 = new PointF(-a.X + b.X, -b.Y + a.Y);

PointF v2 = new PointF(-c.X + b.X, -b.Y + c.Y);

double deltaX = v2.X - v1.X;

double deltaY = v2.Y - v1.Y;

if (deltaX == 0 && deltaY == 0)

return 0;

angulo = Math.Atan(deltaY/deltaX)*180/Math.PI ;

if (deltaX >= 0 && deltaY >= 0)

angulo = 90 + angulo;

if (deltaX >=0&& deltaY<0)

angulo = 90 + angulo;

if (deltaX < 0 && deltaY > 0)

angulo = 270 + angulo;

if (deltaX < 0 && deltaY <= 0)

angulo = 270 + angulo;

return angulo;

}

}

Nube de Puntos para dibujar un Círculo

Código en c# para dibujar un circulo de una nube de puntos public partial class frmCirculo : Form

{

public frmCirculo()

{

InitializeComponent();

}

Graphics g;

Pen p = new Pen(Color.Blue);

SolidBrush b = new SolidBrush(Color.AntiqueWhite);

ArrayList lineas = new ArrayList();

ArrayList puntos = new ArrayList();

int suma;

PointF centro;

double distanciaMax = 0;

int indiceI = 0;

int indiceJ = 0;

double distancia;

funciones f = new funciones();

Point[] puntosRandom;

//calcular la distancia entre dos puntos, con máxima distancia

private void calcularDistancias(int numeroPuntos)

{

Page 49: Geometría Computacional libro1

Universidad Central del Ecuador

Geo

met

ría

Com

puta

cional

4

9

indiceI = 0;

indiceJ = 0;

distanciaMax = 0;

distancia = 0;

puntosRandom= new Point[numeroPuntos];

puntosRandom =

f.generarNubePuntos(numeroPuntos,panel_screen.Size);

for (int i = 0; i < numeroPuntos; i++)

{

suma = 0;

for (int j = i + 1; j < numeroPuntos; j++)

{

suma = ((puntosRandom[j].X - puntosRandom[i].X) *

(puntosRandom[j].X - puntosRandom[i].X)) + ((puntosRandom[j].Y -

puntosRandom[i].Y) * (puntosRandom[j].Y - puntosRandom[i].Y));

distancia = Math.Sqrt((double)suma);

if (distancia > distanciaMax)

{

distanciaMax = distancia;

indiceI = i;

indiceJ = j;

}

}

}

Point punto1 = puntosRandom[indiceI];

Point punto2 = puntosRandom[indiceJ];

g.DrawEllipse(Pens.Red, puntosRandom[indiceI].X,

puntosRandom[indiceI].Y, 2, 2);

g.DrawEllipse(Pens.Red, puntosRandom[indiceJ].X,

puntosRandom[indiceJ].Y, 2, 2);

//calcula el centro entre los dos puntos

centro = new PointF((punto1.X + punto2.X) / 2, (punto1.Y +

punto2.Y) / 2);

}

private void btnDibujar_Click(object sender, EventArgs e)

{

int numeroPuntos = int.Parse(txtNumeroPuntos.Text);

calcularDistancias(numeroPuntos);

RectangleF rect = new RectangleF(new PointF(centro.X -

(float)distanciaMax / 2, centro.Y - (float)distanciaMax / 2), new

SizeF((float)distanciaMax, (float)distanciaMax));

for (int i = 0; i < numeroPuntos;i++)

{

g.DrawEllipse(Pens.Red, puntosRandom[i].X,

puntosRandom[i].Y, 1, 1);

}

g.DrawEllipse(Pens.Blue, rect);

}

private void frmCirculo_Load(object sender, EventArgs e)

{

g = panel_screen.CreateGraphics();

}

private void btnLimpiar_Click(object sender, EventArgs e)

{

g.Clear(Color.White);

} }