GRAFICACION C++

GRAFOS

Desafortunadamente no existe una terminología estandarizada en la teoria de los grafos, por lo tanto es oportuno aclarar que las presentes definiciones pueden variar ligeramente entre diferentes publicaciones de estructura de datos y de teoría de grafos, pero en general se puede decir que un grafo como indica su nombre lo indica es la representación (para nuestro caso) gráfica de los datos de una situación particular, ejemplo:

Los datos contienen, en algunos casos, relaciones entre ellos que no es necesariamente jerárquica. Por ejemplo, supongamos que unas líneas aéreas realizan vuelos entre las ciudades conectadas por líneas como se ve en la figura anterior (más adelante se presentaran grafos con estructuras de datos); la estructura de datos que refleja esta relación recibe el nombre de grafo.

Se suelen usar muchos nombres al referirnos a los elementos de una estructura de datos. Algunos de ellos son "elemento", "ítem", "asociación de ítems", "registros", "nodo" y "objeto". El nombre que se utiliza depende del tipo de estructura, el contexto en que usamos esa estructura y quien la utiliza.

En la mayoría de los textos de estructura de datos se utiliza el termino "registro" al hacer referencia a archivos y "nodo" cuando se usan listas enlazadas, arboles y grafos.

También un grafo es una terna G = (V,A,j ), en donde V y A son coonjuntos finitos, y j es una aplicación que hace corresponder a cada elemento de A un par de elementos de V. Los elementos de V y de A se llaman, respectivamente, "vértices" y "aristas" de G, y j asocia entonces a cada arista con sus dos vértices.

Esta definición da lugar a una representación gráfica, en donde cada vértice es un punto del plano, y cada arista es una línea que une a sus dos vértices.

Aristas

Son las líneas con las que se unen las aristas de un grafo y con la que se construyen también caminos.

Si la arista carece de direccion se denota indistintamente {a, b} o {b, a}, siendo a y b los vértices que une.

Si {a ,b} es una arista, a los vértices a y b se les llama sus extremos.

• Aristas Adyacentes: Se dice que dos aristas son adyacentes si convergen en el mismo vértice.
• Aristas Paralelas: Se dice que dos aristas son paralelas si vértice inicial y el final son el mismo.
• Aristas Cíclicas: Arista que parte de un vértice para entrar en el mismo.
• Cruce: Son dos aristas que cruzan en un punto.

Vértices

Son los puntos o nodos con los que esta conformado un grafo. Llamaremos grado de un vértice al número de aristas de las que es extremo. Se dice que un vértice es `par' o `impar' según lo sea su grado.

• Vértices Adyacentes: si tenemos un par de vértices de un grafo (U, V) y si tenemos un arista que los une, entonces U y V son vértices adyacentes y se dice que U es el vértice inicial y V el vértice adyacente.
• Vértice Aislado: Es un vértice de grado cero.
• Vértice Terminal: Es un vértice de grado 1.

Caminos

Sean x, y " V, se dice que hay un camino en G de x a y si existe una sucesión finita no vacía de aristas {x,v₁}, {v₁,v₂},..., {v_n,y}. En este caso

• x e y se llaman los extremos del camino
• El número de aristas del camino se llama la longitud del camino.
• Si los vértices no se repiten el camino se dice propio o simple.
• Si hay un camino no simple entre 2 vértices, también habrá un camino simple entre ellos.
• Cuando los dos extremos de un camino son iguales, el camino se llama circuito o camino cerrado.
• Llamaremos ciclo a un circuito simple
• Un vértice a se dice accesible desde el vértice b si existe un camino entre ellos. Todo vértice es accesible respecto a si mismo

Clasificación de grafos

Los grafos se pueden clasificar en dos grupos dirigidos y no dirigidos. En un grafo no dirigido el par de vértices que representa un arco no está ordenado. Por lo tanto, los pares (v1, v2) y (v2, v1) representan el mismo arco. En un grafo dirigido cada arco está representado por un par ordenado de vértices, de forma que y representan dos arcos diferentes.

