交叉三角形(一般是凸多边形)的问题比看起来更难,特别是如果你想在线性时间内相对于所涉及的边数求解它.
你可以考虑这个页面来了解一般凸多边形的工作算法(该算法基于旋转卡尺.实际上,背后有一些抽象几何,特别是几何Hanh-Banach定理).
考虑一旦你有交叉多边形,它是凸的,评估该区域是微不足道的.
因此,您有两种选择:
你保持问题抽象(不知何故你认为三角形是凸多边形,就是这样),C/C++中的快速解决方案可以通过GPC库(用C语言编写)实现,或者,例如,通过boost: :几何.
你专注于三角形:在这种情况下,我的建议是考虑这篇精彩的论文 ,它在拓扑上详细介绍了交叉的可能方式,并提供了解决方案的有效实现.
我还有一件事要说:当你考虑玩具三角形的问题时(即低偏度,尺寸大于机器精度),你仍然可以考虑实现自己的算法并使用它.但是,当你必须每秒交叉数百万个可能病态的三角形时,你最好依赖一个好的和快速的库.