python - 由重叠圆圈组成的图形的面积和周长

Question

我计划用 Python 编写这段代码，但这更像是一个一般的算法设计问题，而不是与任何特定语言有关的问题。我正在编写代码来模拟混合火箭发动机，长话短说，问题涉及找到由许多(可能数千个)重叠圆组成的图形的周长和面积。

我在 stackexchange 上看到了这个:

Combined area of overlapping circles

除了我还需要找到周长。该线程中有人提到了 Monte Carlo(随机点猜测)方法，但是它可以用来求周长和面积吗？

提前致谢。

Answer 1

我添加了第二个答案而不是扩展第一个答案，因为我非常肯定另一个答案是正确的，但我不太确定这个答案是否正确。我做了一些简单的测试，似乎可以工作，但请指出我的错误。

这基本上是我之前所说内容的快速实现:

from math import atan2, pi

def intersectLine (a, b):
    s0, e0, s1, e1 = a [0], a [1], b [0], b [1]
    s = max (s0, s1)
    e = min (e0, e1)
    if e <= s: return (0, 0)
    return (s, e)

class SectorSet:
    def __init__ (self, sectors):
        self.sectors = sectors [:]

    def __repr__ (self):
        return repr (self.sectors)

    def __iadd__ (self, other):
        acc = []
        for mine in self.sectors:
            for others in other.sectors:
                acc.append (intersectLine (mine, others) )
        self.sectors = [x for x in acc if x [0] != x [1] ]
        return self

class Circle:
    CONTAINS = 0
    CONTAINED = 1
    DISJOINT = 2
    INTERSECT = 3

    def __init__ (self, x, y, r):
        self.x = float (x)
        self.y = float (y)
        self.r = float (r)

    def intersect (self, other):
        a, b, c, d, r0, r1 = self.x, self.y, other.x, other.y, self.r, other.r
        r0sq, r1sq = r0 ** 2, r1 ** 2
        Dsq = (c - a) ** 2 + (d - b) ** 2
        D = Dsq ** .5
        if D >= r0 + r1:
            return Circle.DISJOINT, None, None
        if D <= abs (r0 - r1):
            return Circle.CONTAINED if r0 < r1 else Circle.CONTAINS, None, None
        dd = .25 * ( (D + r0 + r1) * (D + r0 - r1) * (D - r0 + r1) * (-D + r0 + r1) ) ** .5
        x = (a + c) / 2. + (c - a) * (r0sq - r1sq) / 2. / Dsq
        x1 = x + 2 * (b - d) / Dsq * dd
        x2 = x - 2 * (b - d) / Dsq * dd
        y = (b + d) / 2. + (d - b) * (r0sq - r1sq) / 2. / Dsq
        y1 = y - 2 * (a - c) / Dsq * dd
        y2 = y + 2 * (a - c) / Dsq * dd
        return Circle.INTERSECT, (x1, y1), (x2, y2)

    def angle (self, point):
        x0, y0, x, y = self.x, self.y, point [0], point [1]
        a = atan2 (y - y0, x - x0) + 1.5 * pi
        if a >= 2 * pi: a -= 2 * pi
        return a / pi * 180

    def sector (self, other):
        typ, i1, i2 = self.intersect (other)
        if typ == Circle.DISJOINT: return SectorSet ( [ (0, 360) ] )
        if typ == Circle.CONTAINS: return SectorSet ( [ (0, 360) ] )
        if typ == Circle.CONTAINED: return SectorSet ( [] )
        a1 = self.angle (i1)
        a2 = self.angle (i2)
        if a1 > a2: return SectorSet ( [ (0, a2), (a1, 360) ] )
        return SectorSet ( [ (a1, a2) ] )

    def outline (self, others):
        sectors = SectorSet ( [ (0, 360) ] )
        for other in others:
            sectors += self.sector (other)
        u = 2 * self.r * pi
        total = 0
        for start, end in sectors.sectors:
            total += (end - start) / 360. * u
        return total

def outline (circles):
    total = 0
    for circle in circles:
        others = [other for other in circles if circle != other]
        total += circle.outline (others)
    return total

a = Circle (0, 0, 2)
b = Circle (-2, -1, 1)
c = Circle (2, -1, 1)
d = Circle (0, 2, 1)
print (outline ( [a, b, c, d] ) )

两个圆的交点计算公式无耻地偷自here .