c++ - 相交三角形的面积

Question

很难说出这里问的是什么。这个问题是含糊的、模糊的、不完整的、过于宽泛的或修辞性的，无法以目前的形式得到合理的回答。如需帮助澄清此问题以便重新打开它， visit the help center 。

已关闭 10 年前。

我想解决一个问题，但是有点难，我需要一些帮助。问题是:

we have 2 triangles, and we have the coordinates of the vertices like (x1, y1), (x2, y2), (x3, y3), (a1, b1), (a2, b2), (a3, b3). We want to measure the area that two triangles are on each other. It may be 0 or more.

例如，如果我们有第一个三角形 (0,0) (3,0) (0,3) 和第二个三角形 (0,0) (3,3) (3,0)，则公共(public)区域将为 2.25。

我应该如何编写程序来解决这个问题？

Answer 1

相交三角形(以及一般的凸多边形)问题比看起来困难得多，特别是如果你想在线性时间内解决它关于涉及的边数。

您可以考虑this page了解一般凸多边形的工作算法(该算法基于 rotating calipers 。实际上，背后有一些抽象几何图形，特别是 geometric Hanh-Banach theorem )。

考虑一下，一旦有了凸交集多边形，就可以评估 area是微不足道的。

<小时/>

因此，您有两个选择:

1. 您保持问题抽象(不知何故，您将三角形视为凸多边形，仅此而已)，并且可以通过 GPC library 实现 C/C++ 中的快速解决方案。 (用 C 编写)或者，例如，通过 boost::geometry .

2. 您只专注于三角形:在这种情况下，我的建议是考虑这个 wonderful paper 从拓扑上详细介绍了所涉及的可能的相交方式，并给出了解决方案的有效实现。

我还有一件事要说:当您考虑玩具三角形的问题时(即低偏度，尺寸远大于机器精度)，您仍然可以考虑实现自己的算法并使用它。但是，当您必须每秒相交数百万个可能病态三角形时，您最好依赖一个良好且快速的库。