8

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?

Improve this question
2
  • 1
    You could tesselate the semi-random shapes into triangles, which would make it so much easier to decide. Commented May 5, 2017 at 20:14
  • 2
    You can just delegate to existing implementations, but if you want to do it yourself, there are plenty of resources regarding known algorithms. Commented May 5, 2017 at 20:15

3 Answers 3

Reset to default
13

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: enter image description here

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
Improve this answer
Sign up to request clarification or add additional context in comments.

11 Comments

Very great idea! So if inside, the sum of triangles is 360, and if it is not, the sum is not 360. One thing I don't understand is abs(round(degree) - 360) <= 3. why 3?
This answer is wrong. It only applies to convex polygons; for concave polygons, the angles could double back on themselves.
@user2357112 hmm, can you make it clear?
@SmAc yes, 3 is a threshold about how accurate you want to be. If you are very confident about my idea, you can try to make it 0.1 instead of 3. The smaller the more accurate.
@user2357112 I don't see how it is wrong, if I understand you correcly. By double back you mean the angle move backward? I already take that into consideration, different backward angle has a negative value. By the way, I really want to see the problem.
|
1

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.
Improve this answer

2 Comments

Doesn't work, because a point might lie inside the convex hull and yet outside the polygon.
@user2357112 ahh that is an interesting corner case I failed to account for =)
0

Here is a pseudo code:

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
Improve this answer

2 Comments

can you explain a bit?
Sorry I got it from otherwhere, I'm using it in a Tangram app that I did for iOS, but I'm not sure if it works only on convex polygons. I only know that is a DP algorithm which means that it skips many steps.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.