如何计算三角形（指定为三（X，Y）对）和圆（X，Y，R）之间的交叉区域？我做了一些搜索无济于事 . 这是为了工作，而不是学校 . :)

它在C＃中看起来像这样：

struct { PointF vert[3]; } Triangle;
struct { PointF center; float radius; } Circle;

// returns the area of intersection, e.g.:
// if the circle contains the triangle, return area of triangle
// if the triangle contains the circle, return area of circle
// if partial intersection, figure that out
// if no intersection, return 0
double AreaOfIntersection(Triangle t, Circle c)
{
 ...
}

11 回答

0

如果您拥有GPU，则可以使用this技术获取交叉点的像素数 .

回复于 2024-04-28T03:22:39+08:00
31
如果你想要一个精确的解决方案（或者至少与使用浮点运算一样精确），那么这将涉及大量的工作，因为有很多情况需要考虑 .

我计算了九种不同的情况（在下图中按圆圈内三角形的顶点数量分类，以及圆圈中相交或包含的三角形边缘数量）：

（然而，众所周知，这种几何情况的枚举是棘手的，如果我错过了一两个，它就不会让我感到惊讶！）

所以方法是：
- 确定三角形的每个顶点是否在圆内 . 我假设你知道怎么做 .
- 确定三角形的每个边缘是否与圆相交 . （我写了一个方法here，或者看到任何计算几何图书 . ）你需要计算在步骤4中使用的一个或多个交点（如果有的话） .
- 确定您拥有的九个案例中的哪一个 .
- 计算交叉口的面积 . 案例1,2和9很容易 . 在其余六种情况下，我绘制了虚线，以显示如何根据三角形的原始顶点以及在步骤2中计算的交点将交叉区域划分为三角形和circular segments .
这个算法会相当精细并且容易出错，只会影响其中一个案例，因此请确保您拥有涵盖所有九个案例的测试用例（我建议也可以置换测试三角形的顶点） . 特别注意三角形的一个顶点位于圆的边缘的情况 .

如果你不需要一个精确的解决方案，那么光栅化数字和计算交集中的像素（正如其他几个受访者所建议的那样）似乎是一种更容易的代码方法，相应地也不容易出错 .
回复于 2024-04-28T03:22:39+08:00

首先，我将提醒我们如何找到多边形的区域 . 完成此操作后，找到多边形和圆形之间交点的算法应该很容易理解 .

如何查找多边形的区域

设's look at the case of a triangle, because all the essential logic appears there. Let'假设我们在逆时针绕三角形时有一个带顶点（x1，y1），（x2，y2）和（x3，y3）的三角形，如下图所示：
triangleFigure

然后，您可以通过公式计算面积

A =（x1 y2 x2 y3 x3 y1 - x2y1-x3 y2 - x1y3）/ 2 .

要了解为什么这个公式有效，让我们重新排列它以便它在形式中

A =（x1 y2-x2 y1）/ 2（x2 y3-x3 y2）/ 2（x3 y1-x1y3）/ 2 .

现在第一个术语是以下区域，在我们的案例中是积极的：
enter image description here

如果不清楚绿色区域的面积确实是（x1 y2 - x2 y1）/ 2，则读取this .

第二个任期是这个区域，这也是积极的：

enter image description here

第三个区域如下图所示 . 这次该地区是负面的

enter image description here

添加这三个，我们得到以下图片

enter image description here

我们看到三角形外面的绿色区域被红色区域取消，因此净面积就是三角形的面积，这就说明了为什么我们的公式在这种情况下是正确的 .

我上面所说的是关于为什么区域公式是正确的直观解释 . 更严格的解释是观察到当我们从边缘计算面积时，我们得到的面积与积分r ^2dθ/ 2的面积相同，因此我们有效地将r ^2dθ/ 2积分在边界附近通过多边形和斯托克斯定理，这给出了与在多边形有界的区域上积分rdrdθ相同的结果 . 由于将rdrdθ集成在由多边形限定的区域上给出了区域，我们得出结论，我们的过程必须正确地给出该区域 .

圆与多边形的交点区域

现在让我们讨论如何找到半径为R的圆与多边形的交点区域，如下图所示：

enter image description here

我们有兴趣找到绿色区域 . 正如在单个多边形的情况下，我们可以将计算分解为为多边形的每一边找到一个区域，然后向上添加这些区域 .

