是正六边形内部的一个点

Question

我正在寻求有关最佳继续方式的建议。我试图找出给定点 A:(a, b) 是否在以中心 O:(x, y) 和外接圆直径定义的正六边形内。

对于这样一个简单的情况，使用光线投射或缠绕数来确定这一点似乎有点矫枉过正，我目前正在考虑寻找线 OA 的角度（与水平方向）和“标准化”的选项（可能不是正确的词）将其放入 6 个等边三角形之一，然后看看这个新点是否位于该三角形内。

我感觉我错过了一些简单的东西，并且有一种简单的方法（或者如果我真的很幸运，可以使用 Java API）来简单而有效地完成此操作。

感谢您的帮助。

编辑：六边形的方向使得其中一侧与水平面平齐。

Answer 1

您可以对六边形的每条边使用方程式；使用它们，您可以找出给定点是否与六边形中心位于同一半平面内。

例如，右上角有等式：

-sqrt(3)x - y + sqrt(3)/2 = 0

您代入该点的坐标，然后代入中心的坐标。如果结果具有相同的符号，则该点位于左下半平面中（因此它可能位于六边形内部）。

然后，您可以使用其他边的方程重复。
请注意，此算法适用于任何凸多边形。

Answer 2

如果将问题简化为检查单个象限中的{x = 0, y = 0, d = 1}，则可以变得非常简单。

public boolean IsInsideHexagon(float x0, float y0, float d, float x, float y) {
    float dx = Math.abs(x - x0)/d;
    float dy = Math.abs(y - y0)/d;
    float a = 0.25 * Math.sqrt(3.0);
    return (dy <= a) && (a*dx + 0.25*dy <= 0.5*a);
}

• dy <= a 检查该点是否位于水平边缘下方。
• a*dx + 0.25*dy <= 0.5*a 检查该点是否位于倾斜右边缘的左侧。

对于 {x0 = 0, y0 = 0, d = 1}，角点将为 (±0.25, ±0.43) 和 (±0.5, 0.0 ）。

Answer 3

这就是我一直在使用的：

public bool InsideHexagon(float x, float y)
{
    // Check length (squared) against inner and outer radius
    float l2 = x * x + y * y;
    if (l2 > 1.0f) return false;
    if (l2 < 0.75f) return true; // (sqrt(3)/2)^2 = 3/4

    // Check against borders
    float px = x * 1.15470053838f; // 2/sqrt(3)
    if (px > 1.0f || px < -1.0f) return false;

    float py = 0.5f * px + y;
    if (py > 1.0f || py < -1.0f) return false;

    if (px - py > 1.0f || px - py < -1.0f) return false;

    return true;
}

px 和 py 是 x 和 y 投影到坐标上的坐标系统更容易检查边界。

Answer 4

看起来你知道一般的解决方案：“使用它似乎有点矫枉过正……”。所以这是我的想法：

计算从点到中心的距离，我们称之为l。

然后您可以将其与内半径 (r) 和外接半径 (R) 进行比较。如果 l < r 则点位于六边形内部，如果 l > R 然后在外面。如果 r l < R 那么你必须分别检查每一边，但由于 R - r 非常小（十六进制边长的 13%），所以你可能必须进行复杂的计算很小。

公式可以在这里找到：http://mathworld.wolfram.com/Hexagon.html

Answer 5

我首先检查该点是否位于内切圆内部（您可以轻松计算内切圆半径）或外接圆外部（您已经有了）。

前者表示点已入，后者表示点已出。

从统计上看，大多数输入点应该允许您根据上述简单测试来决定。

对于最坏的情况（点位于内切圆和外接圆之间），我认为您可以找到距离该点最近的两个顶点，然后查看该点位于线段 V1V2 的哪一侧（内部或外部，如相对于 O 中心）。
特殊情况：点等于其中一个顶点 =>如果

我有一个更聪明的想法（或者如果我开始真正学习三角学），我会编辑答案让你知道:)

Answer 6

从点 P 中减去六边形中心的位置即可得到向量 V。然后，计算 V 与以下向量的点积，这些向量对应于三对相对的六边形边：

[0,1] ; the edges that are flat with the horizontal
[cos(30),sin(30)] ; the upper-right and lower-left edges
[cos(-30),sin(-30)] ; the lower-right and upper-left edges

如果任何点积为其大小大于从六边形中心到其边缘之一的距离，则该点不在六边形内部。

作为参考，向量 [a,b] 和 [c,d] 的点积为 a*c+b*d。

上面的角度“30”的单位是度；）

Answer 7

您想要的是找出一个点是否位于凸多边形内部的代码，六边形是其中的一个特殊情况。

这是一个很好的答案：
https://stackoverflow.com/a/34689268/516188

我确实修改了该函数以供我使用，我找到了我的版本更清晰。这是打字稿（你只要眯着眼睛看，它就是 javascript）：

function vectorX(v: Vector): number {
    return v[1].x - v[0].x;
}

function vectorY(v: Vector): number {
    return v[1].y - v[0].y;
}

function crossProduct(v1: Vector, v2: Vector): number {
    return vectorX(v1)*vectorY(v2) - vectorY(v1)*vectorX(v2);
}

