How to determine if a point is inside a rectangle?

Question

Possible duplicate:
Search if a point is inside the rectangle or not

There is an interview question: "How to determine if a point is inside a rectangle"

Note that the rectangle can also be rotated. Therefore, the simple solution of the control point inside the rectangle is not justified here ...

Share your thoughts on this issue ..

I found the link on the Internet and tried to understand it, but I couldn’t .... Please, if any body here can give a complete solution with a bit of computer graphics logic, because I forgot all the basics ..., How to determine if point inside the rectangle.

Answer 1

Select a point defined outside the rectangle. Then create a segment from this point to the point in question. Solve the linear equations for the intersections between this segment and the segments that make up the rectangle. If you get exactly one intersection, the point is inside the rectangle. Otherwise (0 or 2 intersections), outside.

This is trivial to extend to almost any polygon - an odd number of intersections means that the point is inside the polygon, and an even number means it outside.

Edit: this may not be immediately obvious, so I emphasize that the point we select outside the rectangle (polygon) is completely arbitrary. We can choose any point we want, as long as we are sure that it is outside the polygon. To make our calculations easy, we will usually choose (P _x , infinity) (where P _x is the x coordinate of the point P where we are testing) - that is, what we are creating is essentially a vertical ray. This makes testing easier because we only need to test one point to find the intersection. It also simplifies the solution of linear equations to such an extent that it is hardly recognized as a solution of linear equations. We just need to calculate the Y coordinate for the row on P _x and see if it will be larger than P _y . Thus, the solution of the linear equation splits into:

• check if this X value is within the range of X values ​​for the segment
• if so by plugging the value of X into the line equation
• check whether the obtained Y value is greater than P _y

If they pass, we have an intersection. Also note that tests can be run in parallel (convenient if we do this on parallel hardware such as a GPU).

Answer 2

A simple solution that works in sizes N for convex polyhedra, of which a two-dimensional rectangle is a special case:

• Imagine a polyhedron as the intersection of half-spaces, each of which is determined by a unit normal vector and the distance of the surface hyperplane from the origin along the normal.
• For each of these half-spaces, we take the point product of the considered point with the defining normal vector. A point is in half-space if and only if the point product is less than [or equal to] the determining distance.
• A point is inside a polyhedron if and only if it is in each of the half-spaces.

For a rectangle defined as a sequence of edges counterclockwise, step 1 is equal to turning the edges 90 degrees clockwise to get the normals, and then cross the normal line with the line containing the edge to find the distance to the origin.

Assuming step 1 is complete, testing the point takes no more than 8 multiplications, 4 additions, and 4 comparisons.

If you want, you can optimize the process a bit, since you have rectangles (and therefore opposite sides have opposite normals). Now you look only at 2 normals, and not at 4, and at a series of point product values ​​that indicate points that are between opposite sides. So now you are reducing to 4 multiplications, 2 additions and 4 comparisons.

You may also be lucky if the first test you do shows that the point is outside the rectangle, in which case it is only 2 multiplications, 1 addition and 1-2 comparisons.

Answer 3

This is far from the best solution ... But if you have points in sequential order, name them a , b , c and d using the x and ay fields, you can use the transverse product of vectors between your point p and each of the consecutive pairs.

If you always get the same sign for the result (i.e. all positive or all negative), then you are inside the rectangle; otherwise you are outside.

Answer 4

Define a new coordinate system with two rectangular sides as unit vectors and transform the coordinate of the point into a new coordinate system. If both coordinates are between 0 and 1, inside.

In the equations (if A, B, C, D are the angles of the rectangle, P is the point, _x and _y are the components of x and y):

 P_x = A_x + x * (B_x - A_x) + y * (D_x - A_x) P_y = A_y + x * (B_y - A_y) + y * (D_y - A_y) 

Solve for x and y and check if they are between 0 and 1

Written as a linear system of equations (A, B, C, D, P are vectors of length 2):

 [ | ] [x] [ ] [BA | DA] * [ ] = [PA] [ | ] [y] [ ] 

The solution is easy, as it has only two dimensions, and you can be sure that you are not the only ones.

Answer 5

Since the rectangle can be rotated, you may need an algorithm that is used to determine if a point is inside a convex polygon ..

You can also calculate the angle of rotation of the rectangle, and then convert the rectangle and point to axially align the rectangle. Then check if the converted point is inside the rectangle aligned on the axis.

Answer 6

You can rotate and move your frame of reference so that it matches the position and rotation of the rectangle. Now it's just a matter of simple comparisons between coordinates. This is a more mathematical way, therefore not the fastest (@Platinum Azure call)

Answer 7

Finding whether a point is in a limited area, such as a rectangle, is part of the classical clipping algorithms. See the wikipedia articles on Clipping and Trimming Strings to find out more about this.

Answer 8

Following the spirit of @Jerry Coffin: create segments from the corners of the rectangle to the point in question. Solve linear equations. Tilt tan(a) . Sum all seq arctangents diff if it is 2 * PI and each diff <PI point is inside the rectangle.

Edit It’s probably quite simple to check each successive difference <Pi ...