# Shoelace formula for polygon area with unsorted list of vertices

I want to apply the Shoelace formula to a list of polygon vertices, whose order is known, but they are stored in memory in the wrong order:

Point Nr.    x    y
1            1    0
4            1    1
2            0    0
3            0    1


Since the Shoelace formula contains products of coordinates (x1*y2 etc.) of successive vertices, I would have to sort them first. Is there a way to avoid this?

-
What is your motivation why you don't want to sort things? Is allocating a new array with the size of the polygon acceptable? You could use that to store the order in which your factors should be accessed, or something like that. In the end you have to compute the same products as the sorted version, so some kind of sorting seems unavoidable. –  MvG Jan 7 '13 at 15:54
New allocation and sorting are exactly the things I want to avoid. –  Rafael Reiter Jan 8 '13 at 12:37
You can avoid allocation by performing a linear search for the next point, leading to an O(n²) algorithm. –  MvG Jan 8 '13 at 13:32
Correct, but I want to avoid sorting. –  Rafael Reiter Jan 10 '13 at 12:27