Check if point inside polygon or not

help
1

Given list of points of polygon and one point
Can anyone explain how to check given point is inside polygon or not ?
I want to understand this to get better understanding in CONTAIN problem.
Thanks in advance.

2 Likes
2

Don’t know about other languages but in java there is a class Polygon which has method contains(x,y)

1 Like
3

I am interested in algorithm to check.
Thanks for reply.

4

Me too, that seemed to be the only problem in my otherwise perfect code.

1 Like
5

Suppose you have polygon made up of N points and let (x,y) be the point to check whether it lies inside or outside it. You can consider a horizontal ray from this point and if the number of intersections of this ray with the polygon is odd then it lies inside it and if its even then it will be outside.

But you also have to take care of the ray when it coincides with the edge. In this case the result will vary on orientation of the polygon. So to tackle with this case take the edge and check if the point lie on it or not.

1 Like
6

I referred to this blog.
Head to solution 3(2D).
http://www.eecs.umich.edu/courses/eecs380/HANDOUTS/PROJ2/InsidePoly.html

1 Like
7

For convex polygon it is very simple-
A convex polygon with vertices from 0 to n-1 can be imaginary divided in 2 convex polygons by joining vertex 0 with vertex n/2.
Therefore, a point is inside the polygon iff it is inside one half, or the other half. There you have an easy binary search solution.

ll area(pt pa, pt pb, pt pc)
{
    return pa.x * (pb.y - pc.y) + pb.x * (pc.y - pa.y) + pc.x * (pa.y - pb.y);
}

bool isInConvex(vector<pt> &A, const pt &P)
{
    ll n = A.size(), lo = 1, hi = A.size() - 1;

    if (area(A[1], A[0], P) <= 0)
        return 0;
    if (area(A[0], A[n - 1], P) <= 0)
        return 0;

    while (hi - lo > 1)
    {
        ll mid = (lo + hi) / 2;

        if (area(A[mid], A[0], P) > 0)
            lo = mid;
        else
            hi = mid;
    }

    return area(A[hi], A[lo], P) > 0;
}

Here function named area is just to find out the orientation of the triangle.
And it is assumed that all the points of the convex polygon are clockwise.

5 Likes
8

Afaik, that takes O(n) per query. Can you please explain a better one? I think that there is a O(log n) algorithm for checking this.

1 Like
9

Nicely explained.

10

You can also refer this:
https://cp-algorithms.com/geometry/point-in-convex-polygon.html

Its an O(logn) approach.

1 Like
11

thanks

12

Check these amazing blogs by Oleksandr Bacherikov (Al.Cash)

A lot of geometry questions can be solved using the template he shared. :raised_hands:

13

nice blogs. thanks.

14

For CONTAIN problem, I used the convex hull algorithm to check if a point lied inside the current hull. I added the candle point into the set of hull points, called the convex hull function on this modified set, and checked if the candle point lies on the new hull. If present, the candle point lies outside the original polygon.

The algorithm can definitely be optimised (only adjacent points are required to be checked after inserting the candle point in the sorted order), however I preferred to not mess up my code further.

1 Like