Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
298 views
in Technique[技术] by (71.8m points)

algorithm - Finding whether a point lies inside a rectangle or not

I want to find whether a point lies inside a rectangle or not. The rectangle can be oriented in any way, and need not be axis aligned.

One method I could think of was to rotate the rectangle and point coordinates to make the rectangle axis aligned and then by simply testing the coordinates of point whether they lies within that of rectangle's or not.

The above method requires rotation and hence floating point operations. Is there any other efficient way to do this?

Question&Answers:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

How is the rectangle represented? Three points? Four points? Point, sides and angle? Two points and a side? Something else? Without knowing that, any attempts to answer your question will have only purely academic value.

In any case, for any convex polygon (including rectangle) the test is very simple: check each edge of the polygon, assuming each edge is oriented in counterclockwise direction, and test whether the point lies to the left of the edge (in the left-hand half-plane). If all edges pass the test - the point is inside. If at least one fails - the point is outside.

In order to test whether the point (xp, yp) lies on the left-hand side of the edge (x1, y1) - (x2, y2), you just need to calculate

D = (x2 - x1) * (yp - y1) - (xp - x1) * (y2 - y1)

If D > 0, the point is on the left-hand side. If D < 0, the point is on the right-hand side. If D = 0, the point is on the line.


The previous version of this answer described a seemingly different version of left-hand side test (see below). But it can be easily shown that it calculates the same value.

... In order to test whether the point (xp, yp) lies on the left-hand side of the edge (x1, y1) - (x2, y2), you need to build the line equation for the line containing the edge. The equation is as follows

A * x + B * y + C = 0

where

A = -(y2 - y1)
B = x2 - x1
C = -(A * x1 + B * y1)

Now all you need to do is to calculate

D = A * xp + B * yp + C

If D > 0, the point is on the left-hand side. If D < 0, the point is on the right-hand side. If D = 0, the point is on the line.

However, this test, again, works for any convex polygon, meaning that it might be too generic for a rectangle. A rectangle might allow a simpler test... For example, in a rectangle (or in any other parallelogram) the values of A and B have the same magnitude but different signs for opposing (i.e. parallel) edges, which can be exploited to simplify the test.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...