计算科学 - 求多边形的面积。在 C 和 Obj C 中。 - 吾爱随笔录

求多边形的面积。在 C 和 Obj C 中。

计算科学计算几何 C

2021-12-28 05:36:54

我被分配了一个任务：

创建一个将计算随机多边形面积的控制台应用程序（使用 C 和 Obj C）。应用程序应将输入数据处理为 .txt 文件，其中包含以下格式的笛卡尔坐标对列表：

(12;34)
(23;35)
(85;23)
...

应该从这些对中形成一个多边形。多边形的边（线段）不应相交。如果他们这样做 - 返回一个错误。应用程序应该将多边形划分为三角形，计算它们的面积，求和，然后返回多边形的面积。输入处理器、三角形和求和运算——都应该作为一个单独的类来实现。该应用程序应支持命令“帮助”并返回有关如何使用该应用程序的信息。

到目前为止，我已经构建了以下算法。它缺少一些功能（我需要帮助）并且有几个程序错误。

我的问题是：

如何检查多边形的边（线段） - 不相交？每个线段都应检查到另一个。这种检查应该在算法的哪一点进行？
如果多边形有凹边，我从第一个点构建三角形的算法就会失败。解决方案是什么？（该应用程序也应该适用于凹面/复杂多边形）

该应用程序处理条目数据。形成 2 个 NSMutableArrays，一个用于 X，另一个用于 Y 坐标。
计算任何数组中的值的数量。如果小于 3 - 显示错误“输入至少 3 对以形成多边形”。
创建类“角落”。它的属性将是坐标 X 和 Y。此类的对象将是我们多边形的一个角。
创建一个for循环，该循环的重复次数应少于我们的 NSMutableArrays 之一中的值数。
在循环开始时，我们从“Corner”类创建一个对象。我们从 NSMutableArrays 坐标中取出并将其作为“角”对象的属性。这样，在循环周期结束时，我们将创建所有角/顶点。
每个创建Corner的我们都将添加到另一个数组中。
如果 for 循环已经进行了至少 3 个循环 - 我们已经有 3 个顶点，我们可以从中构建第一个三角形（从第 10 项将了解我们为什么关心三角形）
因此，我们创建了一个新类Triangle。我们给它属性："side1", "side2", "side3", "area".
回到我们的“for”循环。我们创建一个Triangle类的实例。
因为我们将计算最终多边形的面积，所以我们可以将它分割成三角形，计算它们的面积，然后将它们相加。我们将从第一个顶点绘制三角形：1v->2v->3v；1v->3v->4v；1v->4v->5v... 因为我们知道坐标点——我们可以计算点之间的长度。因此，我们知道三角形所有边的长度。要找到这种三角形的面积，我们可以使用 Heron 公式（更多信息请参见第 13 项）。为了计算点之间的长度，我们将在Triangle类中创建一个新方法：sideLengthWithVert:corner1 vert2:corner2 vert3:corner3. 该方法采用三角形的角/顶点 - “角”类的对象，然后使用公式：d=sqrt((x2-x1)^2+(y2-y1)^2) 一个接一个地计算角之间的长度。长度将分配给“三角形”对象的属性 -side1 side2 side3
（这里我的代码中有一个错误，我怀疑这是一个逻辑错误）因为这个方法需要corners作为参数 - 我们从我们之前创建的数组中创建这 3 个角corners。一个错误说：[__NSArrayM objectAtIndex:]:index 567 beyond bounds [0 .. 2] 索引 567 来自哪里 - 我不知道。在创建角度的方法中，我传递t了等于循环周期数的变量for。
我们使用新创建的方法：sideLengthWithVert:corner1 vert2:corner2 vert3:corner3并给它我们的角落。现在我们的对象Triangle具有side1 side2 side3等于角之间长度的属性。
现在我们有了一个完整的三角形，我们可以计算它的面积。为此，我们将在Triangle名为的类中编写一个新方法calcArea。在其中，我们使用 Heron 公式： p=(a+b+c)/2 然后 A=sqt(p(pa)(pb)(pc)) 计算后，我们将其赋予Triangle'sproperty area。
我们创建一个新的 NSMutableArray 并在其中添加将在大循环的每个循环中创建的三角形for。
最后要做的就是将最后一个数组内的三角形区域相加。为此，我们创建了一个条件“如果我们至少Triangle创建了一个对象 - 执行以下代码：（在下一项 16、17、18 内）”
计算数组内的三角形数量。创建一个循环，该循环将在数组内循环更少或相等数量的三角形。每一步加起来三角形的面积。
如果用户进入calc控制台 - 显示我们的计算结果。
如果用户进入help控制台 - 显示应用程序的使用示例。

1个回答

在检查输入数据形成一个有效的多边形后，您可以在不对多边形进行三角剖分的情况下计算面积。关键是要认识到面积公式可以通过格林定理（http://en.wikipedia.org/wiki/Green%27s_theorem）进行转换：

A = \int_{Ω} 1 d A = \oint_{\partial Ω} x d y = - \oint_{\partial Ω} y d x = \frac{1}{2} \oint_{\partial Ω} (- y d x + x d y)

$A = \int_\Omega 1\,dA = \oint_{\partial\Omega}x\,dy = -\oint_{\partial\Omega} y\,dx= \frac{1}{2}\oint_{\partial\Omega}\left(-y\,dx + x\,dy \right)$

由于您得到了边界的描述，因此很自然地在一组边上计算此线积分。由于您是在线性边上积分，因此已经为您正确地制定了这个积分，它被称为“鞋带公式”。Wikipedia 页面为此明确写出了公式，因此您可以选择最容易处理的版本。

http://en.wikipedia.org/wiki/Shoelace_formula

检查两条线段的交点可以有很多不同的方法，但一种概念上简单的方法是写每条线 n形式，计算两条线的交点，然后检查是否相交发生在两条线段的边界内。请注意正确处理完美的垂直/水平线，因为这可能是被零除的机会。 $y=mx + b$

编辑：三角测量法

抱歉，我没有看到您的问题中关于需要三角测量的部分。我想出了一种非常简单有效的方法来对非凸多边形的内部进行三角剖分。基本思想是，在迭代地制作三角形的同时，跟踪内部的非三角形边界多边形。

用伪代码编写的基本算法是这样的：

While(interiorPolygon.size() >= 3)

    [v1, v2, v3] = threeConsecutiveVertices in interiorPolygon
    if( isCCW(v1,v2,v3) )
       tris.add(v1,v2,v3)
       Drop v2 from interiorPolygon list
    end
end

该方法假定给定的顶点是围绕多边形边界逆时针排列的。这是必要的，因为我使用了 isCCW(v1,v2,v3) 函数，该函数确定 {v1,v2,v3} 是在多边形内部还是在多边形外部形成一个三角形。这可以通过计算 (v2-v1) 和 (v3-v1) 的叉积来实现。如果叉积为正，则顶点形成逆时针三角形，位于多边形内部。否则，由顶点形成的三角形位于interiorPolygon 边界之外。

我在 Matlab 中对其进行了编码，并且可以在不到 20 行代码中完成一个相当健壮的版本（我没有检查多边形的有效性）。我会让你充实代码中需要发生的细节和簿记。

其它你可能感兴趣的问题

上一篇梯度下降下一篇二维三次样条的自然样条条件