检查位置并使用delphi合并多边形

geometry polygons

609 观看

3回复

556 作者的声誉

在我的应用程序中,我有2个或更多的多边形,多边形可以在其他内部或外部(ALL内部或ALL外部)。我必须这样做:

  1. 检查多边形是否在其他多边形内部(所有内部没有交叉点);
  2. 如果第1点为真,则“合并多边形”;

要了解我的“合并多边形”,请看图像:

在此输入图像描述

你可以看到有2个多边形:ABCDA和1-2-3-1,我需要找到2个点(ABCDA一个点,1-2-3-1一个点)然后连接2个线,新线不得与多边形线相交。

是否有关于此类问题的理论可以更快地找到最佳解决方案?

作者: Martin 的来源 发布者: 2013 年 2 月 22 日

回应 (3)


1

519468 作者的声誉

其他多边形的多边形

由于您的多边形全部在内部,或者全部在外部,因此可以简单地将其简化为测试多边形的一个点是在另一个多边形的内部还是外部。这是一个众所周知的问题,有各种解决方案:点多边形

合并多边形

您的问题没有独特的解决方案。对我来说最明显的方法是找到两个角,每个多边形的一个角落比任何其他角落更靠近。

作者: David Heffernan 发布者: 22.02.2013 11:54

0

1271 作者的声誉

要获得最佳性能,您应该在自己的数据上比较不同的算法。我比较了一些Point-In-Polygon算法,我发现Ray-Casting提供了最佳性能,这是一个比较。您可以在此处找到精心编写的Ray-Casting算法实现。

这是快速而简单的部分,下一步你要合并两个多边形。如果多边形是凸的,你可以连接两个更接近的顶点,但是因为你说它们可能是凹的(或者甚至是在边缘有额外顶点的凸多边形),所以更近的角落将不起作用。例如: 在此输入图像描述

您应该从每个多边形中选择一个顶点,使其连接线不与多边形的边相交。要找到两条线交叉点,您可以这样做:

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,这意味着它们是系统生成的,甚至是预定义的字符边界。然后,您可以更改所有讨论的算法,以便为您自己的案例获得更好的性能。

作者: saastn 发布者: 22.02.2013 11:36

0

1 作者的声誉

我们使用一种简单的强力方法来查找是否有任何点是多边形。

创建一个画布,用白色填充并用蓝色绘制多边形。现在查看您感兴趣的任何点的像素颜色,以确定它是否在多边形内。

如果你想知道一个是否完全包含在另一个画布中而不是创建第二个画布并在另一个画布上绘制一个,则都是蓝色,然后比较它们以查看它们是否相同。

在计算上,这不是最有效的,但它是完全准确的。

作者: Byte Player 发布者: 26.02.2019 02:06
32x32