找出点是否位于矩形内

Question

如何找到一个点位于给定4个点的2D矩形内？

Answer 1

将点转换为与矩形对齐的坐标框,然后问题变得轴对齐且无关紧要.

如果矩形包含以下4点:

a  b
c  d

然后得到矩形的"x轴"和"y轴":

x = Normalize(d-c)
y = Normalize(a-c)

然后使用x和y作为列构造旋转矩阵:

r = [ x | y ]

如果你使用三维坐标,我们需要az轴:

z = CrossProduct(x, y)
r = [ x | y | z ]

从世界坐标到矩形轴对齐坐标的变换矩阵变为:

T = [ r^T | -r^T * c ]
    [ 0^T |     1    ]

在这里,我们选择了左下角c作为本地原点."r ^ T"被转置."0 ^ T"是用零填充的2-d或3-d行向量.1只是一个.请注意,这只是简单的矩形到世界变换的反转,即

T^-1 = [ r   | c ]
       [ 0^T | 1 ]

我们可以使用T将点转换为轴对齐坐标.记得用尾随1填充p,因为T是一个齐次矩阵.

tp = T * p;  // Don't forget to pad p with a trailing 1 before multiplying.

// Checks that p isn't below or to the left of the rectangle.
for ( int d = 0; d < num_dimensions; ++d ) {
  if ( tp[d] < 0.0 ) {
    return false;
  }
}

// Checks that p isn't to the right of the rectangle
double width = Length(d-c);
if ( tp[0] > width ) {
  return false;
}

// Checks that p isn't above the rectangle.
double height = Length(a-c);
if ( tp[1] > height ) {
  return false;
}

// p must be inside or on the rectangle.
return true

如果您正在使用3d坐标,请注意上面忽略了转换点tp的局部z值.即使p在矩形的平面之外,上面的行为就好像它被投影到矩形表面一样.如果要检查共面性,请事先执行以下操作:

if ( fabs(tp[2]) > some_small_positive_number ) {
   return false;  // point is out of the rectangle's plane.
}