找到圆和矩形之间重叠的中点
我正在研究一个小型游戏几何图书馆，以及其他一些方法中，我希望能够找到圆和矩形之间的交点的中点。 但是，我很难考虑使用快速算法。 有谁知道一个好的算法来做到这一点？
如果它意味着算法会显着加快，我愿意牺牲完美的精度。
我代表每种形状的基本方式是：
圈子 ：
矩形 ：
编辑：
由于我的意思是“中点”似乎存在混淆，让我澄清一下：
考虑到圆和矩形相交，就有一个由它们重叠而产生的区域。 我希望确定这个地区的地理中心（要么确切地，要么确定一个近似的近似值）。
例如：http://en.wikipedia.org/wiki/Centroid
编辑＃2：
你们给了我一些想法，让我来实施其中的一些想法，我会尽快回复你们。
闭幕的想法：
我将Gareth的答案标记为已接受的答案，因为它给了我最终结果的想法，但是我的最终实现与他的不同，所以我会在这里解释它。
我提出了两种通用的方法：一种是完全准确的（但需要更复杂的编程和更多的数学运算），另一种更简单/更快的方式，这种方式一直非常接近。 我结束了与后者，但这里有两种方法：
方法1：形状碎片化：
基本上，这个想法是将重叠区域分解成离散的片段，这些片段可以容易地计算它们的中点和面积，然后对整个结果取加权平均值。
此处显示的示例有三个子部分：占据该区域大部分的中心矩形和用于圆形边缘的两个曲线部分。
方法2：行插补
首先，您需要计算矩形中的一个点，该点将成为基础位置。 这应该是一个易于计算并且重叠的点。 我在这一点上使用的是圆和矩形的所有边交点的平均值（如果不存在边交点，我默认为圆的位置，因为它表示一个形状包含在另一个中）。
计算圆心和该点之间的线。 然后，计算位于重叠区域内的片段。 该区域的中点被视为该线段的中点。
这种方法是不准确的，但总是在两个对象内产生一个点，并且所得到的点通常接近中间（所以它对于随便的眼睛“看起来很好”）。 它也更加简单和快捷，所以我随之而去。
如果您对近似值感到满意，请尝试采样。 将矩形分成若干个正方形，并且对于每个平方估计，如果它主要在圆内（可能只是通过测试其中心是否在圆内）。
然后应用质心公式，
平面图的质心可以通过将其分成有限数量的更简单的图形，计算每个部分的质心Ci和面积Ai，然后计算ΣCi Ai /ΣAi来计算。
这在这种情况下特别简单，因为正方形的质心是其中心，并且所有的Ai都是相等的。
（Vaughn Cato建议的几何解剖将得到确切的答案，但这种近似方法具有简单性的优点：编程错误会更困难。）
CodeBunny在评论中询问“简单的，基于等式的结果”。 以下是如何使用方程计算结果，但我认为这不是“更简单”。
首先，你必须通过将圆与矩形的每条边交叉并计算交点的数量来确定你所处的几何情况。 我相信，这会让你有以下十四种情况之一：
然后，对于每种情况，将该交点解剖成圆形段和凸多边形的总和。 计算每个面的面积和质心（请参阅维基百科的公式：圆形面的面积和质心;凸多边形的面积和质心），并使用上面给出的质心公式对它们进行组合。
这绝不是一件简单的事情：枚举几何案例很棘手（我可以很容易地错过了一两个案例：在第一次尝试时我只发现了11个案例），并且对计算进行编程很微妙（很容易做出只在其中一个案件中发生错误，不予通知）。
一种方法是将其分解成下列情况：
然后，在每种情况下找到质心。 例如，在第三种情况下，交点是圆形线段，您可以使用标准公式找到该交点的质心。 在第四种情况下，您将以三角形和圆形段结束。 您可以通过将每件的面积乘以其各自的质心，然后除以总面积来找到组合面积的质心。
如果我正确理解您的要求，您希望找到两个形状重叠的区域的中心？
那是对的吗？
有一个中心（x，y）和半径为r的圆。 有一个中心（x，y），宽度w和高度h的矩形
所以这是第一个差距：
你不能在x，y平面上定义一个只有中心点和宽度和高度的矩形。 矩形面向哪个方向？
如上所述的圆的方程是（xa）^ 2 +（yb）^ 2 = r ^ 2
可以同时用一条线的方程求解这个方程以得到交点。
第二个差距：
一条线可以在2个点，一个点或没有点相交一个圆 - 你确定知道圆和矩形总会重叠，因此线的两点与圆相交？
假设是这样，从这点（找到两个交点）不应该太困难来计算交点之间的中点，然后在垂直于该中点的直线的中点绘制到边缘的圆（形状的交点面积的中点）
这绝不意味着'这是答案'的答案，但我希望这有所帮助？
史蒂夫
链接地址: http://www.djcxy.com/p/84981.html上一篇: Find the midpoint of overlap between circle and rectangle
下一篇: finding the number of integer points under a triangle, square and circle