我想解决一个问题，但这有点难，我需要一些帮助。问题是：
我们有 2 个三角形，我们有顶点的坐标，例如 (x1, y1), (x2, y2), (x3, y3), (a1, b1), (a2, b2), (a3, b3)。我们想测量两个三角形相互重叠的面积。它可以是 0 或更多。
例如，如果我们有第一个三角形 (0,0) (3,0) (0,3) 和第二个 (0,0) (3,3) (3,0)，则公共面积将为 2.25。
我应该如何编写一个程序来解决这个问题？
问问题
2672 次
1 回答
6
相交三角形（以及一般的凸多边形）的问题比看起来要困难得多，特别是如果你想在线性时间内解决它涉及的边数。
您可以考虑这个页面来了解一般凸多边形的工作算法（该算法基于旋转卡尺。确实，背后有一些抽象几何，特别是几何 Hanh-Banach 定理）。
考虑一下，一旦有了凸面的交叉多边形，评估该区域就变得微不足道了。
因此，您有两个选择：
您将问题保持抽象（不知何故，您将三角形视为凸多边形，仅此而已），并且可以通过GPC 库（用 C 编写）或例如通过boost 来实现 C/C++ 中的快速解决方案： : 几何。
您只专注于三角形：在这种情况下，我的建议是考虑这篇精彩的论文 ，它在拓扑上详细说明了所涉及的相交的可能方式，并给出了解决方案的有效实现。
我还有一件事要说：当您考虑玩具三角形的问题（即低偏度，尺寸远大于机器精度）时，您仍然可以考虑实现自己的算法并使用它。但是，当您必须每秒与数百万个可能病态的三角形相交时，您最好依靠一个良好且快速的库。
于 2012-10-26T16:10:29.017 回答