Geometría

Algoritmos geométricos

Analizador Diferencial Digital (algoritmo gráfico)

En Gráficos por ordenador, una implementación de hardware o software de un Analizador Diferencial Digital (DDA) se usa para la interpolación lineal de variables sobre un intervalo entre un punto de comienzo y un punto de fin. Los DDAs se usan para rastreo de líneas, triangulos y polígonos. En la implementación más simple del algoritmo DDA interpola valores en intervalo [(x_inicio, y_inicio), (x_fin, y_fin)] por calculo para cada x_i las ecuaciones x_i = x_i−1+1, y_i = y_i−1 + Δy/Δx, donde Δx = x_fin − x_inicio y Δy = y_fin − y_inicio.

Si m>=0 (pendiente positiva)
  Si m<=1
    de izquierda a derecha
       * muestreo de x (Δx =1)
       * yk+1 = redondeo(yk + m) k=1,2,...
    de derecha a izquierda
       * muestreo de x (Δx =-1)
       * yk+1 = redondeo(yk - m) k=1,2,...
  Si m > 1 (para evitar la aparición de agujeros)
    de izquierda a derecha
       * muestreo de y (Δy =1)
       * xk+1 = redondeo(xk + 1/m) k=1,2,...
    de derecha a izquierda
       * muestreo de y (Δy =-1)
       * xk+1 = redondeo(xk - m) k=1,2,...
Si m<0 a="" de="" derecha="" izquierda="" m="" muestreo="" negativa="" pendiente="" si="" style="line-height: 1em;" sub="" x="1)" y="">k+1

= redondeo(y_k + m) k=1,2,... de derecha a izquierda * muestreo de x (Δx =-1) * y_k+1 = redondeo(y_k - m) k=1,2,... Si |m| > 1 (para evitar la aparición de agujeros) de izquierda a derecha * muestreo de y (Δy =1) * x_k+1 = redondeo(x_k + 1/m) k=1,2,... de derecha a izquierda * muestreo de y (Δy =-1) * x_k+1 = redondeo(x_k - m) k=1,2,...

  public void DDA(int x0, int y0, int x1, int y1, Graphics g)
    {
        int dx = x1 - x0;
        int dy = y1 - y0;
 
        g.drawLine( x0, y0, x1, y1);
        if (Math.abs(dx) > Math.abs(dy)) {          // pendiente < 1
            float m = (float) dy / (float) dx;
            float b = y0 - m*x0;
            if(dx<0)
                dx =  -1;
            else
                dx =  1;
            while (x0 != x1) {
                x0 += dx;
                y0 = Math.round(m*x0 + b);
                g.drawLine( x0, y0, x1, y1);
            }
        } else
        if (dy != 0) {                              // slope >= 1
            float m = (float) dx / (float) dy;      // compute slope
            float b = x0 - m*y0;
            if(dy<0)
                dy =  -1;
            else
                dy =  1;
            while (y0 != y1) {
                y0 += dy;
                x0 = Math.round(m*y0 + b);
                g.drawLine( x0, y0, x0, y0);







El árbol de Steiner, nombrado en honor a Jakob Steiner, es un problema de optimización combinatoria consistente en buscar la interconexión más corta para un conjunto de elementos dado. Es superficialmente similar al problema del árbol recubridor mínimo: dado un conjunto V de puntos (vértices), interconectalos por la red gráfica de menor longitud, donde la longitud es la suma de las medidas de todos los lados.

La diferencia entre el problema del árbol de Steiner y el del árbol recubridor es que, en el primero se pueden añadir vértices intermedios y lados extras al grafo con el fin de reducir la longitud del árbol recubridor. Los vértices introducidos para decrecer la longitud total de las conexiones son conocidos como puntos de Steiner. Ha sido demostrado que la conexión resultante es un árbol, llamado árbol de Steiner. Pueden existir varios árboles de Steiner para un conjunto dado de vértices iniciales.

El árbol de Steiner tiene aplicaciones en el diseño de circuitos eléctricos y redes de telecomunicaciones. La mayoría de las versiones del problema de Steiner son NP-completo. De hecho uno de estos pertenece a la lista de 21 problemas NP-completos de Karp. Algunos casos restringidos pueden ser resueltos por tiempo polinómico, sin embargo en la práctica se usa laheurística en su lugar.







Árbol de Steiner para tres puntos A,B y C. Nótese que no hay conexiones directas entre ellos. El punto de Steiner S está puesto en el punto de Fermat del triángulo ABC.







Solución para cuatro puntos. Nótese que hay dos puntos de Steiner, S1 y S2




















PUNTO DE STEINER   (1/2)



r6
primer triángulo de Brocard, triángulos paralelógicos
r17
primer triángulo de Brocard, simediano
r23
elipse circunscrita de Steiner, circunferencia circunscrita
r24
simediano, baricentro, polo trilineal
d
punto de Parry
d
hipérbola de Wallace
d
punto de Tarry
d
punto X(115)
r101
ejes de Steiner, simediano, baricentro, circuncentro, punto de Tarry
r118
perspector, parábola de Kiepert
r173
puntos de Fermat, anticomplemento
r237
recta de Simson, recta de Brocard
r258
cónica inscrita, perspector
r435
punto isogonal del infinito, puntos de Brocard
r513
triángulos de Fermat, perspectiva, puntos concíclicos
r559
anticomplemento, medianas, perspectiva, hipérbola de Kiepert
r625
punto de Tarry, puntos de Brocard, puntos antigonales, triángulo ceviano
r644
punto X(110), cónica circunscrita, recta de Lemoine, recta de De Longchamps, circunferencia circunscrita, rectas isogonales,rectas isotómicas
r648
triángulo medial, triángulo órtico, recta de Simson
r701
punto X(681), recta de Euler, recta de Brocard, punto X(110)
r721
cociente ceviano, punto X(100), punto X(190)
r730
retrocentro, punto X(74), punto X(376)
r762
triángulo de Morley, triángulo circuntangencial, circunferencia circunscrita, puntos isotómicos, elipse circunscrita de Steiner, tercer punto de Brocard,triángulos homotéticos