geometry - 用delphi检查位置和合并多边形

Question

在我的应用程序中，我有 2 个或更多多边形，一个多边形可以在其他的内部或外部（全部在内部或全部在外部）。我必须这样做：

1. 检查一个多边形是否在其他多边形的内部（所有内部没有交叉点）；
2. 如果点 1 为真“合并多边形”；

要了解我的“合并多边形”，请看图片：

如您所见，有 2 个多边形：ABCDA 和 1-2-3-1，我需要找到 2 个点（ABCDA 一个点，1-2-3-1 一个点）然后连接 2 条线，新线不得与多边形线相交。

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

Answer 1

其他多边形中的多边形

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

合并多边形

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

Answer 2

To approach best performance you should compare different algorithms on your own data. I've compared some of Point-In-Polygon algorithms and I found that Ray-Casting provides best performance, here's a comparsion. You can find a well-written implementation of Ray-Casting algorithm here.

That was fast and simple part, on next step you want to merge two polygons. If polygons were convex you could connect two vertices which were closer, but since you say that they may be concave (or even convex polygons with extra vertices on their edges) the closer corners won’t work. For example:

You should select one vertex from each polygon that their connecting line doesn't intersect none of polygons' edges. To find two lines intersection you can do this:

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;

But notice that just finding an intersection doesn't mean that selected vertices are not proper, because we're working with a line segment, so the intersection should be inside the segment. To find that out you can check if the point is inside the bounding box of segment. For example in this illustration 1 and 2 are selected vertices and 3 is the intersection point of their crossing line with an edge, but 3 is not inside the covering bounding box of 1 and 2.

You should notice that crossing line of each selected couple of vertices will cross at least two edges of each polygon inside the bounding box (edges that meet on selected vertices), so bounding-box shouldn't embrace it's boundaries.

After that you should divide the outer polygon from it's selected vertex and insert redirected vertices of inner polygon between them.

As a final word I should say: Yes! There're lots of theories about all of these, but you should find your own ones. As you said that one polygon is ALL inside the other, it means that they are generated systematically or even predefined like character boundaries. Then you may be able to change all discussed algorithms to reach a better performance for your own case.

Answer 3

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

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

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

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