线性规划 - 算法
Linear Programming - Algorithms
给定平面中的两组 P1, P2 个点。
解：如果有一条线把P1和P2的点分开，一条线认为P1的所有点都在一侧，所有的点都在一侧P2在另一边，return'There is such line'，否则return'There is no such line'.
示例：考虑这些点：5 = (−2,1) ,4 = (6,2) ,3 = (2, −2) ,2 = (1,5) ,1 = (−2 , −1).
P1 = {1,2} and P1 = {3,4} ---> 例如 return 'There is such line' y = 2x-3。
而 P1 = {1,2} and P1 = {3,4,5} ---> return 'There is no such line'.
有没有不使用凸包的基于线性设计的算法来解决这个问题？我很乐意提出建议！
一种解决方案是分别设计P1和P2的两个凸包。您可以使用 Wikipedia 中列出的算法之一。 Graham 扫描实现起来非常简单，并且具有 O(nlogn) 时间复杂度。
然后检查这两个多边形是否重叠。为此，您可以采取以下步骤：
- 对于第一个凸包上的每个顶点，检查它是否完全在第二个凸包内。这意味着检查顶点是否位于另一个凸包的每个（有向）边的同一侧。如果至少一个顶点是这样，则多边形重叠。我们可以到此为止了。
- 做同样的事情，但现在使用第二个凸包的每个顶点。
如果这些步骤中的 none 给出了它们重叠的结论，那么它们就不会重叠。
第 1 步：为点集 p1 创建凸包。检查集合 P2 的任何点是否在点 P1 的凸包内。
第 2 步：为点集 p2 创建凸包。检查集合 P1 的任何点是否在点 P2 的凸包内。
如果在任一步骤中，一个点位于多边形内，'There is no such line'。否则，'There is such line'.
您必须完成这两个步骤。不能只为 P1 创建一个凸包并检查 P2 中的点是否在 P1 的凸包内，反之亦然。如上图示例所示，您不能只为红色点设置一个凸包，然后检查黄色点是否在该凸包内。
凸包的时间复杂度：O(nlogn)。
参考文献：
- Convex hull algorithms
- Check if a point lies inside the convex hull.
- Another resource for Check if a point lies inside the convex hull
您还可以在 stack overflow and computer science stack exchange 上找到一些有趣的方法。这些提到了一些不使用凸包方法的方法。
当且仅当有一条线将它们的凸包分开时，确实有一条线将两组点分开，但是您不需要完成生成包和相交的所有工作多边形来解决这个问题。
首先，检查点集是否在它们的 x 坐标上重叠，即如果 min_x(P1) <= max_x(p2) 和 max_x(p1) >= min_x(p2)
如果它们在 x 坐标上不重叠，则有一条垂直线将它们分开，您就完成了。否则...
使用单调链算法求出P1的上下壳和P2的上下壳：https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain
如果P1和P2之间有一条线，那么在x坐标重叠的区域，要么P1的下壳完全在P2的上壳之上，要么相反。您可以通过按 x 坐标顺序处理上下船体上的点来检查这一点。
这个算法确实使用了单调链的方法，是用来生成凸包，但是避免了一般的多边形求交和在 O(N log N) 时间内很容易实现。
给定平面中的两组 P1, P2 个点。
解：如果有一条线把P1和P2的点分开，一条线认为P1的所有点都在一侧，所有的点都在一侧P2在另一边，return'There is such line'，否则return'There is no such line'.
示例：考虑这些点：5 = (−2,1) ,4 = (6,2) ,3 = (2, −2) ,2 = (1,5) ,1 = (−2 , −1).
P1 = {1,2} and P1 = {3,4} ---> 例如 return 'There is such line' y = 2x-3。
而 P1 = {1,2} and P1 = {3,4,5} ---> return 'There is no such line'.
有没有不使用凸包的基于线性设计的算法来解决这个问题？我很乐意提出建议！
一种解决方案是分别设计P1和P2的两个凸包。您可以使用 Wikipedia 中列出的算法之一。 Graham 扫描实现起来非常简单，并且具有 O(nlogn) 时间复杂度。
然后检查这两个多边形是否重叠。为此，您可以采取以下步骤：
- 对于第一个凸包上的每个顶点，检查它是否完全在第二个凸包内。这意味着检查顶点是否位于另一个凸包的每个（有向）边的同一侧。如果至少一个顶点是这样，则多边形重叠。我们可以到此为止了。
- 做同样的事情，但现在使用第二个凸包的每个顶点。
如果这些步骤中的 none 给出了它们重叠的结论，那么它们就不会重叠。
第 1 步：为点集 p1 创建凸包。检查集合 P2 的任何点是否在点 P1 的凸包内。
第 2 步：为点集 p2 创建凸包。检查集合 P1 的任何点是否在点 P2 的凸包内。
如果在任一步骤中，一个点位于多边形内，'There is no such line'。否则，'There is such line'.
您必须完成这两个步骤。不能只为 P1 创建一个凸包并检查 P2 中的点是否在 P1 的凸包内，反之亦然。如上图示例所示，您不能只为红色点设置一个凸包，然后检查黄色点是否在该凸包内。
凸包的时间复杂度：O(nlogn)。
参考文献：
- Convex hull algorithms
- Check if a point lies inside the convex hull.
- Another resource for Check if a point lies inside the convex hull
您还可以在 stack overflow and computer science stack exchange 上找到一些有趣的方法。这些提到了一些不使用凸包方法的方法。
当且仅当有一条线将它们的凸包分开时，确实有一条线将两组点分开，但是您不需要完成生成包和相交的所有工作多边形来解决这个问题。
首先，检查点集是否在它们的 x 坐标上重叠，即如果 min_x(P1) <= max_x(p2) 和 max_x(p1) >= min_x(p2)
如果它们在 x 坐标上不重叠，则有一条垂直线将它们分开，您就完成了。否则...
使用单调链算法求出P1的上下壳和P2的上下壳：https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain
如果P1和P2之间有一条线，那么在x坐标重叠的区域，要么P1的下壳完全在P2的上壳之上，要么相反。您可以通过按 x 坐标顺序处理上下船体上的点来检查这一点。
这个算法确实使用了单调链的方法，是用来生成凸包，但是避免了一般的多边形求交和在 O(N log N) 时间内很容易实现。