tabitaCatalan / python.ForceBundle

Python implementation of Force-Directed Edge Bundling for Graph Visualization
GNU General Public License v3.0
2 stars 0 forks source link

Magnitud de la fuerza electrostática #6

Closed tabitaCatalan closed 3 years ago

tabitaCatalan commented 3 years ago

Fuerza electrostática en el paper

Es un tema interesante. Si vemos el paper, la definen como en la imagen. image

Pensemos cuidadosamente en lo que dice el paper. Consideremos dos puntos p y q y llamemos L a la distancia entre ellos, ie, L = norm(p-q). Necesitamos encontrar un vector que apunte desde p a q, cuya magnitud sea 1/L. El vector q-p apunta en la dirección correcta, pero su norma es L, así que deberíamos dividir por L**2.

Problemas prácticos

Sin embargo, al poner el esquema numérico en práctica, surgen inestabilidades cuando dos partículas se acercan: cuando están demasiado cerca se atraen con tanta fuerza que se pasan de largo, hacen un desplazamiento tan grande en dirección a la otra que terminan alejándose.

Problema numérico con partículas muy cercanas

Solución

Opción 1: cambiar a fuerza constante

En la práctica, es conveniente que se atraigan con una fuerza contante la una a la otra (o sea, dividiendo por L en lugar de L**2). Esto es lo que hicieron en d3.ForceBundle:

if ((Math.abs(force.x) > eps) || (Math.abs(force.y) > eps)) {
    var diff = (1 / Math.pow(custom_edge_length({
        'source': subdivision_points_for_edge[compatible_edges_list[oe]][i],
        'target': subdivision_points_for_edge[e_idx][i]
    }), 1));

    sum_of_forces.x += force.x * diff;
    sum_of_forces.y += force.y * diff;
}

Como puede verse, la variable diff solo está elevada a la potencia 1.

Opción 2: forzar a que ocupen la misma posición cuando están a punto de pasarse.

Esto no lo he probado, pero una vez que dos nodos están lo suficientemente cerca (noción por definir), deberían ser tratados como uno solo. Esto significaría ubicarlos a ambos en el punto medio... pero esto tiene otro tipo de complicaciones. No se ejerce sobre ellos la misma fuerza proveniente de otras aristas, esto debido a las medidas de compatibilidad. Debería moverse juntos, como un nodo con el doble de masa, pero esto se vuelve mucho más difícil de seguir. Creo que esta solución es impracticable.