Check position and merge polygons with delphi

Question

On my application I have 2 or more polygons, a polygon can be inside or outside other (ALL inside or ALL outside). I must do this:

1. check if a polygon is inside (ALL inside without intersections) to other polygon;
2. if point 1 is true "merge the polygon";

To understand my "merge the polygon", please see the image:

As you can see there are 2 polygons: A-B-C-D-A and 1-2-3-1, I need find 2 points (one point for A-B-C-D-A and one point for 1-2-3-1) then connect with 2 lines, the new lines must not intersect the polygons lines.

Is there a theory about this kind of problem to find the best solution faster?

Answer 1

Polygon in side other polygon

Since your polygon is either all inside, or all outside, this can simply be reduced to testing whether one point the polygon is inside or outside the other polygon. That's a well known problem with a variety of solutions: Point in polygon

Merging polygons

There's no unique solution to your problem. The most obvious approach to me would be to find two corners, one corner from each polygon that are closer together than any other pair of corners.

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

There is a simple brute force method we use to find if any point in is a polygon.

Create a canvases, fill it with white and draw the polygon in blue. Now look at the pixel color of any point you are interested in to find out whether or not it is within the polygon.

If you want to know if one is entirely contained in another than create a second canvas and draw one on top of the other, both in blue and then compare them to see if they are the same.

Computationally this isn't the most efficient, but it is completely accurate.