How can I determine if two vertices on a polygon are consecutive?

Question

Suppose I have a set of points that construct a convex polygon in the Cartesian plane with the points as its vertices. I randomly choose two vertices and want to know if they are consecutive vertices on the polygon. Does anyone know of an algorithm that would do this, as in you would input the array of points and the two vertices as parameters and it would return a boolean?

It's given that the polygon exists and is unique.

Answer 1

As the polygon is convex, it is simple! Two vertices are consecutive if all other vertices are located on the same side of the line that goes through these two points. This means that the cross product of the vector feom one of the pionts to the other one with the vector from the first point to any other one in the polygon have the same sign (all negative or all positive). For example, if those two points are called $P_1$ and $P_2$, you should compute all cross product of $\langle P_1, P_2\rangle$ with $\langle P_1, P_i\rangle$ ($P_i$ here means all other vertices).

Also, as discussed in the comment, we have some degenerate cases. The degenerate case is a common phenomenon in computational geometry, that is mostly handled separately. Here, the degenerate case is three points are located on a line.

Answer 2

Given that the polygon is convex, its centroid $C$ is in its interior. Test the gradients of the lines $CV$ for each vertex $V$. This gives a linear time test.

Answer 3

An alternative to OmG's answer (which is great) would be to sort your points into an ordered array where you can find any points neighbors by looking at the points on either side. This method would be very good if you need to work with the same polygon for many calculations as most work is done upfront but afterwards the cost of determining if two points are neighbors is very small.

So how do we sort the array?

Let's say we have an array of our unsorted points where each point contains its x and y coordinates.

var points = [{x:1, y:0}, {x:6, y:8}, {x:-10, y:12} ...etc]

First we want to find the left-most and right-most points i.e highest and lowest x-values. A function for this would look like the following:

//input the array of unsorted points
//also assuming a valid non-empty array
function getLeftMostPoint(points){
    //the point with the lowest x value.
    var leftMostPoint = points[0];
    for(var i = 1; i < points.length; i++){
        if(points[i].x < leftMostPoint.x){
            leftMostPoint = points[i];
        }
    }
    return leftMostPoint;
}

The rightmost point would be near-identical but the less-than would be swapped for a greater-than.

Next up we imagine we draw a line from our left-most point to our right-most point. Then we group all remaining points into two categories; those below the line and those above it.

//assuming we have left and rightmost points from above
//we are looping over the points (not shown here) and passing each one 
//as the current point in this function
//this will return a number. 
//If positive it means the current point is "above" the line
//negative means below the line and 0 means on the line.
function overOrUnder(leftMostPoint, rightMostPoint, currentPoint){
    return (currentPoint.x - leftMostPoint.x) * (rightMostPoint.y- leftMostPoint.y) - (currentPoint.y - leftMostPoint.y) * (rightMostPoint.x- leftMostPoint.x);
}

Now assuming we have stored all the points under/over into their own arrays we have all the info needed to build our sorted array or points.

1. We choose our starting point as the leftmostpoint
2. Then we add all values in the over array in x-ascending(smallest first) order.
3. Add the rightmostpoint
4. Add the values in the under array in x-descending order(biggest first)

The result is an array where each point connects to the next point in the array and the final point connects back to the first. Note that this method gives a non-intersecting polygon as its result regardless of if the input is convex or concave. The output will only be guaranteed convex if the input is guaranteed convex.

See below for more complete code

//Input: array of unsorted polygon points
//Output: NEW array of sorted polygon points
function sortPoints(points){
    var sortedPoints = [];

    //Get the leftmost and rightmost points
    var leftMost = getLeftMostPoint(points);
    var rightMost = getRigthMostPoint(points);

    //array to hold the points that are over/under or middle(on the line)
    var over = [];
    var under = [];
    var middle = [];

    //loop the points and put them in the appropriate array depending on where they sit relative to the line
    for(var i = 0; i < points.length; i++){
        //dont want/need to sort the left and right points
        if(points[i] != leftMost && points[i] != rightMost){
            var side = overOrUnder(leftMost, rightMost, points[i]);
            if(side < 0){
                under.push(points[i]);
            }else if(side > 0){
                over.push(points[i]);
            }else{
                middle.push(points[i]);
            }
        }
    }

    //There's an edge case with convex polygons where we don't know whether 
    //points on the line, i.e in the middle array, should be assigned to the over or 
    //under. The answer is we put them in the array which is empty
    if(middle.length > 0){
        if(over.length == 0){
            over = middle;
        }else{
            under = middle;
        }
    } 

    //as explained above we sort one descending and the other ascending.
    over.sort(function(a, b){
        return a.x - b.x;
    });

    over.sort(function(a, b){
        return b.x - a.x;
    });

    //now build up the array like explained above
    sortedPoints.push(leftMost);
    sortedPoints = sortedPoints.concat(under);
    sortedPoints.push(rightMost);
    sortedPoints = sortedPoints.concat(over);

    return sortedPoints;
}

function getLeftMostPoint(points){
    //the point with the lowest x value.
    var leftMostPoint = points[0];
    for(var i = 1; i < points.length; i++){
        if((points[i].x < leftMostPoint.x) || (points[i].x == leftMostPoint.x && points[i].y > leftMostPoint.y)){
            leftMostPoint = points[i];
        }
    }
    return leftMostPoint;
}

function getRightMostPoint(points){
    //the point with the lowest x value.
    var rightMostPoint = points[0];
    for(var i = 1; i < points.length; i++){
        if((points[i].x > rightMostPoint.x) || (points[i].x == rightMostPoint.x && points[i].y > rightMostPoint.y)){
            rightMostPoint = points[i];
        }
    }
    return rightMostPoint ;
}

function overOrUnder(leftMostPoint, rightMostPoint, currentPoint){
    return (currentPoint.x - leftMostPoint.x) * (rightMostPoint.y- leftMostPoint.y) - (currentPoint.y - leftMostPoint.y) * (rightMostPoint.x- leftMostPoint.x);
}

And there we have it! and now to check if points are next to each other is easy something like:

//given sorted array is available 
//this would return a boolean indicating whetehr point 1 and point 2 are next to each other
function(p1, p2) {
    var neighbours = false;
    var p1Index = sortedPoints.indexOf(p1);
    var p2Index = sortedPoints.indexOf(p2);

    //one index apart next to each other
    //or the edge cases where the points are at the start and ends of the array
    if (Math.abs(p1Index - p2Index) == 1) {
        neighbours = true;
    } else if (p1Index == 0 && p2Index == sortedPoints.length - 1) {
        neighbours = true;
    } else if (p1Index == sortedPoints.length - 1 && p2Index == 0) {
        neighbours = true;
    }
    return neighbours;
}