找到圆和矩形之间的重叠中点

Question

我正在研究一个小型游戏几何库,在一堆其他方法中,我希望能够找到圆形和矩形之间的交点中点.但是,我很难想到快速算法.有谁知道这样做的好算法？

如果这意味着算法会明显加快,我愿意牺牲完美的准确性.

我代表每个形状的基本方法是:

圈子:

矩形:

编辑:

由于似乎对"中点"的含义感到困惑,让我澄清一下:

假设圆和矩形相交,则存在由它们的重叠创建的区域.我想确定这个区域的地理中心(确切地说,或者确定一个近似的近似值).

编辑#2:

你们给了我一些想法,让我努力实现其中的一些,我会回复你.

闭幕思考:

我把Gareth的答案标记为已接受的答案,因为它给了我最终结果的想法,但我的最终实现与他的不同,所以我将在这里解释.

我想出了两种一般的方法:一种是完全准确的(但需要更复杂的编程和更多的数学运算),另一种是更简单/更快的方式,它始终相当接近.我最后选择了后者,但这里有两种方法:

方法1:形状碎片:

形状碎片的一个例子

基本上,我们的想法是将重叠区域分解为可以轻松计算其中点和面积的离散区段,然后对整个结果进行加权平均.

此处显示的示例有三个子部分:占据区域大部分的中心矩形,以及用于圆的边缘的两个弯曲部分.

方法2:线插值

线插值示例

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

计算圆心和该点之间的直线.然后,计算位于重叠区域内的段.该区域的中点被视为该线段的中点.

这种方法不准确,但总是在两个对象中产生一个点,并且结果点通常接近中间(因此它看起来对于随意的眼睛来说是好的).它也更简单,更快,所以我选择了它.

Answer 1

如果您对近似值感到满意,请尝试采样.将矩形划分为若干个正方形,并且对于每个正方形估计,如果它主要位于圆内(可能仅通过测试其中心是否在圆内).

矩形划分为正方形,显示哪些正方形属于与圆形的交点

然后应用质心公式,

平面图形的形心可通过将其分成有限数量的简单的数字,计算的质心C下计算_我和面积A _我每个部分的,然后计算ΣÇ _我甲_我 /Σ甲_我.

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

(Vaughn Cato建议的几何解剖将得到确切的答案,但这种近似方法具有简单的优点:对它进行错误编程会更加困难.)

CodeBunny在评论中询问"更简单,基于方程式的结果".以下是使用方程计算结果的方法,但我不认为它"更简单".

首先,您必须通过将圆与矩形的每个边相交并计算交叉点的数量来确定您所处的几何情况.我相信,这让你有以下十四种情况之一:

圆与矩形交叉的情况

然后,对于每种情况,您将交点分解为圆形段和凸多边形的总和.计算每个的这些区域和形心(见维基百科中的公式:面积和形心圆形段的; 区和凸多边形的形心),并使用该质心上面式I中,得到将它们结合起来.

这绝不是简单的:几何案例的枚举很棘手(我很容易错过一两个案例:在我第一次尝试时我只发现了11个案例),编程计算很精细(很容易制作一个只有一个案例中的错误,而不是通知).