Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

2 Answers 2

up vote 0 down vote accepted

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

share|improve this answer
    
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 ;-)

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.