2

I have a set of points that I can plot on a graph that if connected would form shape (bounded box might be the correct term?). How can I find if another point falls inside this box?

Here points for an example box:

var box = [[181,7500],[181,11279],[185,12500], [196.4,12500],[196.4,7500]];
var point_inside_box = [188,10000];
var point_outside_box = [182,12000];

It is easy to see if these points fall outside of the box if you visualize it as below:

bounding box

Is there a way to do this in javascript with a bit of math?

bernieberg
  • 55
  • 6
  • 1
    The word "box" in the title is a little deceiving, at least to me box implies rectangle. Can we assume the shapes are always convex? I believe that affects the logic – Matt Dodge Jun 14 '12 at 16:13
  • 1
    This comprehensive stackoverflow answer should help you: http://stackoverflow.com/questions/217578/point-in-polygon-aka-hit-test – Robin Jun 14 '12 at 16:15
  • @mattedgod Yes, I think I have my terms mixed up. The shapes will be some sort of polygon, not necessarily a box. – bernieberg Jun 14 '12 at 16:38
  • @Robin That link is very helpful, thanks – bernieberg Jun 14 '12 at 16:41

2 Answers2

2

One method of doing this is to pick a direction and figure out how many sides are crossed if you were to theoretically keep moving in that direction forever. If it's an odd number, the point is inside the box. If it's an even number, the point is outside the box.

Reference: http://local.wasp.uwa.edu.au/~pbourke/geometry/insidepoly/

Falterfire
  • 156
  • 4
  • 9
1

One of the ways is to check whether all cross products of vectors (PA_i, PA_{i+1}) are of the same sign. If so, the point is inside, otherwise outside. (P is the point to be checked, the polygon is A_1A_2...A_n.)

In the 2-dimensional case, the cross product of the vectors (a, b), (c, d) is just the number ad - bc.

This calculation is valid if your points A_i form a convex polygon.

Vlad
  • 35,022
  • 6
  • 77
  • 199