Algorithm for arranging Cartesian points

Question

I have few Cartesian points of the form : (x,y)
where x and y both are non-negative integers.

For e.g.
(0,0) , (1,1), (0,1)

I need an algorithm to arrange the above points
in such a way that going from one point to other
changes either x or y by 1.

In other words, I would like to avoid
diagonal movement.

So, the above mentioned points will be arranged like :
(0,0), (0,1), (1,1).

Similarly for (0,0),(1,1),(0,2)
there is no such arrangement possible.

I am not sure about what to call it
but I would call it Manhattan ordering.

Can anyone help?

Answer 1

This could be simplified as minimizing the distance between each consecutive point. Going from (0,0) to (0,1) is simply 1 unit, but going from (0,0) to (1,1) is actually sqrt(2). So if you arrange the points into a graph, and then perform a simple minimum-total-distance traversal (traveling salesman), it should arrange them correctly.

Edit: If you never want a step that would be larger than 1, simply do not add any edges that are greater than 1. The traversal will still work correctly, and ignore any paths that require a movement > 1.

Edit 2: To clarify further, you can use any edge selection algorithm you wish. If you're ok with it moving 2 spaces, as long as the space is not diagonal, then you may choose to put an edge between (0,2) and (0,4). The minimum distance algorithm will still work. Simply place the edges in a smart way, and you can use any number of selection criteria to determine the outcome.

Answer 2

One way to do this is to create two sorted lists of the coordinates. One sorted by x and one sorted by y. Then, recursively find a solution.

Code coming (not sure what language yet; maybe pseudocode?)... Edit - nevermind, since my answer isn't as good as some of the others anyways.

Answer 3

You can construct a graph with the vertices being your points, and the edges being the valid steps.

What you're then looking for is a Hamiltonian path for this graph. This, in its general form, is an NP-complete problem, which means there is no known efficient solution (i.e. one that scales well with the number of points). Wikipedia describes a randomized algorithm that is "fast on most graphs" and might be of use:

Start from a random vertex, and continue if there is a neighbor not visited. If there are no more unvisited neighbors, and the path formed isn't Hamiltonian, pick a neighbor uniformly at random, and rotate using that neighbor as a pivot. (That is, add an edge to that neighbor, and remove one of the existing edges from that neighbor so as not to form a loop.) Then, continue the algorithm at the new end of the path.

A more efficient solution might exist for this particular situation, though.

Answer 4

Think of it as a graph where each node as at most four edges. Then do depth/breadth-first search.

Answer 5

If you are looking for an arrangement that does not repeat vertices:

What you seem to be looking for is a Hamiltonian Path in a Grid Graph.

This is known to be NP-Complete for general Grid Graphs, see Hamilton Paths in Grid Graphs.

So you can probably try your luck with any of the approximate/heuristic/etc algorithms known for Hamiltonian Path/Euclidean Traveling Salesman Problem.

---

If you are looking for an arrangement that can repeat, but want the minimum possible number of points in the arrangement:

This is again NP-Complete. The above problem can be reduced to it. This is because the minimum possible walk has n vertices if and only if the graph has a hamiltonian path.

---

If you are just looking for some arrangement of points,

Then all you need to do is check if the graph is connected. If it is not connected, there can be no such arrangement.

You can do a depth first search to figure that out. The depth first search will also give you such an arrangement in case the graph is connected.

If you want something closer to optimal (but in reasonably fast time), you can probably use approximation algorithms for the Euclidean Traveling Salesman problem.

Answer 6

How about a brute force recursive REXX routine... Try all possible paths and print those that work out.

/* rexx */
point. = 0  /* Boolean for each existing point */
say 'Enter origin x and y coordinate:'
pull xo yo
point.xo.yo = 1  /* Point exists... */
say 'Enter destination x and y coordinate:'
pull xd yd
point.xd.yd = 1  /*  Point exists... */
say 'Enter remaining x and y coordinates, one pair per line:'
do forever
  pull x y
  if x = '' then leave
  point.x.y = 1
end

path = ''
call findpath xo yo path
say 'All possible paths have been displayed'
return

findpath: procedure expose point. xd yd
arg x y path
if \point.x.y then return               /* no such point */
newpoint = '(' || x y || ')'
if pos(newpoint, path) > 0 then return  /* abandon on cycle */
if x = xd & y = yd then                 /* found a path */
  say path newpoint
else do                                 /* keep searching */
  call findpath x+1 y path newpoint
  call findpath x-1 y path newpoint
  call findpath x y+1 path newpoint
  call findpath x y-1 path newpoint
  end
return 

Example session:

Path.rex
Enter origin x and y coordinate:
0 0
Enter destination x and y coordinate:
2 2
Enter remaining x and y coordinates, one pair per line:
0 1
1 1
2 1
1 2

 (0 0) (0 1) (1 1) (2 1) (2 2)
 (0 0) (0 1) (1 1) (1 2) (2 2)
All possible paths have been displayed

Don't try this on anything big though - could take a very long time! But then the question never mentioned anything about being an optimal solution.