# determining if a point is located on a line

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!

-

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

-
That link was very helpful for what I'm trying to do. Thanks a lot! –  Paul Mar 24 '12 at 20:53

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 ;-)

-
For the first part, let's say I have the points p(0.2, 1.1), q(0.4, 3.1), r(-1.2, 1.0). To determine if they are on the same line: p - r = (0.2 * 1.0) - (1.1 * -1.2) = 1.52. q - r = (0.4 * 1.0) - (3.1 * -1.2) = 4.12. r - r = (0.2 * 1.0) - (1.0 * 0.2) = 0. I must not be understanding because I'm a little confused. Would it be possible for you to include an example of both techniques? Will they still work if a rectangle is oriented at an angle and is not aligned with the axes? –  Paul Mar 24 '12 at 20:26
@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. –  dtldarek Mar 25 '12 at 13:30