algorithm - Tipo topológico para una grilla de puntos arbitrarios?

graph grid

Question

Tengo una grilla de puntos x, y donde puedes moverte de un punto a un punto inmediatamente visible, siempre y cuando el nuevo punto tenga una x, una, o ambas mayores. ¿Cómo ordenaría esto topológicamente?

Answer 1

Debido a que esta es una relación transitiva (es decir, si puedes ir de a a b, y de b a c, entonces debes ser capaz de ir de aa c) simplemente puedes ordenar tus puntos para lograr un orden topológico.

Por ejemplo, este código C realizaría un tipo topológico de una matriz de puntos al ordenar los puntos según la primera coordenada, o por la segunda coordenada si la primera coordenada coincide.

int C[1000][2];
int compar(const void*a,const void*b)
{
int *a2=(int*)a;
int *b2=(int*)b;
int d=a2[0]-b2[0];
if (d)
return d; // Sort on first coordinate
return a2[1]-b2[1]; // Sort on second coordinate
}
...
qsort(C,1000,sizeof(int)*2,compar);
...

Para su ejemplo (0,0) (1,99) (9,16) (16,9) (36,64) (64,36) (100,100), estos puntos ya están ordenados según la primera coordenada, por lo que ser el resultado de la llamada a qsort.

Este enfoque funciona porque si puedes ir de aa b, entonces debes tener una x más pequeña (y así aparece antes en la lista), o la misma xy una y más pequeña (y aparece de nuevo antes en la lista ordenada).

Answer 2

Hay una gran cantidad de ordenamientos topológicos de esta cuadrícula. Sin embargo, algunos de ellos son muy fáciles de calcular sin ningún espacio adicional:

1. Itera en las filas de abajo hacia arriba, de izquierda a derecha.
2. Itera a través de las columnas de izquierda a derecha, de abajo hacia arriba.
3. Enumera todos los puntos cuya suma de xey es cero, luego cuya suma de xey es 1, etc.

¡Espero que esto ayude!