Algorithm to tell whether a point is inside an area [duplicate]

Question

I am recently working on a project which has an algorithm to tell whether a point is inside an area.

The area looks like this:

{"state": "Washington", "border": [[-122.402015, 48.225216], [-117.032049, 48.999931], [-116.919132, 45.995175], [-124.079107, 46.267259], [-124.717175, 48.377557], [-122.92315, 47.047963], [-122.402015, 48.225216]]}

It is easy if the area is a rectangle. However, the area is irregular. One of the idea I have is to check whether a point is in the 'inner' side of every line of the area. However, the performance is not good. Any idea?

Answer 1

First of all, very interesting question!! Although it might be a duplicated question, but I am still going to post another workable answer different from that post to encourage this new guy.

The idea is to use the sum of angles to decide whether the target is inside or outside. If the target is inside an area, the sum of angle form by the target and every two border points will be 360. If the target is outside, the sum will not be 360. The angle has direction. If the angle going backward, the angle is a negative one. This is just like calculating the winding number.

The provided input data [[-122.402015, 48.225216], [-117.032049, 48.999931], [-116.919132, 45.995175], [-124.079107, 46.267259], [-124.717175, 48.377557], [-122.92315, 47.047963], [-122.402015, 48.225216]] is clockwise (you can check google map). Therefore, my code assume that the positive angle is clockwise one.

Refer this for the idea:

The following is the python code that implements it.

def isInside(self, border, target):
    degree = 0
    for i in range(len(border) - 1):
        a = border[i]
        b = border[i + 1]

        # calculate distance of vector
        A = getDistance(a[0], a[1], b[0], b[1]);
        B = getDistance(target[0], target[1], a[0], a[1])
        C = getDistance(target[0], target[1], b[0], b[1])

        # calculate direction of vector
        ta_x = a[0] - target[0]
        ta_y = a[1] - target[1]
        tb_x = b[0] - target[0]
        tb_y = b[1] - target[1]

        cross = tb_y * ta_x - tb_x * ta_y
        clockwise = cross < 0

        # calculate sum of angles
        if(clockwise):
            degree = degree + math.degrees(math.acos((B * B + C * C - A * A) / (2.0 * B * C)))
        else:
            degree = degree - math.degrees(math.acos((B * B + C * C - A * A) / (2.0 * B * C)))

    if(abs(round(degree) - 360) <= 3):
        return True
    return False

Answer 2

Sounds like a good use case for a modified convex hull algorithm.

1. Start out with all points inside of the "area" (since no hull is yet created).
2. Then, as you progress through your chosen algorithm (e.g. Graham scan is O(nlog(n)) performance), if the point is chosen as part of the convex hull, it is no longer inside of the "area" -- (i.e. a point that comprises the convex hull is not is not part of the final answer).
3. Repeat until you have created the convex hull. The leftover points which are not part of the hull is therefore inside the area, which is the answer you are looking for.