Finding whether a point lies inside a rectangle or not

Question

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

User · Answer

If you can t solve the problem for the rectangle try dividing the problem in to easier problems  Divide the rectangle into 2 triangles an check if the point is inside any of them like they explain in here  Essentially  you cycle through the edges on every two pairs of lines from a point  Then using cross product to check if the point is between the two lines using the cross product  If it s verified for all 3 points  then the point is inside the triangle  The good thing about this method is that it does not create any float-point errors which happens if you check for angles

User · Answer

bool pointInRectangle Point A  Point B  Point C  Point D  Point m         Point AB   vect2d A  B    float C1   -1    AB y A x   AB x A y   float  D1    AB y m x   AB x m y    C1      Point AD   vect2d A  D    float C2   -1    AD y A x   AD x A y   float D2    AD y m x   AD x m y    C2      Point BC   vect2d B  C    float C3   -1    BC y B x   BC x B y   float D3    BC y m x   BC x m y    C3      Point CD   vect2d C  D    float C4   -1    CD y C x   CD x C y   float D4    CD y m x   CD x m y    C4      return     0  gt   D1  amp  amp  0  gt   D4  amp  amp  0  lt   D2  amp  amp  0  gt   D3        Point vect2d Point p1  Point p2        Point temp      temp x    p2 x - p1 x       temp y   -1    p2 y - p1 y       return temp       I just implemented AnT s Answer using c    I used this code to check whether the pixel s coordination X Y   lies inside the shape or not

User · Answer

In continuation matts answer  we need to use  https   math stackexchange com questions 190111 how-to-check-if-a-point-is-inside-a-rectangle 190373 190373 solution to make it work   Below does not work   0  lt   dot AB AM   lt   dot AB AB   amp  amp  0  lt   dot BC BM   lt   dot BC BC   Below works   0  lt   dot AB AM   lt   dot AB AB   amp  amp  0  lt   dot AM AC   lt   dot AC AC   you check by pasting below in javascript console               Javascript solution for same              var screenWidth   320              var screenHeight   568              var appHeaderWidth   320              var AppHeaderHeight   65              var regionWidth   200              var regionHeight   200               this topLeftBoundary                     A   x  0  y  AppHeaderHeight                   B   x  regionWidth  y  AppHeaderHeight                   C   x  0  y  regionHeight   AppHeaderHeight                   D   x  regionWidth  y  regionHeight   AppHeaderHeight                             this topRightBoundary                     A   x  screenWidth  y  AppHeaderHeight                   B   x  screenWidth - regionWidth  y  AppHeaderHeight                   C   x  screenWidth  y  regionHeight   AppHeaderHeight                   D   x  screenWidth - regionWidth  y  regionHeight   AppHeaderHeight                             this bottomRightBoundary                     A   x  screenWidth  y  screenHeight                   B   x  screenWidth - regionWidth  y  screenHeight                   C   x  screenWidth  y  screenHeight - regionHeight                   D   x  screenWidth - regionWidth  y  screenHeight - regionHeight                             this bottomLeftBoundary                     A   x  0  y  screenHeight                   B   x  regionWidth  y  screenHeight                   C   x  0  y  screenHeight - regionHeight                   D   x  regionWidth  y  screenHeight - regionHeight                            console log this topLeftBoundary               console log this topRightBoundary               console log this bottomRightBoundary               console log this bottomLeftBoundary                checkIfTapFallsInBoundary   function  region  point                    console log  region     JSON stringify region                    console log  point    JSON stringify point                     var r   region                  var m   point                   function vector p1  p2                        return                           x   p2 x - p1 x                           y   p2 y - p1 y                                                            function dot u  v                        console log  DOT      u x   v x   u y   v y                        return u x   v x   u y   v y                                     function pointInRectangle m  r                        var AB   vector r A  r B                       var AM   vector r A  m                       var AC   vector r A  r C                       var BC   vector r B  r C                       var BM   vector r B  m                        console log  AB     JSON stringify AB                        console log  AM     JSON stringify AM                        console log  AM     JSON stringify AC                        console log  BC     JSON stringify BC                        console log  BM     JSON stringify BM                         var dotABAM   dot AB  AM                       var dotABAB   dot AB  AB                       var dotBCBM   dot BC  BM                       var dotBCBC   dot BC  BC                       var dotAMAC   dot AM  AC                       var dotACAC   dot AC  AC                        console log  ABAM     JSON stringify dotABAM                        console log  ABAB     JSON stringify dotABAB                        console log  BCBM     JSON stringify dotBCBM                        console log  BCBC     JSON stringify dotBCBC                        console log  AMAC     JSON stringify dotAMAC                        console log  ACAC    JSON stringify dotACAC                         var check     0  lt   dotABAM  amp  amp  dotABAM  lt   dotABAB   amp  amp   0  lt   dotBCBM  amp  amp  dotBCBM  lt   dotBCBC                        console log   first check    check                       var check     0  lt   dotABAM  amp  amp  dotABAM  lt   dotABAB   amp  amp   0  lt   dotAMAC  amp  amp  dotAMAC  lt   dotACAC                        console log  second check    check                       return check                                     return pointInRectangle m  r                            var point    x  136  y  342                checkIfTapFallsInBoundary topLeftBoundary   x  136  y  342                checkIfTapFallsInBoundary topRightBoundary   x  136  y  274                checkIfTapFallsInBoundary bottomRightBoundary   x  141  y  475                checkIfTapFallsInBoundary bottomRightBoundary   x  131  y  272                checkIfTapFallsInBoundary bottomLeftBoundary   x  131  y  272

