给定允许接触多边形的坐标，计算圆是否适合多边形 (triangle/pentagon) 的内部？
Calculate if circle fits inside of polygon (triangle/pentagon) given coordinates where touching the polygon is allowed?
给定一个圆心 (Xc,Yc) 和半径 r
以及在数组内部具有顶点的多边形，这样
顶点[] = { (Xv1, Yv1) , ... , (Xvn , Yvn) } 其中 n 是顶点数。
我想知道圆是否在多边形内部。我假设（并且可以安全地假设）多边形中没有孔。
我检查的唯一多边形将是三角形和五边形。
到目前为止我所做的是计算圆心是否在多边形内部。这个函数叫做 isInside().
如何检查圆是否完全在我正在检查的多边形内部？摸一下就可以了
更具体地说，我在计算圆和多边形的关系时遇到了问题，而这对于解决这个问题至关重要。我了解如何查找圆心是否在多边形内部，但如果完整的圆包含在多边形中则无法查找。
任何帮助:)
方法 1：简单，但不精确
您已经实现了一种检查点是否在多边形内的算法。那么，为什么不将圆近似为等边多边形呢？您只需检查圆的 16 或 64 或 256 个点。
方法 2：更复杂，但更精确
- 找到多边形每一边的法向量（您可以轻松计算）。
- 通过这个法向量求圆心到边的距离（直线相交也是一个简单的任务）。
- 如果距离小于圆的半径，则圆在多边形外。
- 否则，如果每条边到法线点的距离大于或等于圆的半径，则圆在里面。
以下假设您已经知道the center of the circle is inside the polygon。有几件事你想检查一下你的定义 touching the vertices is ok adds some cornercases。此解决方案也适用于凹多边形。
提前检查
要使圆完全在 多边形内部，我们需要所有边都在外部 圆。特别是这确保多边形不完全在圆内。
给定半径为 r 的圆，圆心为 c，边为 e0 , e1, ..., en 的多边形，因此一个必要条件是对于所有 i < n:
d(c, ei) >= r
其中 d 是第 euclidian distance.
如果上述任何一条边都不成立，那么要么多边形和圆之间存在交点，要么多边形本身完全在圆内。
圆是否与多边形相交
最后的检查是圆在里面的必要条件，虽然它是不充分的，因为有可能所有的边都在圆的外面，但是圆仍然漏出一个顶点。
让我们先记住一些我们需要的公式。
圆心为 (x0, y0 的圆心为 r 的方程):
(x - x0)2 + (y - y0)2 = r2
因此与直线 y = ax + b 的交点通过求解找到：
(x - x0)2 + (ax + b - y0)2 = r2
这只不过是一个可以重写为的二次方程：
(a2 + 1)x2 + (2ab - 2ay0 - 2x0)x + (x0 + (b - y0)2 - r2) = 0
你可以用每个顶点的 quadratic formula 来解决这个问题。那么你就有了三种可能。
1) 无解
这表示与该顶点不存在交集。使用高级语言，您可以捕获某种 MathError 异常来检测它。否则，您可以在数学上检查 discriminant 的符号，因为如果它是负数，就会发生这种情况。
(2ab - 2ay0 - 2x0)2 - 4 (a2 + 1) (x0 + (b - y0)2 - r2) < 0
2) 存在唯一解
如果方程只有一个解，即两个解相同，则圆可能会接触，但不会漏出边缘。你说这仍然被认为是在你的情况下多边形内。
从数学上讲，当判别式为零时会发生这种情况。
(2ab - 2ay0 - 2x0)2 - 4 (a2 + 1) (x0 + (b - y0)2 - r2) = 0
3) 存在两种解法
如果存在两个解，比如xi和xj，那么 可能会 重叠。虽然，这在凹多边形的情况下还不确定。
要检查是否确实存在重叠，您必须检查相交是否发生在您的线段上。
这很简单。假设你的顶点位于点 (x1, y1) 和 之间(x2, y2), 那么有交集只有当...
x1 < xi < x2
或...
x1 < xj < x2
在任何其他情况下，相交发生在顶点的延续，而不是顶点本身。
如果上述条件之一成立，那么并且只有到那时你才知道你的圆泄漏到多边形之外。
最终角形：凹边
如前所述，接触多边形是可以的，因此还有最后一个没有包含在上面的角落：接触凹边。
凹边是内角大于180°的边。因此，无论何时与多边形有交点，如果交点发生在凹边上，您都希望忽略它。
以上所有方法都适用于任何多边形，而不仅仅是三角形和六边形。
给定一个圆心 (Xc,Yc) 和半径 r 以及在数组内部具有顶点的多边形，这样 顶点[] = { (Xv1, Yv1) , ... , (Xvn , Yvn) } 其中 n 是顶点数。
我想知道圆是否在多边形内部。我假设（并且可以安全地假设）多边形中没有孔。
我检查的唯一多边形将是三角形和五边形。
到目前为止我所做的是计算圆心是否在多边形内部。这个函数叫做 isInside().
如何检查圆是否完全在我正在检查的多边形内部？摸一下就可以了
更具体地说，我在计算圆和多边形的关系时遇到了问题，而这对于解决这个问题至关重要。我了解如何查找圆心是否在多边形内部，但如果完整的圆包含在多边形中则无法查找。
任何帮助:)
方法 1：简单，但不精确
您已经实现了一种检查点是否在多边形内的算法。那么，为什么不将圆近似为等边多边形呢？您只需检查圆的 16 或 64 或 256 个点。
方法 2：更复杂，但更精确
- 找到多边形每一边的法向量（您可以轻松计算）。
- 通过这个法向量求圆心到边的距离（直线相交也是一个简单的任务）。
- 如果距离小于圆的半径，则圆在多边形外。
- 否则，如果每条边到法线点的距离大于或等于圆的半径，则圆在里面。
以下假设您已经知道the center of the circle is inside the polygon。有几件事你想检查一下你的定义 touching the vertices is ok adds some cornercases。此解决方案也适用于凹多边形。
提前检查
要使圆完全在 多边形内部，我们需要所有边都在外部 圆。特别是这确保多边形不完全在圆内。
给定半径为 r 的圆，圆心为 c，边为 e0 , e1, ..., en 的多边形，因此一个必要条件是对于所有 i < n:
d(c, ei) >= r
其中 d 是第 euclidian distance.
如果上述任何一条边都不成立，那么要么多边形和圆之间存在交点，要么多边形本身完全在圆内。
圆是否与多边形相交
最后的检查是圆在里面的必要条件，虽然它是不充分的，因为有可能所有的边都在圆的外面，但是圆仍然漏出一个顶点。
让我们先记住一些我们需要的公式。
圆心为 (x0, y0 的圆心为 r 的方程):
(x - x0)2 + (y - y0)2 = r2
因此与直线 y = ax + b 的交点通过求解找到：
(x - x0)2 + (ax + b - y0)2 = r2
这只不过是一个可以重写为的二次方程：
(a2 + 1)x2 + (2ab - 2ay0 - 2x0)x + (x0 + (b - y0)2 - r2) = 0
你可以用每个顶点的 quadratic formula 来解决这个问题。那么你就有了三种可能。
1) 无解
这表示与该顶点不存在交集。使用高级语言，您可以捕获某种 MathError 异常来检测它。否则，您可以在数学上检查 discriminant 的符号，因为如果它是负数，就会发生这种情况。
(2ab - 2ay0 - 2x0)2 - 4 (a2 + 1) (x0 + (b - y0)2 - r2) < 0
2) 存在唯一解
如果方程只有一个解，即两个解相同，则圆可能会接触，但不会漏出边缘。你说这仍然被认为是在你的情况下多边形内。
从数学上讲，当判别式为零时会发生这种情况。
(2ab - 2ay0 - 2x0)2 - 4 (a2 + 1) (x0 + (b - y0)2 - r2) = 0
3) 存在两种解法
如果存在两个解，比如xi和xj，那么 可能会 重叠。虽然，这在凹多边形的情况下还不确定。
要检查是否确实存在重叠，您必须检查相交是否发生在您的线段上。
这很简单。假设你的顶点位于点 (x1, y1) 和 之间(x2, y2), 那么有交集只有当...
x1 < xi < x2
或...
x1 < xj < x2
在任何其他情况下，相交发生在顶点的延续，而不是顶点本身。
如果上述条件之一成立，那么并且只有到那时你才知道你的圆泄漏到多边形之外。
最终角形：凹边
如前所述，接触多边形是可以的，因此还有最后一个没有包含在上面的角落：接触凹边。
凹边是内角大于180°的边。因此，无论何时与多边形有交点，如果交点发生在凹边上，您都希望忽略它。
以上所有方法都适用于任何多边形，而不仅仅是三角形和六边形。