5
$\begingroup$

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.

$\endgroup$
12
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Almost. A polygonal convex hull can have multiple points on one of its segments. (Easiest example: the set $\{1,2\} \times \{1,2,3\}$.) However, adding a "check that there are no points on this edge in the segment between the two given points" is as easy to do as what you have described (using two half-spaces bounded by perpendiculars to the containing edge). $\endgroup$ – Eric Towers Oct 21 at 6:25
  • $\begingroup$ @EricTowers: Those points don't form the vertices of a convex polygon. $\endgroup$ – user2357112 supports Monica Oct 21 at 6:30
  • 1
    $\begingroup$ @user2357112 they sure do. Think of a rectangle with vertices added in the middle of the edges. It still looks like a rectangle so it's still convex. $\endgroup$ – Eric Duminil Oct 21 at 7:50
  • $\begingroup$ As two different erics said this wont work when the cross product in this example is 0, which would mean it lies on the same line. Luckily this can be accounted for by finding the distance between the points on the same line using pythagoras theorem. But you must be careful and take into account direction as the two closest points are not necessarily the two either side. You can test for direction if we think about the line as a vector and the two points either side are the closest points for the same vector, and the opposite vector. $\endgroup$ – Tim Andrews Oct 21 at 10:30
  • 1
    $\begingroup$ @user2357112 : Again, you are reversing OP's construction. OP has a set of points, all of which are declared vertices, even the ones which land on segments bounded by other vertices. You seem to want to start with a polygon and extract the set of vertices from the extreme points of that object. But that is not the construction you are given. $\endgroup$ – Eric Towers Oct 22 at 2:11
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What do you mean, "test the gradients"? Do you mean that all the other gradients should be outside of the range defined by the gradients calculated with the two input vertices? $\endgroup$ – Eric Duminil Oct 21 at 7:52
  • $\begingroup$ It's a bit more subtle than than, because of wrap-around between $\pm \infty$ and because that means there are two ranges. But essentially, yes. $\endgroup$ – Peter Taylor Oct 21 at 8:00
4
$\begingroup$

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;
}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.