我们的第一个区域将如下所示：
enter image description here

第二个区域看起来像
enter image description here

第三个区域将是
enter image description here

同样，前两个区域在我们的情况下是积极的，而第三个区域将是负面的 . 希望取消将有效，以便净面积确实是我们感兴趣的区域 . 让我们看看 .

enter image description here

实际上，这些区域的总和将是我们感兴趣的区域 .

同样，我们可以更加严格地解释其原因 . 让我成为交集定义的区域，让P为多边形 . 然后从前面的讨论中，我们知道我们想要计算围绕I边界的r ^2dθ/ 2的积分 . 但是，这很难做到因为它需要找到交点 .

相反，我们在多边形上做了一个整数 . 我们在多边形的边界上积分了max（r，R）^2dθ/ 2 . 为了找出为什么这给出正确的答案，让我们定义一个函数π，它将极坐标（r，θ）中的一个点作为点（max（r，R），θ） . 参考π（r）= max（r，R）和π（θ）=θ的坐标函数应该不会引起混淆 . 然后我们做的是将π（r）^2dθ/ 2整合到多边形的边界上 .

另一方面，由于π（θ）=θ，这与在多边形的边界上积分π（r）^2dπ（θ）/ 2相同 .

现在做变量的变化，我们发现如果我们在π（P）的边界上积分r ^2dθ/ 2我们会得到相同的答案，其中π（P）是π下的P的图像 .

再次使用斯托克斯定理，我们知道在π（P）的边界上积分r ^2dθ/ 2给出了π（P）的面积 . 换句话说，它给出了与将dxdy积分超过π（P）相同的答案 .

再次使用变量变量，我们知道将dxdy积分超过π（P）与将Jdxdy积分在P上相同，其中J是π的雅可比 .

现在我们可以将Jdxdy的积分分成两个区域：圆圈中的部分和圆圈外的部分 . 现在π仅在圆中留下点，所以J = 1，所以P的这部分的贡献是位于圆中的P部分的面积，即交点的面积 . 第二个区域是圆圈外的区域 . 由于π将该部分折叠到圆的边界，因此J = 0 .

因此，我们计算的确实是交叉区域 .

现在我们相对肯定我们在概念上知道如何找到该区域，让我们更具体地讨论如何计算单个区段的贡献 . 让我们首先看一下我将称之为“标准几何”的片段 . 如下所示 .

enter image description here

在标准几何体中，边缘从左向右水平移动 . 它由三个数字描述：xi，边缘开始的x坐标，xf，边缘结束的x坐标，y，边缘的y坐标 .

现在我们看到如果| y | <R，如图中所示，则边缘将在点（-xint，y）和（xint，y）处与圆相交，其中xint =（R ^ 2-y ^ 2）^（1/2） . 然后我们需要计算的区域被分解为图中标记的三个部分 . 为了得到区域1和区域3，我们可以使用arctan得到各个点的角度，然后将区域等于R ^2Δθ/ 2 . 因此，例如，我们将θi= atan2（y，xi）和θl= atan2（y，-xint）设置 . 然后区域1的区域是R ^ 2（θl-θi）/ 2 . 我们可以类似地获得区域3的面积 .

区域2的区域只是三角形的区域 . 但是，我们必须小心标志 . 我们希望显示的区域为正，因此我们将该区域称为 - （xint - （ - xint））y / 2 .

另外要记住的是，通常，xi不必小于-xint，xf不必大于xint .

另一种需要考虑的情况是| y | > R.这种情况比较简单，因为只有一个部分类似于图中的区域1 .

既然我们知道如何从标准几何中的边缘计算面积，那么剩下要做的就是描述如何将任何边缘转换为标准几何体 .

但这只是一个简单的坐标变化 . 给定一些具有初始顶点vi和最终顶点vf的新x单位向量将是从vi指向vf的单位向量 . 那么xi就是vi从点缀成x的圆心的位移，而xf只是xi加上vi和vf之间的距离 . 同时y由x的楔积给出，其中vi从圆心位移 .

代码

这完成了对算法的描述，现在是时候编写一些代码了 . 我会用java .

首先，由于我们正在与圈子合作，我们应该有一个圆圈类

public class Circle {

    final Point2D center;
    final double radius;

    public Circle(double x, double y, double radius) {
        center = new Point2D.Double(x, y);
        this.radius = radius;
    }

