How to get all n sets of three consecutives elements in an array or arraylist with a for statement ?

Question

Hi,

I'm trying to do a convex hull approach and the little problem is that I need to get all sets of three consecutive vertices, like this:

private void isConvexHull(Ponto[] points) {
        Arrays.sort(points);
        for (int i = 0; i <points.length; i++) {
            isClockWise(points[i],points[i+1],points[i+2]);
        }
     //... 
    }

I always do something that I don't consider clean code. Could please help me find one or more ways to this? I want it to be circular, i.e., if my fisrt point of the a set is the last element in the array, the 2nd element will be the 3rd in the list and the 3rd in that set will be the the 2nd element in the list, and so on. They must be consecutive, that's all.

Answer 1

The remainder "trick"

You can use the % "trick" (% is the remainder operator JLS 15.17.3) for circular indexing. Here I will illustrate the general idea using a String instead.

    String s = "ABCDE";
    final int L = s.length();
    for (int i = 0; i < L; i++) {
        System.out.format("%c%c%c ",
            s.charAt(i),
            s.charAt((i + 1) % L),
            s.charAt((i + 2) % L)
        );
    } // prints "ABC BCD CDE DEA EAB "

---

An Iterator approach

If you're doing this triplet processing often, though, it will be a better overall design to have an Iterator<PointTriplet> or something similar.

Here's a prototype to illustrate the idea:

import java.util.*;

public class CircSubArray {
    static <T> Iterator<T[]> circularIterator(final T[] arr, final int K) {
        return new Iterator<T[]>() {
            int index = 0;
            final int L = arr.length;
            T[] sub = Arrays.copyOf(arr, K); // let it do the dirty work!

            @Override public boolean hasNext() {
                return index < L;
            }
            @Override public T[] next() {
                for (int i = 0; i < K; i++) {
                    sub[i] = arr[(index + i) % L];
                }
                index++;
                return sub; // we always overwrite; no need to .clone()
            }
            @Override public void remove() {
                throw new UnsupportedOperationException();
            }
        };
    }   
    public static void main(String[] args) {
        String[] arr = { "s1", "s2", "s3", "s4", "s5", "s6" };

        Iterator<String[]> iter = circularIterator(arr, 4);
        while (iter.hasNext()) {
            System.out.println(Arrays.toString(iter.next()));
        }
    }
}

This prints:

[s1, s2, s3, s4]
[s2, s3, s4, s5]
[s3, s4, s5, s6]
[s4, s5, s6, s1]
[s5, s6, s1, s2]
[s6, s1, s2, s3]

---

A List-based solution

As Effective Java 2nd Edition says, Item 25: Prefer lists to arrays. Here's a solution that redundantly stores the first K-1 elements at the end of the List, and then simply uses subList to get K elements at a time.

    String[] arr = { "s1", "s2", "s3", "s4", "s5", "s6" };

    final int L = arr.length;
    final int K = 3;
    List<String> list = new ArrayList<String>(Arrays.asList(arr));
    list.addAll(list.subList(0, K-1));

    for (int i = 0; i < L; i++) {
        System.out.println(list.subList(i, i + K));
    }

This prints:

[s1, s2, s3]
[s2, s3, s4]
[s3, s4, s5]
[s4, s5, s6]
[s5, s6, s1]
[s6, s1, s2]

Since subList is a view, this does not have to do the O(K) shifting that the array-based solution does. This also shows the expressiveness of List over arrays.

Answer 2

Can you elaborate the problem with some sample data ?

Answer 3

Simply remember the previous two points, starting at the end, and shift them with each iteration.

private static boolean isConvexHull(Ponto[] points)
{
    final int len = points.length;
    if (len < 3) return false;
    Arrays.sort(points);

    Ponto p1 = points[len - 2];
    Ponto p2 = points[len - 1];
    for (Ponto p3 : points)
    {
        if (!isClockWise(p1, p2, p3)) return false;
        p1 = p2;
        p2 = p3;
    }
    return true;
}

By the way, how exactly do you sort the array? What is the sorting criterion?