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);
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With