    public Circle(Point2D.Double center, double radius) {
        this(center.getX(), center.getY(), radius);
    }

    public Point2D getCenter() {
        return new Point2D.Double(getCenterX(), getCenterY());
    }

    public double getCenterX() {
        return center.getX();
    }

    public double getCenterY() {
        return center.getY();
    }

    public double getRadius() {
        return radius;
    }

}

对于多边形，我将使用java的 Shape 类 . Shape 有一个 PathIterator ，我可以用来迭代多边形的边缘 .

现在为实际工作 . 我将分离迭代遍历边缘的逻辑，将边缘放在标准几何等中，一旦完成，就从计算区域的逻辑中分离出来 . 这样做的原因是，您可能在将来想要计算除该区域之外的其他内容，并且您希望能够重用必须处理迭代边缘的代码 .

所以我有一个泛型类，它计算类 T 关于我们的多边形圆交集的一些属性 .

public abstract class CircleShapeIntersectionFinder<T> {

它有三个静态方法，可以帮助计算几何：

private static double[] displacment2D(final double[] initialPoint, final double[] finalPoint) {
    return new double[]{finalPoint[0] - initialPoint[0], finalPoint[1] - initialPoint[1]};
}

private static double wedgeProduct2D(final double[] firstFactor, final double[] secondFactor) {
    return firstFactor[0] * secondFactor[1] - firstFactor[1] * secondFactor[0];
}

static private double dotProduct2D(final double[] firstFactor, final double[] secondFactor) {
    return firstFactor[0] * secondFactor[0] + firstFactor[1] * secondFactor[1];
}

有两个实例字段，一个只保留圆的副本的 Circle 和保留方形半径副本的 currentSquareRadius . 这可能看起来很奇怪，但我使用的类实际上是为了找到整个圆形 - 多边形交叉集合的区域 . 这就是为什么我将其中一个圆圈称为"current" .

private Circle currentCircle;
private double currentSquareRadius;

接下来是计算我们想要计算的内容的方法：

public final T computeValue(Circle circle, Shape shape) {
    initialize();
    processCircleShape(circle, shape);
    return getValue();
}

initialize() 和 getValue() 是抽象的 . initialize() 将设置保持总面积为零的变量， getValue() 将返回该区域 . processCircleShape 的定义是

private void processCircleShape(Circle circle, final Shape cellBoundaryPolygon) {
    initializeForNewCirclePrivate(circle);
    if (cellBoundaryPolygon == null) {
        return;
    }
    PathIterator boundaryPathIterator = cellBoundaryPolygon.getPathIterator(null);
    double[] firstVertex = new double[2];
    double[] oldVertex = new double[2];
    double[] newVertex = new double[2];
    int segmentType = boundaryPathIterator.currentSegment(firstVertex);
    if (segmentType != PathIterator.SEG_MOVETO) {
        throw new AssertionError();
    }
    System.arraycopy(firstVertex, 0, newVertex, 0, 2);
    boundaryPathIterator.next();
    System.arraycopy(newVertex, 0, oldVertex, 0, 2);
    segmentType = boundaryPathIterator.currentSegment(newVertex);
    while (segmentType != PathIterator.SEG_CLOSE) {
        processSegment(oldVertex, newVertex);
        boundaryPathIterator.next();
        System.arraycopy(newVertex, 0, oldVertex, 0, 2);
        segmentType = boundaryPathIterator.currentSegment(newVertex);
    }
    processSegment(newVertex, firstVertex);
}

我们花一点时间快速查看 initializeForNewCirclePrivate . 此方法仅设置实例字段，并允许派生类存储圆的任何属性 . 它的定义是

private void initializeForNewCirclePrivate(Circle circle) {
    currentCircle = circle;
    currentSquareRadius = currentCircle.getRadius() * currentCircle.getRadius();
    initializeForNewCircle(circle);
}

initializeForNewCircle 是抽象的，一个实现将是它存储圆半径以避免必须做平方根 . 无论如何回到 processCircleShape . 在调用 initializeForNewCirclePrivate 之后，我们检查多边形是否为 null （我将其解释为空多边形），如果它是 null 则返回 . 在这种情况下，我们的计算区域将为零 . 如果多边形不是 null ，那么我们得到多边形的 PathIterator . 我调用的 getPathIterator 方法的参数是可以应用于路径的仿射变换 . 我不想申请一个，所以我只是通过 null .

接下来，我声明将跟踪顶点的 double[] . 我必须记住第一个顶点，因为 PathIterator 只给我每个顶点一次，所以我必须在它给我最后一个顶点后返回，并形成一个带有最后一个顶点和第一个顶点的边 .

下一行的 currentSegment 方法将下一个顶点放在其参数中 . 它返回一个代码，告诉你它何时不在顶点 . 这就是我的while循环的控制表达式就是这样的原因 .

此方法的其余大部分代码都是与迭代顶点相关的无趣逻辑 . 重要的是，每次迭代while循环时，我调用 processSegment 然后在方法结束时再次调用 processSegment 来处理将最后一个顶点连接到第一个顶点的边 .

我们来看看 processSegment 的代码：

private void processSegment(double[] initialVertex, double[] finalVertex) {
    double[] segmentDisplacement = displacment2D(initialVertex, finalVertex);
    if (segmentDisplacement[0] == 0 && segmentDisplacement[1] == 0) {
        return;
    }
    double segmentLength = Math.sqrt(dotProduct2D(segmentDisplacement, segmentDisplacement));
    double[] centerToInitialDisplacement = new double[]{initialVertex[0] - getCurrentCircle().getCenterX(), initialVertex[1] - getCurrentCircle().getCenterY()};
    final double leftX = dotProduct2D(centerToInitialDisplacement, segmentDisplacement) / segmentLength;
    final double rightX = leftX + segmentLength;
    final double y = wedgeProduct2D(segmentDisplacement, centerToInitialDisplacement) / segmentLength;
    processSegmentStandardGeometry(leftX, rightX, y);
}

在这种方法中，我实现了将边缘转换为标准几何的步骤，如上所述 . 首先，我计算 segmentDisplacement ，从初始顶点到最终顶点的位移 . 这定义了标准几何的x轴 . 如果这个位移为零，我会提前返回 .

接下来我计算位移的长度，因为这是获得x单位向量所必需的 . 获得此信息后，我计算从圆心到初始顶点的位移 . 这个与 segmentDisplacement 的点积给了我 leftX ，我一直在调用xi . 然后 rightX ，我一直在调用xf，只是 leftX + segmentLength . 最后我按照上面的描述做了楔形产品 y .

现在我已经将问题转换为标准几何体，它将很容易处理 . 这就是 processSegmentStandardGeometry 方法的作用 . 我们来看看代码吧

private void processSegmentStandardGeometry(double leftX, double rightX, double y) {
    if (y * y > getCurrentSquareRadius()) {
        processNonIntersectingRegion(leftX, rightX, y);
    } else {
        final double intersectionX = Math.sqrt(getCurrentSquareRadius() - y * y);
        if (leftX < -intersectionX) {
            final double leftRegionRightEndpoint = Math.min(-intersectionX, rightX);
            processNonIntersectingRegion(leftX, leftRegionRightEndpoint, y);
        }
        if (intersectionX < rightX) {
            final double rightRegionLeftEndpoint = Math.max(intersectionX, leftX);
            processNonIntersectingRegion(rightRegionLeftEndpoint, rightX, y);
        }
        final double middleRegionLeftEndpoint = Math.max(-intersectionX, leftX);
        final double middleRegionRightEndpoint = Math.min(intersectionX, rightX);
        final double middleRegionLength = Math.max(middleRegionRightEndpoint - middleRegionLeftEndpoint, 0);
        processIntersectingRegion(middleRegionLength, y);
    }
}

第一个 if 区分 y 足够小以使边可以与圆相交的情况 . 如果 y 很大并且没有交叉的可能性，那么我调用该方法来处理这种情况 . 否则我处理可能交叉的情况 .

如果可以交叉，我计算交点的x坐标 intersectionX ，并将边缘分成三个部分，分别对应于标准几何图形的区域1,2和3以上 . 首先我处理区域1 .

为了处理区域1，我检查 leftX 是否确实小于 -intersectionX ，否则将没有区域1.如果有区域1，那么我需要知道它何时结束 . 它以 rightX 和 -intersectionX 的最小值结束 . 在找到这些x坐标后，我处理了这个非交叉区域 .

处理区域3我做了类似的事情 .

对于区域2，我必须做一些逻辑来检查 leftX 和 rightX 实际上是否在 -intersectionX 和 intersectionX 之间包含了一些区域 . 找到区域后，我只需要区域的长度和 y ，所以我将这两个数字传递给处理区域2的抽象方法 .

现在让我们来看看 processNonIntersectingRegion 的代码

private void processNonIntersectingRegion(double leftX, double rightX, double y) {
    final double initialTheta = Math.atan2(y, leftX);
    final double finalTheta = Math.atan2(y, rightX);
    double deltaTheta = finalTheta - initialTheta;
    if (deltaTheta < -Math.PI) {
        deltaTheta += 2 * Math.PI;
    } else if (deltaTheta > Math.PI) {
        deltaTheta -= 2 * Math.PI;
    }
    processNonIntersectingRegion(deltaTheta);
}

我只需使用 atan2 来计算 leftX 和 rightX 之间的角度差 . 然后我添加代码来处理 atan2 中的不连续性，但这可能是不必要的，因为不连续发生在180度或0度 . 然后我将角度差异传递给抽象方法 . 最后我们只有抽象方法和getter：

protected abstract void initialize();

