sorting of edges of polygon

Question

Let us consider the vertices of the non-self intersecting polygon as 1.(x_1,y_1) 2.(x_2,y_2),...,6.(x_6,y_6).

We are also given with the pair points which form the edges of the polygon in a array. The array is {(1,4),(2,6),(2,5),(4,3),(6,1),(3,5)}'. Note that this edges are not consecutive and (x,y)=(y,x).

I need an algorithm to get array of the type $ (1,4),(4,3),(3,5),(5,2),(2,6),(6,1)$, so that I can get the consecutive edges one by another.

Thanks for your help.

Answer 1

It seems like you are working with graph-like data so perhaps the igraph package might be helpful.

points<-rbind(c(1,4),c(2,6),c(2,5),c(4,3),c(6,1),c(3,5))

library(igraph)
plot(minimum.spanning.tree(graph.edgelist(points)))

Answer 2

You did not provide a data structure for you polygon coordinates, so I assume that they are stored in a data.frame.

Data

d <- data.frame(from = c(1, 2, 2, 4, 6, 3), to = c(4, 6, 5, 3, 1, 5))

Code

getEdgesOrdered <- function(current, rest, result = list(unlist(current))) {
   if (NROW(rest) == 0) {
      result
   } else {
      to <- current$to
      wh <- match(to, rest$from)
      if (is.na(wh)) {
         wh <- match(to, rest$to)
         elem <- setNames(rest[wh, c("to", "from")], c("from", "to"))
      } else {
         elem <- rest[wh, c("from", "to")]
      }
      Recall(elem, rest[-wh, ], c(result, list(unlist(elem))))
   }
}

getEdgesOrdered(d[1,], d[-1,])

Explanation

The function takes the first edge and looks up the to node in the from column in the remaining data.frame. If it is not found there, it looks it up in the to column. The current edge is then appended to the result vector, the found edge is removed from the data.frame and it is the new edge to look up. When there are no rows left in the data.frame the algorithm stops and returns the search path.

Answer 3

Scan the edge list and fill two arrays: at index i, store the indexes of the two vertexes linked to vertex i, let p[N] and q[N] (initialize p and q with a reserved value meaning "unknown yet"). This takes linear time.

Then starting from (i, j):= (1, p[1]), find the next edge: if p[j] == i, then (j, q[j]) else (j, p[j]). Repeat until j == 1. This also takes linear time.

In your case:

1 -> 4, 6
2 -> 6, 5
3 -> 4, 5
4 -> 1, 3
5 -> 3, 2
6 -> 2, 1

The cycle is 1, 4, 3, 5, 2, 6.