在我的应用程序中，我有2个或更多的多边形，多边形可以在其他内部或外部（ALL内部或ALL外部）。我必须这样做：
要了解我的“合并多边形”，请看图像：
你可以看到有2个多边形：ABCDA和1-2-3-1，我需要找到2个点（ABCDA为1个点，1-2-3-1为1个点）然后连接2个线，新线不得与多边形线相交。
是否有关于此类问题的理论可以更快地找到最佳解决方案？
其他多边形的多边形
由于您的多边形全部在内部，或者全部在外部，因此可以简单地将其简化为测试多边形的一个点是在另一个多边形的内部还是外部。这是一个众所周知的问题，有各种解决方案：Point in polygon
合并多边形
您的问题没有独特的解决方案。对我来说最明显的方法是找到两个角，每个多边形的一个角落比任何其他角落更靠近。
要获得最佳性能，您应该在自己的数据上比较不同的算法。我比较了一些Point-In-Polygon算法，我发现Ray-Casting提供了最佳性能，here's是一个比较。你可以找到一个精心编写的Ray-Casting算法here实现。
这是快速而简单的部分，下一步你要合并两个多边形。如果多边形是凸的，你可以连接两个更接近的顶点，但是因为你说它们可能是凹的（或者甚至是在边缘有额外顶点的凸多边形），所以更近的角落将不起作用。例如：
您应该从每个多边形中选择一个顶点，使其连接线不与多边形的边相交。要找到两条线交叉点，您可以这样做：
function Zero(const Value: Double): Boolean;
const
Epsilon = 1E-10;
begin
Result := Abs(Value) < Epsilon;
end;
function IntersectLines(const X11, Y11, X12, Y12, X21, Y21, X22, Y22: Double;
out X, Y: Double): Boolean;
var
A1, B1, C1, A2, B2, C2, D: Double;
begin
A1 := Y12 - Y11;
B1 := X11 - X12;
C1 := A1 * X11 + B1 * Y11;
A2 := Y22 - Y21;
B2 := X21 - X22;
C2 := A2 * X21 + B2 * Y21;
D := A1 * B2 - A2 * B1;
if Zero(D) then
Result := False // Lines are parallel
else
begin
X = (B2 * C1 - B1 * C2) / D;
Y = (A1 * C2 - A2 * C1) / D;
end;
end;
但请注意，只是找到一个交叉点并不意味着选定的顶点不合适，因为我们正在处理一个线段，因此交点应位于该段内。要找到它，您可以检查该点是否在段的边界框内。例如，在该图中，1和2是选定的顶点，3是它们的交叉线与边缘的交点，但是3不在1和2的覆盖边界框内。
您应该注意到，每个选定顶点的交叉线将跨越边界框内每个多边形的至少两条边（在选定顶点上相交的边），因此边界框不应包含它的边界。
之后，您应该从其选定的顶点划分外部多边形，并在它们之间插入内部多边形的重定向顶点。
最后，我应该说：是的！关于所有这些的理论很多，但你应该找到自己的理论。正如你所说的那样，一个多边形在另一个中是ALL，这意味着它们是系统生成的，甚至是预定义的字符边界。然后，您可以更改所有讨论的算法，以便为您自己的案例获得更好的性能。
我们使用一种简单的强力方法来查找是否有任何点是多边形。
创建一个画布，用白色填充并用蓝色绘制多边形。现在查看您感兴趣的任何点的像素颜色，以确定它是否在多边形内。
如果你想知道一个是否完全包含在另一个画布中而不是创建第二个画布并在另一个画布上绘制一个，则都是蓝色，然后比较它们以查看它们是否相同。
在计算上，这不是最有效的，但它是完全准确的。