    protected abstract void initializeForNewCircle(Circle circle);

    protected abstract void processNonIntersectingRegion(double deltaTheta);

    protected abstract void processIntersectingRegion(double length, double y);

    protected abstract T getValue();

    protected final Circle getCurrentCircle() {
        return currentCircle;
    }

    protected final double getCurrentSquareRadius() {
        return currentSquareRadius;
    }

}

现在让我们来看看扩展类， CircleAreaFinder

public class CircleAreaFinder extends CircleShapeIntersectionFinder<Double> {

public static double findAreaOfCircle(Circle circle, Shape shape) {
    CircleAreaFinder circleAreaFinder = new CircleAreaFinder();
    return circleAreaFinder.computeValue(circle, shape);
}

double area;

@Override
protected void initialize() {
    area = 0;
}

@Override
protected void processNonIntersectingRegion(double deltaTheta) {
    area += getCurrentSquareRadius() * deltaTheta / 2;
}

@Override
protected void processIntersectingRegion(double length, double y) {
    area -= length * y / 2;
}

@Override
protected Double getValue() {
    return area;
}

@Override
protected void initializeForNewCircle(Circle circle) {

}

}

它有一个字段 area 来跟踪该区域 . initialize 按预期将区域设置为零 . 当我们处理非交叉边时，我们将面积增加R ^2Δθ/ 2，如上所述 . 对于交叉边，我们将面积减少 y*length/2 . 这是因为我们决定应该将 y 的负值对应于正面区域 .

