Given 4 points to a rectangle (that has some kind of rotation), determine if a single point is withi-CodePudding

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.

CodePudding user response：

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).

CodePudding user response：

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.

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