0

I am trying to think of an algorithm to find out if a point is within a rectangle. Finding a point in a standard rectangle without a rotation built onto the lines is a fairly easy task, however if the rectangle is on an angle, the algorithm becomes more complicated.

code writer 3000
  • 329
  • 5
  • 19
  • 1
    Is there a specific problem that is related to code? – Marco Oct 02 '21 at 21:09
  • @Marco finding whether or not your mouse cursor is within a rectangle. – code writer 3000 Oct 02 '21 at 21:10
  • 2
    This is just a point-in-polygon test. I don't think that knowing the polygon is a rotated rectangle actually helps you any. – jasonharper Oct 02 '21 at 21:13
  • Have you read this? https://en.wikipedia.org/wiki/Point_in_polygon Its the general case for a polygon. – Paul Johnson Oct 02 '21 at 21:14
  • @PaulJohnson The issue with both of those algorithms is the fact that I only have rectangle points, not lines. And also detecting ray intersections is its own algorithm. – code writer 3000 Oct 02 '21 at 21:36
  • You can reduce the task to the "easy case" by applying a counter-rotation to the rectangle and the test point. –  Oct 03 '21 at 12:53
  • @jasonharper: on the opposite, it is much simpler than the case of a general quadrilateral. –  Oct 03 '21 at 12:54

2 Answers2

0

I would suggest the following. Say you have points A (x1, y1), B (x2, y2), C (x3, y3), D (x4, y4) and P (xp, yp).

0 stage. Find min and max of xn and yn. If xp < min(xn) or xp > max(xn) or yp < min(yn) or yn > max(yn) then P is outside the rectangle else we need further calculations.

1 stage. Find four functions f(x) = ax + b that produce graphics (lines) which the sides of the rectangle belong to. For AB side a = (y2 - y1) / (x2 - x1) and b = y1 - a * x1.

2 stage. Find which of the sides is leftward/upward. Say AB is upward to CD*. Then find if the system of inequations is true: fAB(xp) <= yp <= fCD(xp) and fAD(xp) <= yp <= fBC(xp). The true will show that P is inside the rectangle.

*You can skip this stage by checking the truth of opposite inequation fAB(xp) >= yp >= fCD(xp) and fAD(xp) >= yp >= fBC(xp).

asd-tm
  • 3,381
  • 2
  • 24
  • 41
0

Let a side of the rectangle correspond to the green vector (Dx, Dy). Then the linear transformation (a similarity)

X' = Dx.X + Dy.Y
Y' = Dx.Y - Dy.X

will make the rectangle axis-aligned. If you apply the same transformation to the test point, the insideness relation is preserved and the resolution is immediate.

enter image description here

If you have several test points, you only need to transform the rectangle once.