现在好的一点是，如果我们想要跟踪周边，我们就没有必要做更多的工作 . 我定义了一个 AreaPerimeter 类：

public class AreaPerimeter {

    final double area;
    final double perimeter;

    public AreaPerimeter(double area, double perimeter) {
        this.area = area;
        this.perimeter = perimeter;
    }

    public double getArea() {
        return area;
    }

    public double getPerimeter() {
        return perimeter;
    }

}

现在我们只需要使用 AreaPerimeter 作为类型再次扩展我们的抽象类 .

public class CircleAreaPerimeterFinder extends CircleShapeIntersectionFinder<AreaPerimeter> {

    public static AreaPerimeter findAreaPerimeterOfCircle(Circle circle, Shape shape) {
        CircleAreaPerimeterFinder circleAreaPerimeterFinder = new CircleAreaPerimeterFinder();
        return circleAreaPerimeterFinder.computeValue(circle, shape);
    }

    double perimeter;
    double radius;
    CircleAreaFinder circleAreaFinder;

    @Override
    protected void initialize() {
        perimeter = 0;
        circleAreaFinder = new CircleAreaFinder();
    }

    @Override
    protected void initializeForNewCircle(Circle circle) {
        radius = Math.sqrt(getCurrentSquareRadius());
    }

    @Override
    protected void processNonIntersectingRegion(double deltaTheta) {
        perimeter += deltaTheta * radius;
        circleAreaFinder.processNonIntersectingRegion(deltaTheta);
    }

    @Override
    protected void processIntersectingRegion(double length, double y) {
        perimeter += Math.abs(length);
        circleAreaFinder.processIntersectingRegion(length, y);
    }

    @Override
    protected AreaPerimeter getValue() {
        return new AreaPerimeter(circleAreaFinder.getValue(), perimeter);
    }

}

