确定两个多边形是否相交的算法。
假设：多边形是凸的。（这些适用于凸多边形。）您可以查看此链接以获取更多信息。
为了能够确定两个凸多边形是否相交（相互接触），我们可以使用分离轴定理。本质上：
- 如果两个凸多边形不相交，则它们之间存在一条线。
- 只有当多边形之一的一侧形成这样一条线时，才存在这样一条线。
第一个说法很简单。由于多边形都是凸面，除非它们相交，否则您将能够在一侧绘制一条线，另一侧绘制另一条多边形。第二个不太直观。请看图 1。除非多边形的最近边彼此平行，否则它们彼此最靠近的点就是一个多边形的角与另一个多边形的边最接近的点。这一边将在多边形之间形成一个分离轴。如果边平行，则它们都是分离轴。
那么这具体如何帮助我们判断多边形A和B是否相交呢？好吧，我们只是检查每个多边形的每一边并检查它是否形成分离轴。为此，我们将使用一些基本的矢量数学将两个多边形的所有点压缩到一条垂直于潜在分离线的线上（见图 2）。现在整个问题都是一维的。我们可以确定每个多边形的点所在的区域，如果这些区域不重叠，这条线就是一个分离轴。
如果在检查两个多边形的每条线后，没有找到分离轴，则证明多边形相交，必须对其采取措施。
注意：这个问题很好地描述了这部分。我从这个问题中使用了这部分
公共区域覆盖的区域（大约）如果重叠
该算法的工作方式很简单
该算法从
all vertices主题多边形中的输入列表开始。接下来，裁剪多边形的一侧在两个方向上无限延伸，并遍历主题多边形的路径。如果来自输入列表的顶点位于扩展裁剪多边形线的可见侧，则将它们插入到输出列表中，并且将新顶点添加到主题多边形路径与扩展裁剪多边形线相交的输出列表中。
有关更多详细信息，请访问此链接
凸多边形的面积
坐标(x1, y1), (x2, y2), (x3, y3), 。. . ,(xn, yn)的凸多边形排列在“行列式”下方。坐标必须以逆时针顺序围绕多边形，在同一点开始和结束。
| x1 y1 |
| x2 y2 |
| x3 y3 |
Area= (1/2)* | .. .. |
| .. .. |
| xn yn |
| x1 y1 |
= (1/2)[(x1*y2+x2*y3+...xn*y1)- (y1*x2+y2*x3+...+yn*x1)]
这些是您必须执行的步骤才能解决问题。希望能帮助到你。