Should point on the edge of polygon be inside polygon?

Question

Recently I've faced with one little but majour problem: is point on the edge of polygon be inside polygon?

What I mean - currently I am trying to implement 2D geometry library in JS for custom needs and there is method, lets say polygon.contains(point).

So my question is - when point is situated on one of the polygon's edges - as result the point is inside or outside of the polygon? Additional question for vertices: if point is right on top of polygon's vertex - is it inside or outside?

Algo that I've used is taken from here and looks like:

int pnpoly(int nvert, float *vertx, float *verty, float testx, float testy)
{
    int i, j, c = 0;
    for (i = 0, j = nvert-1; i < nvert; j = i++) {
        if ( ((verty[i]>testy) != (verty[j]>testy)) &&
          (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j] - verty[i]) + vertx[i]) )
           c = !c;
    }
    return c;
}

Also, there is a quote from the site:

PNPOLY partitions the plane into points inside the polygon and points outside the polygon. Points that are on the boundary are classified as either inside or outside.

And it is total true, in some situations it returns TRUE, and in some FALSE.

Actually, this is not what I'm needed. So my question is beginning to expand - which behaviour is correct when point is on the edge of polygon - is it inside or outside. And do you have a better algo with predictable behaviour?

UPDATE:

Okay, I'm found another algo, which is called "winding number" and to test this I'm using only polygons and points with integer values:

function isLeft(p0, p1, p2){
    return ( Math.round((p1.x - p0.x) * (p2.y - p0.y)) - Math.round((p2.x - p0.x) * (p1.y - p0.y)) );
}

function polygonContainsPoint(polygon, point){
    var i, j, pointi, pointj;
    var count = 0;
    var vertices = polygon.vertices;
    var length = vertices.length;
    for (i = 0; i < length; i++){
        j = (i + 1) % length;
        pointi = vertices[i];
        pointj = vertices[j];
        if (pointi.y > point.y){
            if (pointj.y <= point.y && (isLeft(pointi, pointj, point) < 0)){
                --count;
            }
        } else if (pointj.y > point.y && (isLeft(pointi, pointj, point) > 0)){
            ++count;
        }
    }
    return 0 !== count;
}

As you can see there is no division; multiplication is wrapped into round() method, so there is no way for floating point errors. Anyway, I'm getting same result as with even-odd algo. And I think I started to see the "pattern" in this strange behaviour: the left and top edges may tell that point is inside of polygon, but when you're tryed to put point on one of the right or bottom edges - it may return false.

This is not good for me. Maybe some of you know some algo with more predictable behaviour?

Antonyantonym

It usually depends on your needs. For physics and collision detection, you want it to be true for its boundary. For many math-related things you may want it to be false. – Garrott

@HyperNeutrino I'm confused.. for physics its true, for math its not. I thought it should has exact same result of any kind of things. Anyway, I'm working with images so.. should I expect true? – Antonyantonym

The code uses division of floating point numbers; the mixed results you're getting could simply be down to rounding errors. – Purchasable

@m69 , okay, I'm agreed, maybe it is truth for the first algo, but I'm found another one and got same results – Antonyantonym

I use an additional term, I have isInside, isOutside and isTouching. All points inside are also touching, some points outside may be touching. That and I generally use a rather large epsilon 1e-4, or use a more complicated tube, ball and one sided surface model that does not allow non 3D objects such as points, lines, line segments, polygons. The issue is not whether you are inside or outside, it is the seams, you don't want a ray to pass between two polygons that share an edge but with different vertices, that is bad for all types of use – Onaonager

Answer 1

The simple answer to the question is that a point on the edge is neither inside, nor outside of polygon, it is on the boundary of the polygon - the third option. But typically it does not matter (as supported by your quotations), and what matters is to avoid the errors in classification of points, which are really deep inside or outside.

Point-in-polygon problem is sometimes called the Parity Algorithm:

• Let r be the horizontal half-line whose left endpoint is the test point.
• Count the number of intersections between r and the edges of the polygon. If that number is odd, then the test point lies within the polygon, and if the number is even, then it lies outside the polygon.

Here are some examples:

• (a), (b) - not-degenerate cases, where half-line either does not intersect the edge or crosses it.
• (c), (d), (e), (f) - four degenerate cases that have to be taken into account.

A correct answer is obtained if cases (c) and (e) are counted as one crossing and cases (d) and (f) are not counted at all. If we write the code for the above algorithm, we realize that a substantial amount of the efforts is required to cover the four degenerated cases.

With more complex algorithms and especially in 3D, the amount of efforts to support degenerate cases increases dramatically.

The above problem and explanation appear in the introduction to Simulation of Simplicity article by Herbert Edelsbrunner and Ernst Peter Mucke. And proposed solution is to get rid of all degenerations by virtual minimal perturbation of input points. After that a tested point will never be on the edge, but only inside or outside of polygon.

Blancmange