Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.