SEGMENTACION

La segmentación es un esquema de administración de la memoria que soporta la visión que el usuario tiene de la misma.

Un espacio de direcciones lógicas es una colección de segmentos. Cada segmento tiene un nombre y una longitud.

Las direcciones especifican tanto el nombre del segmento como el desplazamiento dentro del segmento.

Por lo tanto, el usuario especifica cada dirección mediante dos cantidades: un nombre de segmento y un desplazamiento. (Compárese este esquema con la paginación, donde el usuario especificaba solamente una única dirección, que el hardware particionaba en número de página y desplazamiento, siendo todo ello invisible al programador).

Sistema de gestión de memoria en un sistema operativo.

Divide la memoria en segmentos, cada uno de los cuales tiene una longitud variable, que está definida intrínsecamente por el tamaño de ese segmento del programa.

Los elementos dentro de un segmento están identificados por su desplazamiento con respecto al inicio del segmento: la primera instrucción del programa, la séptima entrada de la pila, la quinta instrucción de la función Sqrt(), etc.

Atributo de Primitivas de Linea

Para dibujar un punto o una linea, etc.. OpenGl usa la misma función glvertex(x,y,z) con 3 parametros que indican un punto en el espacio 3D, por ejemplo glvertex3f(0,0,0) le indicamos el punto 0,0,0 en el eje x y z. glvertex tambien puede tener 2 o 4 argumentos por ejemplo glvertex2d(x,y) nos sirve para indicar un punto en 2 dimensiones.


Entonces, la pregunta que nos podemos hacer es como sabe OpenGL que quiero dibujar un punto o una linia ? Pues bien esto se hace con las primitivas, tenemos diferente tipos de primitivas que cuando le indicamos una de ellas pues se dibuja una cosa o otra, para indicar que tipo de primitiva queremos usar llamaremos a la funcion glBegin a la que le pasaremos por parametros el tipo de primitiva que queremos emplear y al finalizar de dibujar usaremos la función glEnd para indicar el fin.



Por ejemplo si queremos dibujar quadrados le indicarremos que el tipo poligono es GL_QUADS para poder dibujar el cuadrado le indicaremos cuatro puntos del espacio. Es muy importante el orden en que dibujaremos siempre lo haremos en el orden contrario horario, sino puede ser que los resultados no sean los que nosotros esperamos.


En la siguiente tabla se muestra las primitivas que acepta la funcion glBegin
GL_POINTS
los vertices que dibujemos solo dibujaran un punto
GL_LINES
cada dos vertices dibujara una linea, si la cantidad de vertices indicados es impar se elimina el ultimo.
GL_LINE_STRIP
se usan los vertices para dibujar lineas.Despues del segundo vertice, cada vertice subsiguente especifica el punto al que se extiende la linea.
GL_LINE_LOOP
igual que GL_LINE_STRIP pero el ultimo vertice de todos se unira con el primero de todos.
GL_TRIANGLES
Dibujara triangulos cada 3 vertices, si el numero de vertices indicados no se puede dibidir en 3 ignora los ultimos.
GL_TRIANGLE_STRIP
Dibujara un triangulo con los 3 primeros vertices despues con los 2 siguientes vertices y el ultimo de los 3 anteriores vuelve a dibujar un triangulo
GL_TRIANGLE_FAN
Dibuja un abanico de triangulos. Cada vertices despues del tercero se usa para dibujar otro triangulo.
GL_QUADS
Dibujara cuadrados cada 4 vertices. Si el numero de vertices no se puede dibidir en 4 ignora los ultimos vertices.
GL_QUAD_STRIP
Dibuja cuadrados consecutivos es decir, coge los dos ultimos vertices indicados con los dos nuevos y va dibujando cuadrados.
GL_POLYGON
con los vertices que indiquemos se dibuja un poligono convexo. El ultimo vertice indicado se cierra con el primero para asegurar que ha quedado cerrado.