我们有一个变量 perimeter 来跟踪周长，我们记得 radius 的值，以避免必须多次调用 Math.sqrt ，并且我们将区域的计算委托给我们的 CircleAreaFinder . 我们可以看到周边的公式很简单 .

这里是参考 CircleShapeIntersectionFinder 的完整代码

private static double[] displacment2D(final double[] initialPoint, final double[] finalPoint) {
        return new double[]{finalPoint[0] - initialPoint[0], finalPoint[1] - initialPoint[1]};
    }

    private static double wedgeProduct2D(final double[] firstFactor, final double[] secondFactor) {
        return firstFactor[0] * secondFactor[1] - firstFactor[1] * secondFactor[0];
    }

    static private double dotProduct2D(final double[] firstFactor, final double[] secondFactor) {
        return firstFactor[0] * secondFactor[0] + firstFactor[1] * secondFactor[1];
    }

    private Circle currentCircle;
    private double currentSquareRadius;

    public final T computeValue(Circle circle, Shape shape) {
        initialize();
        processCircleShape(circle, shape);
        return getValue();
    }

    private void processCircleShape(Circle circle, final Shape cellBoundaryPolygon) {
        initializeForNewCirclePrivate(circle);
        if (cellBoundaryPolygon == null) {
            return;
        }
        PathIterator boundaryPathIterator = cellBoundaryPolygon.getPathIterator(null);
        double[] firstVertex = new double[2];
        double[] oldVertex = new double[2];
        double[] newVertex = new double[2];
        int segmentType = boundaryPathIterator.currentSegment(firstVertex);
        if (segmentType != PathIterator.SEG_MOVETO) {
            throw new AssertionError();
        }
        System.arraycopy(firstVertex, 0, newVertex, 0, 2);
        boundaryPathIterator.next();
        System.arraycopy(newVertex, 0, oldVertex, 0, 2);
        segmentType = boundaryPathIterator.currentSegment(newVertex);
        while (segmentType != PathIterator.SEG_CLOSE) {
            processSegment(oldVertex, newVertex);
            boundaryPathIterator.next();
            System.arraycopy(newVertex, 0, oldVertex, 0, 2);
            segmentType = boundaryPathIterator.currentSegment(newVertex);
        }
        processSegment(newVertex, firstVertex);
    }

    private void initializeForNewCirclePrivate(Circle circle) {
        currentCircle = circle;
        currentSquareRadius = currentCircle.getRadius() * currentCircle.getRadius();
        initializeForNewCircle(circle);
    }

    private void processSegment(double[] initialVertex, double[] finalVertex) {
        double[] segmentDisplacement = displacment2D(initialVertex, finalVertex);
        if (segmentDisplacement[0] == 0 && segmentDisplacement[1] == 0) {
            return;
        }
        double segmentLength = Math.sqrt(dotProduct2D(segmentDisplacement, segmentDisplacement));
        double[] centerToInitialDisplacement = new double[]{initialVertex[0] - getCurrentCircle().getCenterX(), initialVertex[1] - getCurrentCircle().getCenterY()};
        final double leftX = dotProduct2D(centerToInitialDisplacement, segmentDisplacement) / segmentLength;
        final double rightX = leftX + segmentLength;
        final double y = wedgeProduct2D(segmentDisplacement, centerToInitialDisplacement) / segmentLength;
        processSegmentStandardGeometry(leftX, rightX, y);
    }

    private void processSegmentStandardGeometry(double leftX, double rightX, double y) {
        if (y * y > getCurrentSquareRadius()) {
            processNonIntersectingRegion(leftX, rightX, y);
        } else {
            final double intersectionX = Math.sqrt(getCurrentSquareRadius() - y * y);
            if (leftX < -intersectionX) {
                final double leftRegionRightEndpoint = Math.min(-intersectionX, rightX);
                processNonIntersectingRegion(leftX, leftRegionRightEndpoint, y);
            }
            if (intersectionX < rightX) {
                final double rightRegionLeftEndpoint = Math.max(intersectionX, leftX);
                processNonIntersectingRegion(rightRegionLeftEndpoint, rightX, y);
            }
            final double middleRegionLeftEndpoint = Math.max(-intersectionX, leftX);
            final double middleRegionRightEndpoint = Math.min(intersectionX, rightX);
            final double middleRegionLength = Math.max(middleRegionRightEndpoint - middleRegionLeftEndpoint, 0);
            processIntersectingRegion(middleRegionLength, y);
        }
    }

    private void processNonIntersectingRegion(double leftX, double rightX, double y) {
        final double initialTheta = Math.atan2(y, leftX);
        final double finalTheta = Math.atan2(y, rightX);
        double deltaTheta = finalTheta - initialTheta;
        if (deltaTheta < -Math.PI) {
            deltaTheta += 2 * Math.PI;
        } else if (deltaTheta > Math.PI) {
            deltaTheta -= 2 * Math.PI;
        }
        processNonIntersectingRegion(deltaTheta);
    }

    protected abstract void initialize();

    protected abstract void initializeForNewCircle(Circle circle);

    protected abstract void processNonIntersectingRegion(double deltaTheta);

    protected abstract void processIntersectingRegion(double length, double y);

    protected abstract T getValue();

    protected final Circle getCurrentCircle() {
        return currentCircle;
    }

    protected final double getCurrentSquareRadius() {
        return currentSquareRadius;
    }

