Point in rectangle

What is the fastest way to find if a point is in a rectangle given in this form:

I have two points which are the centers of opposite sides of the rectangle, and a number which is the height of those sides. I hope this is clear.

The rectangle is (probably) not aligned with the axis. I am wondering if there may be a faster algorithm given this data then calculating the four corners, rotating, etc.

An idea I though of but am not sure how to implement (having trouble with the math) was to find the distance from the point to the line traced between the two centers, and if it is less then half the length of the side of the rectangle and also on the line then it is in the rectangle. I don't know how to explain this better.

Maybe the picture will help explain:

A, B, C are given, as well as the length of side A/B. Basically 开发者_高级运维I thought that if CD is less then half of side A and D is on AB, the point is in the rectangle. But how do I do this?

Another thought: Instead of finding D to see if it is on AB, check if angles ABC and BAC are acute, but I still don't know how to do this.

The following method is quite simple, but requires finding 1 vector length (you can cache it for multiple checks)

1. Calc vector AB = B - A

2. Calc AB length - it will be the width of the rectangle

3. If AB_length < TOLERANCE (tolerance is a small value, for example, TOLERANCE = 0.00000001) then the rectangle has zero width, therefore the point cannot lie in the rectangle

4. Normalize AB: AB_normalized = AB / AB_length

5. Calculate axis projections

   Calc AB projection:

   AB_proj = dot product(AB_normalized, C - A)

   Calc AB orthogonal projection (denoted "CD" in your picture):

   AB_orthogonal = (-AB.y, AB.x)

   AB_orthogonal_proj = dot product(AB_orthogonal, C - A)

6. If (0 <= AB_proj <= AB_length) and (ABS(AB_orthogonal_proj) <= AB_height / 2), then the point lies in the rectangle, doesn't lie otherwise

The dot product is your trusty friend for problems like this. That and a bit of Pythagoras should give you everything you need to answer two questions:

1. Is the projection of AC onto AB within AB?
2. Is |DC| < height/2?

Work in square distances rather than doing square roots, and don't bother calculating the angle.

Not entirely sure it's the fastest, but this would likely work:

Rather than placing D half in between the two centers, project C as D along the AB axis. Then check that a) D is between A and B and b) CD is less or equal to half of the rectangle's height.

Re your idea of using the angles... using Pythagorus and or Al Kashi's theorem might actually make sense:

http://en.wikipedia.org/wiki/Law_of_cosines

ABC acute and BAC acute would both be a prerequisite, and given them you place C2 on the rectangle, with the same alpha/beta (see wiki page). From there you also know gamma (pi/2, since on the rectangle) and beta/alpha (pi/2 - beta), which leads to wondering whether the [A,C] or [B,C] distance is lesser or equal to that of [A,C2] or [B,C2] respectively.

The idea with the acute triangle ABC does not work. E.g. it the point C is directly besides the line AB the angle at C will become almost 180°. On the other hand the angle at B might be very small if the rectangle's height is fairly small but C does then lie outside the rectangle.

Nevertheless your other approach is one basic way to implements this.

The point D is somewhere on the line through A and B, thus

D = A + t * (B-A)

(captial letters stand for vectors in space, small letters for numbers). At the same time the connection from D to C is perpendicular to the connection A to B and thus

(C-D) . (B-A) == 0

i.e. the dot product of the two difference vectors is zero. Putting both together yields

(C-A-t*(B-A)) . (B-A) = (C-A) . (B-A) - t * (B-A) . (B-A) == 0

or when solved for t:

t = (C-A).(B-A) / (B-A).(B-A)

(or in other words the relative length of the projection of the vector AC onto the line AB).

The point D is within the rectangle if 0 <= t <= 1, and thus this is your first condition.

Afterwards you can calulate the distance of C to D (just insert t into the very first eqn to get D) and compare this to h/2, i.e. the last condition then is

(C-D).(C-D) <= (h/2)^2

The square is the intersection of 4 half-spaces. Each half-space is derived from one side of the rectangle using the two-point line formula. Depending on the particulars of your problem, perhaps you can check side-by-side, possibly trivially rejecting at each step.

Is this faster than projection? I guess that depends on the probability that you'll trivially reject after your first step!