User · Answer

I ve borrowed from Eric Bainville s answer   0  lt   dot AB AM   lt   dot AB AB   amp  amp  0  lt   dot BC BM   lt   dot BC BC    Which in javascript looks like this   function pointInRectangle m  r        var AB   vector r A  r B       var AM   vector r A  m       var BC   vector r B  r C       var BM   vector r B  m       var dotABAM   dot AB  AM       var dotABAB   dot AB  AB       var dotBCBM   dot BC  BM       var dotBCBC   dot BC  BC       return 0  lt   dotABAM  amp  amp  dotABAM  lt   dotABAB  amp  amp  0  lt   dotBCBM  amp  amp  dotBCBM  lt   dotBCBC     function vector p1  p2        return               x   p2 x - p1 x               y   p2 y - p1 y            function dot u  v        return u x   v x   u y   v y       eg   var r         A   x  50  y  0       B   x  0  y  20       C   x  10  y  50       D   x  60  y  30      var m    x  40  y  20     then   pointInRectangle m  r      returns true    Here s a codepen to draw the output as a visual test    http   codepen io mattburns pen jrrprN

User · Answer

Pseudo code   Corners in ax ay bx by dx dy   Point in x  y  bax   bx - ax bay   by - ay dax   dx - ax day   dy - ay  if   x - ax    bax    y - ay    bay  lt  0 0  return false if   x - bx    bax    y - by    bay  gt  0 0  return false if   x - ax    dax    y - ay    day  lt  0 0  return false if   x - dx    dax    y - dy    day  gt  0 0  return false  return true

User · Answer

If a point is inside a rectangle  On a plane  For mathematician or geodesy  GPS  coordinates   Let the rectangle be set by vertices A  B  C  D  The point is P  Coordinates are rectangular  x  y  Lets prolong the sides of the rectangle  So we have 4 straight lines lAB  lBC  lCD  lDA  or  for shortness  l1  l2  l3  l4  Make an equation for every li  The equation sort of   fi P  0     P is a point  For points  belonging to li  the equation is true     We need the functions on the left sides of the equations  They are f1  f2  f3  f4  Notice  that for every point from one side of li the function fi is greater than 0  for points from the other side fi is lesser than 0  So  if we are checking for P being in rectangle  we only need for the p to be on correct sides of all four lines  So  we have to check four functions for their signs   But what side of the line is the correct one  to which the rectangle belongs  It is the side  where lie the vertices of rectangle that don t belong to the line  For checking we can choose anyone of two not belonging vertices  So  we have to check this   fAB P  fAB C     0  fBC P  fBC D     0  fCD P  fCD A     0  fDA P  fDA B     0   The unequations are not strict  for if a point is on the border  it belongs to the rectangle  too  If you don t need points on the border  you can change inequations for strict ones  But while you work in floating point operations  the choice is irrelevant     For a point  that is in the rectangle  all four inequations are true  Notice  that it works also for every convex polygon  only the number of lines equations will differ  The only thing left is to get an equation for a line going through two points  It is a well-known linear equation  Let s write it for a line AB and point P   fAB P   nbsp  nbsp   nbsp  nbsp   xA-xB   yP-yB  -  yA-yB   xP-xB    The check could be simplified - let s go along the rectangle clockwise - A  B  C  D  A  Then all correct sides will be to the right of the lines  So  we needn t compare with the side where another vertice is  And we need check a set of shorter inequations   fAB P     0  fBC P     0  fCD P     0  fDA P     0  But this is correct for the normal  mathematician  from the school mathematics  set of coordinates  where X is to the right and Y to the top  And for the geodesy coordinates  as are used in GPS  where X is to the top  and Y is to the right  we have to turn the inequations   fAB P   lt   0  fBC P   lt   0  fCD P   lt   0  fDA P   lt   0  If you are not sure with the directions of axes  be careful with this simplified check - check for one point with the known placement  if you have chosen the correct inequations