无论如何，这是我对算法的描述 . 我认为这很好，因为它是确切的，并没有那么多的情况要检查 .

回复于 2024-04-28T03:22:39+08:00

2

我差不多一年半了，但我想也许人们会对我写的code here感兴趣，我认为这样做是正确的 . 查看靠近底部的功能IntersectionArea . 一般的方法是挑选由圆圈限定的凸多边形，然后处理小圆形帽 .

回复于 2024-04-28T03:22:39+08:00
1

假设你说的是整数像素，而不是真实的，那么天真的实现就是遍历三角形的每个像素，并检查圆心的中心与半径之间的距离 .

这不是一个可爱的公式，或者特别快，但它确实完成了工作 .

回复于 2024-04-28T03:22:39+08:00
1

试试computational geometry

注意：这不是一个小问题，我希望它不是功课;-)

回复于 2024-04-28T03:22:39+08:00
1
我认为你不应该将圆形近似为一组三角形，而不是用多边形逼近它的形状 . 天真算法看起来像：
- 将圆转换为具有所需顶点数的多边形 .
- 计算两个多边形的交集（转换后的圆和三角形） .
- 计算该交点的平方 .
您可以通过将步骤2和步骤3组合到单个函数中来优化此算法 .

阅读此链接：
Area of convex polygon
Intersection of convex polygons
回复于 2024-04-28T03:22:39+08:00
0

由于您的形状是凸的，您可以使用蒙特卡罗面积估计 .

在圆圈和三角形周围画一个方框 .

在框中选择随机点，并计算圆圈中落下的数量，以及圆圈和三角形中落入的数量 .

交叉区域circle圆形区域*＃以圆圈和三角形为点/以圆圈为圆点

当估计区域在一定数量的回合中没有变化超过一定量时停止选择点，或者仅根据框的区域选择固定数量的点 . 区域估计应该快速收敛，除非你的一个形状的面积非常小 .

注意：以下是确定点是否在三角形中的方法：Barycentric coordinates

回复于 2024-04-28T03:22:39+08:00
27

你需要多少精确？如果您可以使用更简单的形状来近似圆形，则可以简化问题 . 例如，将圆形建模为在中心相交的一组非常窄的三角形并不困难 .

回复于 2024-04-28T03:22:39+08:00
0
如果只有一个三角形的线段与圆相交，那么纯数学解决方案就不会太难 . 一旦知道两个交点何时出现，就可以使用距离公式来找到弦长 .

根据these equations：
```
ϑ = 2 sin⁻¹(0.5 c / r)
A = 0.5 r² (ϑ - sin(ϑ))
```
其中c是弦长，r是半径，θ是通过中心的角度，A是面积 . 请注意，如果切掉一半以上的圆圈，此解决方案就会中断 .

如果你只需要一个近似值，这可能是不值得的，因为它对实际的交叉点看起来有几个假设 .
回复于 2024-04-28T03:22:39+08:00
1

我的第一直觉是变换所有东西，使圆圈以原点为中心，将三角形转换为极坐标，并求解三角形与圆的交点（或包围） . 我实际上并没有在纸上完成它，但这只是一种预感 .

回复于 2024-04-28T03:22:39+08:00

计算圆和三角形的交点区域？

11 回答

如何查找多边形的区域

圆与多边形的交点区域

代码

相关问题