<p>解决这个问题主要有两种方法:</p>
<h2>一,。线性规划</h2>
<p>将问题表示为线性不等式组,并将其作为线性规划问题求解,如下所述:<a href="https://stackoverflow.com/questions/48966934/solve-a-system-of-linear-equations-and-linear-inequalities">Solve a system of linear equations and linear inequalities</a>。在您的情况下,不等式的形式为<code>(x - ox[i])*sin(a[i]) - (y - oy[i])*cos(a[i]) > 0</code>或<code>(x - ox[i])*sin(a[i]) - (y - oy[i])*cos(a[i]) < 0</code>,具体取决于您如何定义第i条线的角度<code>a[i]</code>,以及该线的哪一侧放置多边形<code>(ox[i], oy[i])</code>是第i个顶点的坐标。如果不等式严格与否,则取决于如何处理多边形与顶点或边接触的边界情况。这是一个很好的、易于推广的方法,但它可能很慢</p>
<h2>二,。交叉测试</h2>
<p>在一般情况下(没有顶点和边重合),有4种可能性:(1)一些边相交;(2) 多边形1在多边形2内;(3) 多边形2在多边形1内;(4) 多边形不相交。您需要测试前3个案例</p>
<p>对于案例1,您需要实现此处所述的线段相交测试<a href="https://stackoverflow.com/questions/3838329/how-can-i-check-if-two-segments-intersect">How can I check if two segments intersect?</a>,并尝试将多边形1的每条边与多边形2的每条边相交,这在您的案例中不是问题,因为最多会有<code>2*2 = 4</code>测试。如果检测到至少一个交叉口,则完成</p>
<p>对于情况2和3,需要测试多边形1的顶点是否在多边形2内,反之亦然。这可以使用<a href="https://stackoverflow.com/questions/3838329/how-can-i-check-if-two-segments-intersect">How can I check if two segments intersect?</a>中描述的相同测试<code>IsOnLeft</code>和<code>IsOnRight</code>来完成:如果一个点位于右线的左侧,而在左线的右侧,则该点位于内部</p>
<p>在任何情况下,都应该特别注意退化和边界情况:如果多边形的边重合,或者一个多边形的顶点位于另一个多边形的边上,或者不同多边形的边重合,该怎么办。根据您的特殊目的,您可能会以不同的方式检测和处理此类病例</p>