En la siguiente imagen podemos ver como dibujarian las primitivas de OpenGL











Entonces si queremos dibujar 3 puntos en el espacio el codigo nos puede quedar de la siguiente forma:
glBegin GL_POINTS
glvertex3f 0,0,0
glvertex3f 0,10,0
glvertex3f 100,0,0
glend
Esto dibujara 3 puntos el primero en las coordenadas x = 0, y = 0, z = 0, el segundo en x = 0, y = 10, z = 0 y por ultimo el tercero en x = 100, y = 0 y z = 0
En el ejemplo de visual basic podéis ver como funcionan las primitivas explicadas.

CARACTERES GRAFICOS

CARACTERES GRÁFICOS PARA RECUADROS

Estos parámetros permiten redefinir los caracteres gráficos utilizados en la elaboración de recuadros de tipo 1 y 2 respectivamente. Sólo son aplicables a la versión PC del sistema, y cada uno de ellos consiste en una cadena de seis caracteres que definen:

1. Los lados verticales

2. Los lados horizontales

3. La esquina superior izquierda

4. La esquina superior derecha

5. La esquina inferior izquierda

6. La esquina inferior derecha

Por ejemplo:

11=-++++

12=******

El código ASCII (acrónimo inglés de American Standard Code for Information Interchange — (Código Estadounidense Estándar para el Intercambio de Información), pronunciado generalmente [áski], es un código de caracteres basado en el alfabeto latino tal como se usa en inglés moderno y en otras lenguas occidentales. Fue creado en 1963 por el Comité Estadounidense de Estándares (ASA, conocido desde 1969 como el Instituto Estadounidense de Estándares Nacionales, o ANSI) como una refundición o evolución de los conjuntos de códigos utilizados entonces en telegrafía.

Más tarde, en 1967, se incluyeron las minúsculas, y se redefinieron algunos códigos de control para formar el código conocido como US-ASCII.
El código ASCII utiliza 7 bits para representar los caracteres, aunque inicialmente empleaba un bit adicional (bit de paridad) que se usaba para detectar errores en la transmisión. A menudo se llama incorrectamente ASCII a otros códigos de caracteres de 8 bits, como el estándar ISO-8859-1 que es una extensión que utiliza 8 bits para proporcionar caracteres adicionales usados en idiomas distintos al inglés, como el español.

ASCII fue publicado como estándar por primera vez en 1967 y fue actualizado por última vez en 1986. En la actualidad define códigos para 33 caracteres no imprimibles, de los cuales la mayoría son caracteres de control obsoletos que tienen efecto sobre como se procesa el texto, más otros 95 caracteres imprimibles que les siguen en la numeración (empezando por el carácter espacio).
Casi todos los sistemas informáticos actuales utilizan el código ASCII o una extensión compatible para representar textos y para el control de dispositivos que manejan texto.

ASCII es, en sentido estricto, un código de siete bits, lo que significa que usa cadenas de bits representables con siete dígitos binarios (que van de 0 a 127 en base decimal) para representar información de caracteres. En el momento en el que se introdujo el código ASCII muchos ordenadores trabajaban con grupos de ocho bits (bytes u octetos), como la unidad mínima de información; donde el octavo bit se usaba habitualmente como bit de paridad con funciones de control de errores en líneas de comunicación u otras funciones específicas del dispositivo. Las máquinas que no usaban la comprobación de paridad asignaban al octavo bit el valor cero en la mayoría de los casos, aunque otros sistemas como las computadoras Prime, que ejecutaban PRIMOS ponían el octavo bit del código ASCII a uno.

El código ASCII define una relación entre caracteres específicos y secuencias de bits; además de reservar unos cuantos códigos de control para el procesador de textos, y no define ningún mecanismo para describir la estructura o la apariencia del texto en un documento; estos asuntos están especificados por otros lenguajes como los lenguajes de etiquetas.

PRIMITIVAS DE LLENADO DE AREAS

La tarea de los primitivos de llenado se puede separar en dos partes:

1. la decisión de que pixeles llenar (esto depende de la forma de la primitiva), y

2. la decisión mas sencilla de cual valor utilizar para el relleno.

En general, determinar que pixeles llenar consiste de tomar líneas de rastreo sucesivas que intersectan la primitiva y llenar en intervalos (spans) de pixeles adyacentes que están dentro de la primitiva de izquierda a derecha.

Para llenar un rectángulo con un color sólido, se asigna a cada pixel sobre una misma línea de rastreo desde el borde izquierdo al borde derecho el mismo valor de pixel; o sea llenamos cada intervalo de xmin a xmax. Se aprovecha de varios tipos de coherencias no solamente para convertir primitivas de 2D, pero también de 3D.

• Los intervalos explotan la coherencia espacial (spatial coherence) de una primitiva: el hecho que las primitivas a menudo no cambian de pixel en pixel dentro de un intervalo o de línea de rastreo a línea de rastreo. Se explota esta coherencia buscando solo aquellos pixeles donde ocurren cambios.

• Para una primitiva trazada de forma sólida, se asigna el mismo valor a todos los pixeles en un mismo intervalo, proporcionando coherencia de intervalo (span coherence).

• Un rectángulo trazado de forma sólida también muestra una fuerte coherencia de línea de rastreo (scan-line coherence) ya que líneas de rastreo consecutivas que intersectan el rectángulo son idéntica; mas tarde se usa también coherencia de arista (edge coherence) para los lados de polígonos generales.

La capacidad de manejar múltiples pixeles en un intervalo de forma idéntica es especialmente importante porque se debe escribir el frame buffer una palabra a la vez para minimizar el numero de accesos a memoria.

Conceptos del algoritmo de relleno de áreas

El algoritmo presentado a continuación considera polígonos cóncavos al igual que convexos, incluyendo aquellos que puedan tener huecos internos o intersectados por si mismos.

La siguiente figura ilustra el procedimiento de la línea de rastreo para el llenado sólido de polígono.

ALGORITMOS PARA TRAZOS DE LINEAS

Algoritmos para trazo de líneas

La ecuación de una recta puede anunciarse en la forma

y = m. x + b (1)

con m como pendiente de la recta y b como intercepción y.

Dado que los dos extremos de un segmento rectilíneo se especifican como (x1 , y1) y (x2 , y2), podemos determinar valores de la pendiente m y de la intersección y, b, con los siguientes cálculos:

m = (y2 - y1) / (x2 - x1) (2)

b = y1 - m. x1 (3)

Los algoritmos para desplegar líneas rectas se basan en la ecuación de la recta (1) y los cálculos que se dan en las ecuaciones (2) y (3).

Para cualquier intervalo dx de x a lo largo de una recta, podemos calcular el intervalo dy de y correspondiente de la ecuación 2 como;

dy = m . dx (4)

Esta ecuación forma la base para determinar tensiones de deflexión en dispositivos analógicos. La variación en la tensión de deflexión horizontal se hace proporcional a dx y el cambio en la tensión de deflexión vertical se hace proporcional al valor de dy calculado a partir de la ecuación 4.

Estas deflexiones se usan después para generar una línea con pendiente m entre los extremos que se especifican. Creamos un vector con cinco componentes, al que seguidamente le asignamos las coordenadas (unas cualesquiera puestas a modo de ejemplo):

Punto 2 D p1[5];

p1[0].x ← 100;
p1[0].y ← 20;
p1[1].x ← 60;
p1[1].y ← 20;
p1[2].x ← 50;
p1[2].y ← 60;
p1[3].x ← 80;
p1[3].y ← 40;
p1[4].x ← 110;
p1[4].y ← 60;

Finalmente, podemos dibujar las líneas, aprovechando un bucle:

DESDE i=0 MIENTRAS i<4>