0
$\begingroup$

I have a rectangle defined by four 2D points. Each point consists of (x, y).

I then have another point (x, y) and I would like to determine if that point is:

1) Located on one of four lines connecting the rectangle points 2) Located inside of the rectangle 

Could anyone provide an example of how I might go about doing this? Any advice or help would be appreciated!

2 Answers 2

0

The approach I would take is the following: I'd find the 4 lines connecting the 4 different rectangle points like: $y-y_1=\frac{y_2-y_1}{x_2-x_1}(x-x_1)$,where 1 and 2 are the two corresponding points every time. When you have the 4 line equations, you can check whether or not the point $(x_p,y_p)$ satisfies one of those equations, in other words if $y_p -y_1=\frac{y_2-y_1}{x_2-x_1}(x_p-x_1)$ is true.

For the 2nd question I refer you to the following: http://mathforum.org/library/drmath/view/54386.html

  • 0
    That link was very helpful for what I'm trying to do. Thanks a lot!2012-03-24
0

Best way to do this is to use the signed magnitude of cross product of vectors, i.e. $(x_1,y_1)\times(x_2,y_2) = x_1 y_2 - x_2 y_1 .$

This formula equals to $0$ if and only if $(x_1, y_1)$, $(x_2,y_2)$ and $(0,0)$ are on the same line. Points $p$, $q$, $r$ are on the same line if and only if $p-r$, $q-r$ and $r-r$ are on the same line.

To check if point is inside a rectangle you can use the cross product too: its sign depends on whether point is on the left or on the right of the line. The point $(x_2, y_2)$ is on the left of line from $(0,0)$ to $(x_1,y_1)$ if and only if $ x_1 y_2 - x_2 y_1 > 0.$

So to check if the point is in the rectangle just check if it's on the same side of every segment, i.e. if $a,b,c,d$ are consecutive vertices of the shape and $x$ is the point in question, then \begin{align*} (b-a)\times(x-a) \\ (c-b)\times(x-b) \\ (d-c)\times(x-c) \\ (a-d)\times(x-d) \\ \end{align*}

will have the same sign if and only if $x$ is inside the rectangle. If $a, b, c, d$ are sorted counterclockwise (clockwise) then all have to be positive (negative).

Hope that helps ;-)

  • 0
    @Paul $p-r = (1.4, 0.1)$, $q-r = (1.6,2.1)$, $r-r = (0,0)$, $ 1.4 \cdot 2.1 - 0.1 \cdot 1.6 = 2.94-0.16 = 2.78.$ This means that $q$ is on the left of line passing through $p$ and $r$ (oriented from $r$), which indeed is the case.2012-03-25