algorithm - 找到圆形和矩形重叠的中点

Question

我正在开发一个小型游戏几何库，在许多其他方法中，我希望能够找到圆形和矩形之间的交点中点。但是，我很难想到一个快速的算法来做到这一点。有谁知道执行此操作的好算法？

如果这意味着算法会明显更快，我愿意牺牲完美的准确性。

我表示每个形状的基本方式是:

圆圈:

• float x, y(居中)
• float r(半径)

矩形:

• float x, y(居中)
• float w, h(宽度和高度值，它们表示从中心到相应边缘的 x 和 y 距离)。

---

编辑:

由于似乎对我所说的“中点”的含义感到困惑，所以让我澄清一下:

鉴于圆形和矩形相交，它们的重叠产生了一个区域。我希望确定该区域的地理中心(准确地或确定近似值)。

示例:http://en.wikipedia.org/wiki/Centroid

---

编辑#2:

你们给了我一些想法，让我努力实现其中的一些，然后我会回复你们。

---

结束语:

我将 Gareth 的回答标记为已接受，因为它为我提供了最终结果的想法，但我的最终实现与他的不同，因此我将在此处进行解释。

我想出了两种通用的方法:一种是完全准确的(但需要更复杂的编程和更多的数学)，另一种是更简单/更快的方法，一直很接近。我最终选择了后者，但这里有两种方法:

方法一:形状分割:

基本上，这个想法是将重叠区域打散成离散的部分，这些部分可以很容易地计算出它们的中点和面积，然后对整个结果取加权平均值。

此处显示的示例包含三个子部分:一个占据大部分区域的中心矩形，以及两个用于圆边的曲线段。

方法二:线插值

首先，您需要计算矩形中的一个点作为基准位置。这应该是一个容易计算并且在重叠中的点。我在这一点上使用的是圆形和矩形的所有边交点的平均值(如果不存在边交点，我默认使用圆的位置，因为这意味着一个形状包含在另一个形状中)。

C计算圆心和那个点之间的线。然后，计算位于重叠区域内的段。该区域的中点取为该线段的中点。

此方法不准确，但总是在两个对象内产生一个点，并且生成的点通常靠近中间(因此在不经意的眼中“看起来”不错)。它也更简单、更快，所以我选择了它。

Answer 1

如果您对近似值满意，请尝试抽样。将矩形分成一定数量的正方形，并为每个正方形估计它是否大部分在圆内(也许只是通过测试它的中心是否在圆内)。

然后申请the centroid formula ,

The centroid of a plane figure can be computed by dividing it into a finite number of simpler figures, computing the centroid C_i and area A_i of each part, and then computing Σ C_i A_i / Σ A_i.

在这种情况下特别简单，因为正方形的质心是它的中心，并且所有 A_i 都相等。

(几何剖分为suggested by Vaughn Cato会得到准确的答案，但这种近似方法的优点是简单:它会更难被错误地编程。)

---

CodeBunny 在评论中要求“更简单的、基于方程的结果”。这是使用方程式计算结果的方法，但我认为它并不“更简单”。

首先，您必须通过将圆与矩形的每条边相交并计算相交数来确定您处于哪种几何情况。我相信，这会给您留下以下十四种情况之一:

然后，对于每种情况，您将交叉点分解为圆形线段和凸多边形的总和。计算其中每一个的面积和质心(参见维基百科的公式:area 和 centroid 圆段；area and centroid of convex polygon)并使用我上面给出的质心公式将它们组合起来。

这绝非简单:几何案例的枚举很棘手(我很容易错过一两个案例:在我第一次尝试时我只发现了十一个案例)，并且计算的编程很微妙(这很容易只在其中一种情况下犯错误而没有注意到)。