Clever Geek Handbook

Topological sort for a grid of arbitrary points?

I have a grid of x, y points where you can move from one point to an immediately visible point if the new point has either a larger x, y, or both. How can I sort this topologically?

+3


source to share


2 answers


Since this is a transitive relationship (i.e. if you can go from a to b and b to c, then you should be able to go from a to c), you can simply sort your points to achieve topological order.

For example, this C code will perform a topological view of an array of points by ordering the points based on the first coordinate or the second coordinate if the first coordinate matches.

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);
...


For your example (0,0) (1.99) (9.16) (16.9) (36.64) (64.36) (100,100) these points are already sorted according to the first coordinate so this would be the output call qsort.

This approach works because if you can go from a to b, then a must either have a smaller x (and so it appears earlier in the list), or the same x and a smaller y (and reappears earlier in the sorted list).

+1


source


There are many topological orders of this mesh. However, some of them are very easy to compute without any overhead:

  • Iterate through the lines from top to bottom, left to right.
  • Iterate through columns from left to right, bottom to top.
  • A list of all points whose sum is x and y is zero, then the sum of x and y is 1, etc.


Hope this helps!

+2


source






More articles:


All Articles