User · Answer

The easiest way I thought of was to just project the point onto the axis of the rectangle  Let me explain   If you can get the vector from the center of the rectangle to the top or bottom edge and the left or right edge  And you also have a vector from the center of the rectangle to your point  you can project that point onto your width and height vectors   P   point vector  H   height vector  W   width vector  Get Unit vector W   H  by dividing the vectors by their magnitude  proj P H   P -  P H  H  proj P W   P -  P W  W   Unless im mistaken  which I don t think I am     Correct me if I m wrong  but if the magnitude of the projection of your point on the height vector is less then the magnitude of the height vector  which is half of the height of the rectangle  and the magnitude of the projection of your point on the width vector is  then you have a point inside of your rectangle   If you have a universal coordinate system  you might have to figure out the height width point vectors using vector subtraction  Vector projections are amazing  remember that

User · Answer

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  gt  0  the point is on the left-hand side  If D  lt  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  gt  0  the point is on the left-hand side  If D  lt  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

User · Answer

Assuming the rectangle is represented by three points A B C  with AB and BC perpendicular  you only need to check the projections of the query point M on AB and BC   0  lt   dot AB AM   lt   dot AB AB   amp  amp  0  lt   dot BC BM   lt   dot BC BC    AB is vector AB  with coordinates  Bx-Ax By-Ay   and dot U V  is the dot product of vectors U and V  Ux Vx Uy Vy   Update  Let s take an example to illustrate this  A 5 0  B 0 2  C 1 5  and D 6 3   From the point coordinates  we get AB  -5 2   BC  1 3   dot AB AB  29  dot BC BC  10   For query point M 4 2   we have AM  -1 2   BM  4 0   dot AB AM  9  dot BC BM  4  M is inside the rectangle   For query point P 6 1   we have AP  1 1   BP  6 -1   dot AB AP  -3  dot BC BP  3  P is not inside the rectangle  because its projection on side AB is not inside segment AB

User · Answer

I realise this is an old thread  but for anyone who s interested in looking at this from a purely mathematical perspective  there s an excellent thread on the maths stack exchange  here   https   math stackexchange com questions 190111 how-to-check-if-a-point-is-inside-a-rectangle  Edit  Inspired by this thread  I ve put together a simple vector method for quickly determining where your point lies   Suppose you have a rectangle with points at p1    x1  y1   p2    x2  y2   p3    x3  y3  and p4    x4  y4   going clockwise  If a point p    x  y  lies inside the rectangle  then the dot product  p - p1   p2 - p1  will lie between 0 and  p2 - p1  2  and  p - p1   p4 - p1  will lie between 0 and  p4 - p1  2  This is equivalent to taking the projection of the vector p - p1 along the length and width of the rectangle  with p1 as the origin   This may make more sense if I show an equivalent code   p21    x2 - x1  y2 - y1  p41    x4 - x1  y4 - y1   p21magnitude squared   p21 0  2   p21 1  2 p41magnitude squared   p41 0  2   p41 1  2  for x  y in list of points to test       p    x - x1  y - y1       if 0  lt   p 0    p21 0    p 1    p21 1   lt   p21magnitude squared          if 0  lt   p 0    p41 0    p 1    p41 1    lt   p41magnitude squared              return  Inside          else              return  Outside      else          return  Outside    And that s it  It will also work for parallelograms

[algorithm] Finding whether a point lies inside a rectangle or not

Examples related to algorithm

Examples related to geometry