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 need to check if a point is inside a rectangle (which can be not parallel to the axes) but not on its perimeter. In 2 dimensions.

I'm checking if the point is inside by finding the intersection between the rectangle and the line parallel to the y axis going through the point, and checking if the point is between the intersection points. Like in the drawing, where on the left it's inside, and on the right it isn't.

example

The rectangle is represented by 4 vertices: $x_1$ $x_2$ $x_3$ $x_4$, and the point is $p$

What I want to do is to create 4 vectors, which are the vectors from the point to each of the 4 vertices as such: $v_i=x_i-p$ And then to check if there are two vectors of adjacent numbers (1 & 2, 2 & 3, 3 & 4, and 4 & 1) whose dot product is -1: $v_1\cdot v_2$

I know that it'll give me a right answer, but can this give a false positive. Meaning, is there a case where a point is inside the rectangle and not on the perimeter, but the dot result of two adjacent vectors $v_i$ will be -1?

share|improve this question
    
This might help. –  Patrick Li Oct 3 '12 at 16:30
add comment

1 Answer

up vote 0 down vote accepted

If you've already found the two points of intersection, you need not find anything else. If the point is on the perimeter it will be equal to one of the two points.

A good way to find if $x$ is between $a$ and $b$ is to check $|a-b| < |a-x| + |b-x|$.

If this is a programming project and you are worrying about FPU imprecision, using > or < instead of = would produce no observable difference. Moreover, no other kind of computation would save you from those errors. If you really need to know if you are on a border, you should measure distances to lines. There are various ways to do this.

The dot product of two vectors pointing to opposite directions is not -1. It is -1 times their lengths. Even if you normalize the vectors and write $< -1+\epsilon$ to fix errors, the "border" would be wider in the middle.

share|improve this answer
add comment

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.