algorithm - 如何检查一个点是否在 3 个点的外接圆内？

Question

有什么简单的解决方法吗？或者有人有实现的例子吗？

谢谢，乔纳斯

Answer 1

让我们打电话

• a、b、c 我们的三点，
• C (a, b, c)的外接圆
• 还有另一点。

确定 d 是否在 C 中的快速方法是计算此行列式:

      | ax-dx, ay-dy, (ax-dx)² + (ay-dy)² |
det = | bx-dx, by-dy, (bx-dx)² + (by-dy)² |
      | cx-dx, cy-dy, (cx-dx)² + (cy-dy)² |

如果a、b、c逆时针排列则:

• 如果det等于0则d在C上
• 如果 det > 0 则 d 在 C 内
• 如果 det < 0 则 d 在 C 之外

这里有一个 javascript 函数可以做到这一点:

function inCircle (ax, ay, bx, by, cx, cy, dx, dy) {
    let ax_ = ax-dx;
    let ay_ = ay-dy;
    let bx_ = bx-dx;
    let by_ = by-dy;
    let cx_ = cx-dx;
    let cy_ = cy-dy;
    return (
        (ax_*ax_ + ay_*ay_) * (bx_*cy_-cx_*by_) -
        (bx_*bx_ + by_*by_) * (ax_*cy_-cx_*ay_) +
        (cx_*cx_ + cy_*cy_) * (ax_*by_-bx_*ay_)
    ) > 0;
}

您可能还需要检查您的点是否按逆时针顺序排列:

function ccw (ax, ay, bx, by, cx, cy) {
    return (bx - ax)*(cy - ay)-(cx - ax)*(by - ay) > 0;
}

我没有将 ccw 检查放在 inCircle 函数中，因为你不应该每次都检查它。

此过程不进行任何除法或平方根运算。

您可以在此处查看代码:https://titouant.github.io/testTriangle/

那里的来源:https://github.com/TitouanT/testTriangle