function isInConvexPolygon(testPoint: Point, polygon: Polygon): boolean {
    // https://stackoverflow.com/a/34689268/516188
    if (polygon.length < 3) {
        throw "Only supporting polygons of length at least 3";
    }
    // going through all the edges around the polygon. compute the
    // vector cross-product http://allenchou.net/2013/07/cross-product-of-2d-vectors/
    // to find out for each edge on which side of the edge is the point.
    // if the point is on the same side for all the edges, it's inside
    let initCrossIsPositive = undefined;
    for (var i=0;i<polygon.length;i++) {
        if (polygon[i].x === testPoint.x &&
            polygon[i].y === testPoint.y) {
            // testPoint is an edge of the polygon
            return true;
        }
        const curPointOnEdge = polygon[i];
        const nextPointOnEdge = polygon[(i+1)%polygon.length];
        const vector1 = <[Point,Point]>[curPointOnEdge, nextPointOnEdge];
        const vector2 = <[Point,Point]>[curPointOnEdge, testPoint];
        const cross = crossProduct(vector1, vector2);
        if (initCrossIsPositive === undefined) {
            initCrossIsPositive = cross > 0;
        } else {
            if (initCrossIsPositive !== (cross > 0)) {
                return false;
            }
        }
    }
    // all the cross-products have the same sign: we're inside
    return true;
}

Answer 8

通过将晶格表示为与平面 x+y+z=0 相交的立方体晶格，可以很好地推广使用齐次坐标的六角晶格，请参阅https://www.redblobgames.com/grids/hexagons/#coordinates

Answer 9

好吧，现在是 2024 年了，这个问题仍然严重缺乏简单而完整的代码和正确的解释。这是 TypeScript，但在任何语言中都是一样的。

function isPointInsideHexagon(px: number, py: number, cx: number, cy: number, radius: number) {
    let sqrt3 = Math.sqrt(3);

    let dx = (px - cx) / radius;
    let dy = (py - cy) / radius;

    return dy > -sqrt3 / 2
        && dy < sqrt3 / 2
        && sqrt3 * dx + sqrt3 > dy
        && sqrt3 * dx - sqrt3 < dy
        && -sqrt3 * dx + sqrt3 > dy
        && -sqrt3 * dx - sqrt3 < dy
}

• (px, py) 是要检查的点的坐标
• (cx, cy) 是六边形中心的坐标
• radius 是从中心到六边形任意顶点的距离

解释

这里我们假设 Y 轴向上：点 (1,1) 位于点 (0,0) 的右上角。但是，由于它是正六边形，因此无论轴方向如何，代码都可以工作。

我们基本上要检查六边形的每一侧，要检查的点和六边形的中心是否在同一侧。

首先，为了方便起见，我们转换点坐标：

let dx = (px - cx) / radius;
let dy = (py - cy) / radius;

从现在开始，(dx, dy) 是要检查的点，(0,0) 是六边形的中心，六边形的半径为1。这使得后续方程更简单。

顶部和底部

这是最容易检查的，因为它们是水平线。顶边的 Y 坐标为 sqrt(3) / 2，底边的 Y 坐标与之相反，为 -sqrt(3) / 2。

所以我们检查 dy < sqrt3 / 2 和 dy > -sqrt3 / 2 表示该点位于这两条线之间。

对角边

有 4 个对角边，其方程为（对于中心 (0,0) 和半径 1 的六边形）：

• 左上角：y = sqrt(3) * x + sqrt(3)
• 右上角：y = -sqrt(3) * x + sqrt(3)
• 右下角：y = sqrt(3) * x - sqrt(3)
• 左下角：y = -sqrt(3) * x - sqrt(3)

了解两个点是否在同一个点上一条线的一侧，我们将它们的坐标代入线方程中，然后检查方程的哪一侧大于另一侧。如果两个点的同侧较大，则意味着它们在同一侧。

让我们以左上角为例。我们想要检查点 (0.5, 0.5) 是否与中心在同一侧。所以我们插入坐标：

• 对于要检查的点 (0.5, 0.5)：
  • 左侧：y = 0.5
  • 右侧：-sqrt(3) * x + sqrt(3) = -sqrt(3) * 0.5 + sqrt(3) ≈ 0.866
  • ->右侧更大
• 对于六边形的中心 (0, 0)：
  • 左侧：y = 0
  • 右侧：-sqrt(3) * x + sqrt(3) = -sqrt(3) * 0 + sqrt(3) ≈ 1.732
  • ->右侧更大

在这两种情况下，右侧都大于左侧，因此我们可以得出结论，点 (0, 0) 和 (0.5, 0.5) 都是在六边形右上角的同一侧。

如果我们尝试使用点 (1, 1)：

• 对于要检查的点 (1, 1)：
  • 左侧：y = 1
  • 右侧：-sqrt(3) * x + sqrt(3) = -sqrt(3) * 1 + sqrt(3) = 0
  • ->左侧更大
• 对于六边形的中心 (0, 0)：
  • 左侧：y = 0
  • 右侧：-sqrt(3) * x + sqrt(3) = -sqrt(3) * 0 + sqrt(3) ≈ 1.732
  • ->右侧更大

每个点都有不同的一侧较大，因此点 (1, 1) 与六边形的中心不在同一侧，因此它位于六边形之外。

总而言之，这可以归结为评估： dy > -sqrt(3) * dx + sqrt(3) === cy > -sqrt(3) * cx + sqrt(3)。

由于中心 (0, 0) 的值始终相同，因此我们可以简化方程，从而得到四个边：

• sqrt(3) * dx + sqrt(3 )> dy
• sqrt(3) * dx - sqrt(3) dy
• -sqrt(3) * dx + sqrt(3) > dy
• -sqrt(3) * dx - sqrt(3) < dy

就是这样。如果六个边中的每一个都通过检查，则该点位于六边形内部。不然就在外面了。