Algorithm to determine if a point is inside an area

Question

I recently worked on a project that has an algorithm to determine if a point is inside an area.

The area is as follows:

{"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]]}

Easy if the area is a rectangle. However, the area is irregular. One of my ideas is to check if a point is in the inside of each area. However, performance is not very good. Any idea?

Answer 1

First of all, a very interesting question !! Although this may be a duplicate question, but I'm still going to post a different working answer, different from this post, to encourage this new guy.

, , , . , 360. , 360. . , . , .

[[-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]] ( google). , .

:

python, .

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

:

var point = [x,y] // Point to evaluate

int i, j, c = 0
int size = border.count
for (i = 0, j = size-1; i < size; j = i++) {
    var ii = border[i]
    var jj = border[j]
    if ( ((ii.[1] > point.[1]) != (jj.[1] > point.[1])) &&
        (point.[0] < (jj.[0]-ii.[0]) * (point.[1]-ii.[1]) / (jj.[1]-ii.[1]) + ii.[0])) {
        c = !c
    }
}
return c

Answer 3

.

• "area" ( ).
• , (, Graham O(nlog(n))), , "area" - (.. , , ).
• , . , , , , , .