Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Function that returns intersection of two TShapes, including TPaths?

Anyone have any knowledge of a function that returns the intersection TPath for two TShapes? Especially one that returns the intersection TPath of two TPaths.

For instance:

pthIntersection := PathIntersection(Path1,Path2);

enter image description here

like image 257
Domus Avatar asked Jun 16 '15 12:06

Domus


1 Answers

There is no built-in function for this.
But what I think you are trying to do is this:

Given a polygon (aka TPath) made up for distinct points connected by lines.
Return all points in ShapeA that lay inside ShapeB.

Point intersection
This can be done using PointInObjectLocal.
Run a loop visiting all points in PathA and see if any lay inside PathB.

Line intersection
If you want to know all vertices that overlap you'll first have to Flatten (a copy) of both TPaths and then run a line intersect algorithm for all lines in both shapes.
This converts all curves to lines.

Here's a routine to do just that:
From: http://www.partow.net/projects/fastgeo/index.html

function Intersect(const x1, y1, x2, y2, x3, y3, x4, y4: TFloat; out ix, iy: TFloat): boolean;
var
  UpperX, UpperY, LowerX, LowerY: TFloat;
  Ax, Bx, Cx, Ay, By, Cy: TFloat;
  D, F, E, Ratio: TFloat;
begin
  Result:= false;

  Ax:= x2 - x1;
  Bx:= x3 - x4;

  if Ax < Zero then begin
    LowerX:= x2;
    UpperX:= x1;
  end else begin
    UpperX:= x2;
    LowerX:= x1;
  end;

  if Bx > Zero then begin
    if (UpperX < x4) or (x3 < LowerX) then Exit;
  end else if (UpperX < x3) or (x4 < LowerX) then Exit;

  Ay:= y2 - y1;
  By:= y3 - y4;

  if Ay < Zero then begin
    LowerY:= y2;
    UpperY:= y1;
  end else begin
    UpperY:= y2;
    LowerY:= y1;
  end;

  if By > Zero then begin
    if (UpperY < y4) or (y3 < LowerY) then Exit;
  end else if (UpperY < y3) or (y4 < LowerY) then Exit;

  Cx:= x1 - x3;
  Cy:= y1 - y3;
  D:= (By * Cx) - (Bx * Cy);
  F:= (Ay * Bx) - (Ax * By);

  if F > Zero then begin
    if (D < Zero) or (D > F) then Exit;
  end else if (D > Zero) or (D < F) then Exit;

  E:= (Ax * Cy) - (Ay * Cx);

  if F > Zero then begin
    if (E < Zero) or (E > F) then Exit;
  end else if (E > Zero) or (E < F) then Exit;

  Result:= true;

  Ratio:= (Ax * -By) - (Ay * -Bx);

  if NotEqual(Ratio, Zero) then begin
    Ratio:= ((Cy * -Bx) - (Cx * -By)) / Ratio;
    ix:= x1 + (Ratio * Ax);
    iy:= y1 + (Ratio * Ay);
  end else begin
    //if Collinear(x1,y1,x2,y2,x3,y3) then
    if IsEqual((Ax * -Cy), ( -Cx * Ay)) then begin
      ix:= x3;
      iy:= y3;
    end else begin
      ix:= x4;
      iy:= y4;
    end;
  end;
end;

function Intersect(const Segment1,Segment2:TSegment2D; out ix, iy : TFloat):Boolean;
begin
  Result := Intersect(Segment1[1].x,Segment1[1].y,Segment1[2].x,Segment1[2].y,Segment2[1].x,Segment2[1].y,Segment2[2].x,Segment2[2].y,ix,iy);
end;

Just convert the TFloat x,y pairs to TPointF and you're in business. The cool thing about the routine is that it also tells you the exact point at which the lines overlap.

If you follow the lines, until two lines overlap and from there on start tracking both overlapping lines and PointInShape you can construct an exact image of the overlap of the two shapes.

Making it faster
If the flattening and the corresponding increase in the number of line segments make your code too slow you can keep the curves and see if a line/curve intersects another curve.
For this you can convert the curves into bezier curves and use De_Casteljau's algorithm

More info
See also this question and the link to Delphi source code in its first or second answer.

like image 55
Johan Avatar answered Oct 25 '22 02:10

Johan