How to handle loops when going i-1

Question

I have a general question about looping in c#, especially when using lists.

I want to implement a simple polygon ear-slicing algorithm. Here is the algorithm:

(Source: http://www.diva-portal.org/smash/get/diva2:330344/FULLTEXT02 , Page 6)

I already implemented finding the ear tips. But there is the problem that I have to access i-1 or sometimes even i-2 elements of the list. My work around was to add last elements at the top of the list and first elements at the end of the list.

But when its comes to the next step when I have to remove some points from the polygon to go further trough the algorithm this approach is not good at all. So the problem is when I try to access elements at the end of the polygon when working at the beginning =) I hope that makes sense.

Here a snippet so you know what I'm talking about:

// suppose that i = 0 at the first step and polygonPoints is List<Vector>
Vector pi = new Vector(polygonPoints[i - 1]);
Vector pj = new Vector(polygonPoints[i]);
Vector pk = new Vector(polygonPoints[i + 1]);

// create line between i-1 and i+1
Line diagonal = new Line(pi,pk);

I would appreciate any suggetion. Thanks in advance.

Answer 1

I hope I understood the question correctly: Your problem is to calculate the neighbor indices at the end of your node list, right?

If so, why don't you just calculate the indices using a simple modulo function as that:

int mod(int k, int x)
{
    return ((k % x) + x) % x;
}
//...
polygonPoints[mod(i + n, polygonPoints.length)]

where n is your offset.

This means e.g. for a polygon point list with 10 elements, i = 9 and n = 1 that:

mod((9 + 1), 10) = 0

And in particular, that the next neighbor of the node at index 9 is at index 0.

And for i = 0 and n = -1:

mod((0 - 1), 10) = 9

Which means, that the previous node for the node at index 0 is at index position 9.