polygon - 旋转二维矩形内的点（不使用平移、三角函数或点积）

Question

我想知道以下检查点是否在矩形内的算法是否有效。我用自己的直觉开发了它（没有强大的三角/数学基础来支持它），所以我很想听听在这件事上有更多经验的人的意见。

语境：

矩形由 4 个点定义。它可以旋转。
坐标总是正的。
根据定义，如果点与矩形相交，则认为该点位于矩形内部。

假设：

使用点和矩形顶点之间的距离（下图）。
最大可能的总距离是当点位于一个顶点时（第二张图）。
如果该点刚好在矩形之外，则距离会更大（第三张图）。

算法（Java）：

static boolean pointInsideRectangle(Point[] rect, Point point) {
    double maxDistance = distance(rect[0], rect[1]);
    maxDistance += distance(rect[0], rect[2]);
    maxDistance += distance(rect[0], rect[3]);

    double distance = 0;
    for (Point rectPoint : rect) {          
        distance += distance(rectPoint, point);
        if (distance > maxDistance) return false;
    }
    return true;
}

问题：这是正确的吗？

score 3 · Accepted Answer

简短的回答：NO :P （不要对此感到失望）

长答案：与您提到的四个圆圈的区域相交（相对顶点之间的最大距离）不会产生矩形。半径等于矩形对角线的四个圆的公共面积，每个角的中心由于我在几何上有点生疏，我不能给出完整的数学解释（我的时间限制），但给你一些带有你要求的约束的过程伪代码（没有花哨的公式），对维基百科的任何矩形都有效或者几何书可以填补空白。

找到 N、E、S、W 顶点（最上面、最右边、最低和最左边的顶点）这对于任何矩形都很容易，但轴对齐的人会产生奇怪的顶点分配（参见带有示例的图像）
找到 NE、SE、SW 和 NW 边界，这是维基百科或其他链接中的线方程，同样应该很容易，但是应该仔细分析轴对齐的边界，因为它们会产生另一种类型的 ecuation/restriction。
检查您的点是否在边界的“右侧”，将不等式视为数学术语，只有 矩形内的一个点满足您在所附图像中看到的四个限制。
如果我忽略了一些可以完成此任务的 java.geom 命令，我深表歉意

我希望这对你的努力有所帮助

score 0 · Accepted Answer

你可以试试这个。让我们将点命名为 A。在 A 和矩形的每个点之间画一条线。之后你会得到 4 个不同的三角形。计算三角形的面积（使用 Heron 公式）并将其与矩形的面积。如果面积相同，则您的点在矩形内。干杯

polygon - 旋转二维矩形内的点（不使用平移、三角函数或点积）

2 回答 2

Related

Reference