求两个凸多边形的公切线
Find common tangents of two convex polygons
给定两个由一条线隔开的凸多边形P、Q，如何找到它们的公切线？
总共应该有4个。
几何不是我的强项，所以任何帮助将不胜感激:)
任何切线都将从（至少）每个多边形上的一个点生成。切线为每个多边形形成一个 half-space，包含整个多边形；通过要求每个多边形位于切线上方或下方生成不同的切线。
每当遇到涉及两个凸多边形的问题时，算法可能涉及“在每个凸多边形上选取一个点，然后迭代”。这个算法也不例外。
基本上，您所做的就是从随机猜测开始，然后进行完善。在每个多边形上选取一个顶点并计算通过这两个顶点的线。查看多边形 A，看看两个相邻顶点中的任何一个是否在线的错误一侧。如果是，则用该顶点替换当前顶点。然后对多边形 B 执行相同的检查。然后，如果您更新了任一顶点，请重复。最终，这些线将收敛到切线，每个顶点都是所需方向上的极值。
给定两个由一条线隔开的凸多边形P、Q，如何找到它们的公切线？ 总共应该有4个。
几何不是我的强项，所以任何帮助将不胜感激:)
任何切线都将从（至少）每个多边形上的一个点生成。切线为每个多边形形成一个 half-space，包含整个多边形；通过要求每个多边形位于切线上方或下方生成不同的切线。
每当遇到涉及两个凸多边形的问题时，算法可能涉及“在每个凸多边形上选取一个点，然后迭代”。这个算法也不例外。
基本上，您所做的就是从随机猜测开始，然后进行完善。在每个多边形上选取一个顶点并计算通过这两个顶点的线。查看多边形 A，看看两个相邻顶点中的任何一个是否在线的错误一侧。如果是，则用该顶点替换当前顶点。然后对多边形 B 执行相同的检查。然后，如果您更新了任一顶点，请重复。最终，这些线将收敛到切线，每个顶点都是所需方向上的极值。