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.

Answer 2

You could also create a decorator over the collection. Then you can define the indexer property to handle the out-of-bounds indexes.

This way you don't have to call mod all the time, it will be handled in the indexer. You do have to have a collection that supports indexing or IndexOf, such as List.

using System;
using System.Collections;
using System.Collections.Generic;

class Program
{
    private static void Main(string[] args)
    {
        var list = new List<int> { 1, 2, 3, 4, 5 };
        var decoratedList = new OverindexableListDecorator<int>(list);

        Console.WriteLine("-1st element is: {0}", decoratedList[-1]);
        Console.WriteLine("Element at index 3 is: {0}", decoratedList[3]);
        Console.WriteLine("6th element is: {0}", decoratedList[6]);

        Console.ReadKey();
    }
}

class OverindexableListDecorator<T> : IList<T>
{
    private readonly IList<T> store;

    public OverindexableListDecorator(IList<T> collectionToWrap)
    {
        this.store = collectionToWrap;
    }

    public T this[int index]
    {
        get
        {
            int actualIndex = IndexModuloCount(index);
            return store[actualIndex];
        }
        set
        {
            int actualIndex = IndexModuloCount(index);
            store[actualIndex] = value;
        }
    }

    public void RemoveAt(int index)
    {
        var actualIndex = IndexModuloCount(index);
        store.RemoveAt(index);
    }

    public void Insert(int index, T item)
    {
        var actualIndex = IndexModuloCount(index);
        store.Insert(actualIndex, item);
    }

    private int IndexModuloCount(int i)
    {
        int count = this.Count;
        return ((i % count) + count) % count;
    }

    #region Delegate calls
    public IEnumerator<T> GetEnumerator()
    {
        return store.GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

    public void Add(T item)
    {
        store.Add(item);
    }

    public void Clear()
    {
        store.Clear();
    }

    public bool Contains(T item)
    {
        return store.Contains(item);
    }

    public void CopyTo(T[] array, int arrayIndex)
    {
        store.CopyTo(array, arrayIndex);
    }

    public bool Remove(T item)
    {
        return store.Remove(item);
    }

    public int Count
    {
        get { return store.Count; }
    }


    public bool IsReadOnly
    {
        get { return store.IsReadOnly; }
    }

    public int IndexOf(T item)
    {
        return store.IndexOf(item);
    }

    #endregion
}