计算区域之间的交圈子和一个三角形的?
-
22-08-2019 - |
题
一个人如何计算区域之间的交一个三角(指定为三(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)
{
...
}
解决方案
如果你想要一个确切的解决方案(或至少作为确切作为你可以得到使用浮点运算),那么这将涉及大量的工作,因为有这么多的情况下加以考虑。
我数九种不同的情况(分为下图数的顶点的三角形内的圈子和数边三角形的那个交叉的或包含在圆):
(但是,这种列举的几何情况下,是众所周知的是棘手的,我不会吃惊如果我错过了一个或两个!)
这样的做法是:
确定每个顶点的三角形,如果它的圈子里面。我会假设你知道如何做到这一点。
确定对每个三角形边缘如果它相交圈子。(我写了一个方法 在这里,, 或看到任何计算的几何形状的书。) 你需要计算点或交叉点(如果有的话)的使用在第4步。
确定的九个案件。
计算区域的交叉路口。案件1、2和9容易。在剩下的六个案件我已经绘的虚线显示如何分区域的交点为三角形, 圆段 在原有基础上顶点的三角形,并在交叉点你计算中的步骤2。
这个算法将是相当微妙的和容易出现错误,影响只有一个案件,所以确保你已经试验的情况下,涵盖所有九起案件(并且我建议permuting的顶点测试的三角形太)。特别注意的案件中的哪一个三角形的顶点是在边缘。
如果你不需要一个确切的解决方案,然后光栅化的数字和计算素的交叉点(建议通过一些其他的受访者)似乎是一个很容易的方法编码,并相应地较不容易产生错误。
其他提示
首先,我要提醒我们如何找到一个多边形的面积。一旦我们做到了这一点,该算法找到一个多边形和一个圆的交点应该很容易理解了。
如何找到一个多边形的面积
让我们来看一个三角形的情况下,因为所有的基本逻辑在那里出现。假设我们有一个顶点(X1,Y1),(X2,Y2)和(X3,Y3),当您去三角逆时针绕,如图下图三角形:
然后,可以由式计算面积
A =(X1 Y2 + Y3 X2 X3 + Y1 - x2y1- X3 Y2 - X1Y3)。/ 2
要看到为什么这个公式工作,让我们来重新安排它,以便它在形式
A =(X1 Y2 - X2 Y1)/ 2 +(X2 Y3 - X3 Y2)/ 2 +(X3 Y1 - X1Y3)/ 2
现在的第一项是以下区域,这是在我们的情况下积极:
如果它是不明确的是,绿色区域的面积是确实(X1 Y2 - X2 Y1)/ 2,则读取此。
第二项是这个区域,这是再一次阳性:
和所述第三区域中,如下图所示。此时的面积为负
添加这三种了,我们得到如下图
我们看到,这是三角形外的绿地面积由红色区域抵消,使得净面积是三角形的只是面积,这说明了为什么我们的配方是在这种情况下正确的。
我上面说什么是直观的解释为什么该地区式是正确的。更严格的解释是观察到,当我们从一个边缘计算面积,我们得到的面积是我们从整合R 12dθ/ 2得到相同的区域,所以我们有效整合R 22dθ/ 2的边界附近多边形的,并且通过斯托克斯定理,这给出了同样的结果作为积分rdrdθ在区域界定的多边形。由于整合rdrdθ在由多边形包围的区域给区域,我们认为我们的程序必须正确地给区域。
用多边形的圆的交点的区
现在让我们来讨论如何找到半径为R的圆的以多边形为显示在下面的图中的交叉点的区域中:
我们感兴趣的是找到绿色区域的面积。我们可能,就如同在单个多边形的情况下,打破我们计算为寻找的区域为多边形的每一侧,然后添加那些区域向上。
我们的第一区域的样子:
在第二区域的样子
和第三区域将是
再次前两个区域是在我们的情况下积极而第三个将是负的。希望的取消将制定使净面积确实是我们感兴趣的领域。让我们来看看。
事实上的面积之和将是区域我们感兴趣的是
同样,我们可以给的,为什么这个作品更严格的解释。让我是通过交叉点定义的区域,让P为多边形。然后从前面的讨论,我们知道我们想要电脑r的积分^2dθ/2一的边界附近。然而,要做到这一点很难,因为它需要找到交集。
相反,我们做了多边形组成。我们综合MAX(R,R)^ 2Dθ/ 2多边形的边界上。为了说明为什么这给出了正确的答案,让我们定义一个函数π这需要一个点,极坐标(r,θ)至点(MAX(R,R),θ)。它不应该是令人困惑指π(R)= MAX(R,R)和π(θ)=θ的坐标的功能。那么我们所做的就是π(R)^ 2Dθ/ 2整合多边形的边界上。
在另一方面,因为π(θ)=θ,这是相同的积分π(R)^ 2dπ(θ)/ 2多边形的边界上。
现在做变量的变化,我们发现,我们会得到相同的答案,如果我们整合R ^ 2Dθ/ 2π的边界(P),其中π(P)是下πP的图像了。
使用斯托克斯定理再次,我们知道的π(P)的边界上集成R ^ 2Dθ/ 2给我们的π(P)的区域。换句话说,它给出了相同的答案超过π(P)积分DXDY。
使用变量的变化再次,我们知道,积分DXDY超过π(P)是一样的过P,其中J是π的雅可比积分Jdxdy。
现在我们可以将积分Jdxdy的分成两个区域:在圆圈中的部分和外循环的部分。现在π离开点在圆圈单独所以J = 1出现,所以从P的这部分的贡献P的部分的那在于圈即,交叉点的区域的区域。第二区域是外循环的区域。有J = 0,因为π折叠这部分下降到圆的边界。
因此我们计算确实的相交的区域中。
现在,我们是比较肯定我们从概念上如何找到该地区知道,让我们更具体说说如何计算从一个单段的贡献。让我们在我所说的“标准几何体”看着段开始。它如下所示。
在标准几何形状,边缘水平变为从左到右。它是由三个数字描述:XI,x坐标,其中所述边缘开始,XF,x坐标,其中所述边缘终止,和y中,y的边缘的坐标。
现在我们可以看到,如果| Y | 区域2的区域是三角形的刚刚的区域。但是,我们必须小心的迹象。我们希望显示的区域是积极的,所以我们会说面积 - (XINT - (-Xint))。Y / 2 要记住的另一件事是,在一般情况下,喜不必小于-Xint和XF没有比XINT更大。 在其他情况下,要考虑的是| Y | > R.这种情况更简单,因为仅存在一个片,其是在图中相似的区域1。 现在,我们知道如何从标准几何体边缘计算领域,唯一剩下要做的就是介绍如何将任何边缘成标准的几何图形。 但是,这只是坐标的简单变化。给出一些与初始顶点vi和最终顶点VF,新的x单位矢量将指向vi到VF的单位向量。然后xi是刚刚从点缀入x中的圆的中心VI的位移,和XF只是XI加vi和VF之间的距离。同时y由X与来自圆的中心VI的位移的楔积给出。 这完成了该算法的描述,现在是时候写一些代码。我将使用Java。 首先,因为我们用圆圈工作,我们应该有一个圆类 有关的多边形,我将使用Java的 现在的实际工作。我将分离出通过边缘迭代,把边缘在标准几何等,从一旦做到这一点计算的区域的逻辑的逻辑。这样做的原因是,你可能会在将来要计算别的东西,除了或者除了该地区,并要能够重用不必处理,通过边缘迭代的代码。 所以,我有一个通用类,其计算类 它有三个静态方法,只是帮助计算几何: 有两个实例字段,这正好保持圆的副本的 接下来是方法计算就是我们要计算: 和 让我们在第二个快速 接着我声明,将跟踪顶点的 从下一行的 大多数这种方法的代码的其余部分是为了通过顶点以迭代相关无趣逻辑。重要的是,每while循环迭代一次我打电话 让我们来看看 在该方法中予实现如上所述转化的边缘成标准几何形状的步骤。首先,我计算 接下来,我计算位移的长度,因为这是必要的,以获得x单位矢量。一旦我有这个信息,我计算从圆到初始顶点的中心的位移。这与 现在,我已经改变了问题转化为标准的几何形状,这将是容易对付的。这是 在第一 如果相交是可能的,我计算X相交, 要处理区1,我是否 我做类似的事情来处理区3。 有关区域2,我必须做一些逻辑检查 现在让我们来看看代码 我简单地使用 现在让我们看一下延伸类, } 它有一个字段 现在的整洁的事情是,如果我们想跟踪周边的我们没有做更多的工作。我所定义的类 现在我们只需要再次扩展我们的抽象类使用 我们有一个变量 有关参考这里是 无论如何,这是我的算法的描述。我认为这是很好的,因为它是准确,有没有真正许多情况下进行检查。代码
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;
}
}
Shape
类。 Shape
s有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
,这使平方半径的副本。这似乎很奇怪,但我现在用的是类实际上是有能力找到圆圈多边形交集的整个集合的区域。这就是为什么我指的圆作为“当前”。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[]
s。我必须记住的第一个顶点,因为只有PathIterator
给我的每个顶点一次,所以我要回去它给了我最后一个顶点之后,并与该最后一个顶点和第一个顶点的边缘。 currentSegment
方法把下一个顶点在其参数。它返回,告诉你当它是从顶点的代码。这就是为什么我而循环的控制表达式是什么了。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轴eometry。我做早日恢复,如果该位移是零。segmentDisplacement
点积给我leftX
这是我一直在呼吁喜。然后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
大,没有交集的可能,然后我打电话给处理这种情况的方法。否则,我处理的情况下交叉点是可能的。intersectionX
的坐标,并且我划分边缘成三个部分,它们对应于区域1,2,和上述标准几何图的3。第一予处理区域1 leftX
确实比-intersectionX
少,否则如果有一个区域1就没有区域1,然后我需要知道何时结束。它结束在最小rightX
和-intersectionX
的。之后,我发现这些x坐标,我对付这种非交叉区域。 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;
}
我差不多一年半晚,但我想,也许人们会感兴趣的此代码的,我写了我认为正确的做到这一点。看在接近底部的功能IntersectionArea。的一般方法是摘下由圆外切的凸多边形,然后与小圆形帽处理。
假设你正在谈论整数像素,不是真实的,天真的实施将遍历三角形的每个像素,并从圆的针对其半径中心检查的距离。
这不是一个可爱的公式,或特别快,但它确实把工作做好。
尝试计算几何
请注意:这不是一个简单的问题,我希望这不是功课; - )
如果您在您的处置有一个GPU,你可以使用的用于获得交叉点的像素计数此技术..
由于您的形状是凸状,则可以使用蒙特卡洛区域估计。
绘制围绕圆形和三角形的盒子。
选择框随机点和保持多少下降的计数在圈内,以及有多少落于圆形和三角形两者。
圆的交点≅区的面积*在圆和三角形#点/在圆#点
停止选择点时所估计的区域不被超过一定量更超过一定的轮数的变化,或只选择基于所述盒的区中的固定数量的点。该地区估计应该收敛非常快,除非你的形状之一具有非常小的区域。
请注意:这里是你如何确定一个点是在一个三角形:重心坐标
如何准确你需要呢?如果你可以近似用简单的形状圆,可以简化问题。这不会是难以建模的圆作为一组在中心会议非常窄的三角形的,例如
如果只是三角形的线段中的一个相交的圆,纯数学解决方案不是太硬。一旦知道当交叉点的两个点是,可以使用距离公式找到的弦长。
根据这些方程的:
ϑ = 2 sin⁻¹(0.5 c / r)
A = 0.5 r² (ϑ - sin(ϑ))
其中,c是弦长,r是半径,θ成为通过该中心的角度,而A是面积。请注意,如果超过一半的圆被切断此溶液断裂。
这可能是不值得的努力,如果你只需要一个近似值,因为它使什么实际的交集看起来像几个假设。
我的第一本能会转化一切,使得圆的中心在原点,反式的三角,极坐标,并求解与圆的三角形的交点(或encompassment)。我没有实际工作是通过在纸上尚未虽然如此,这只是一种预感。