mirror of
https://github.com/doublecmd/doublecmd.git
synced 2026-06-21 09:58:13 +00:00
133 lines
4.1 KiB
ObjectPascal
133 lines
4.1 KiB
ObjectPascal
unit Clipper.Minkowski;
|
|
|
|
(*******************************************************************************
|
|
* Author : Angus Johnson *
|
|
* Date : 21 December 2023 *
|
|
* Copyright : Angus Johnson 2010-2022 *
|
|
* Purpose : Minkowski Addition and Difference *
|
|
* License : http://www.boost.org/LICENSE_1_0.txt *
|
|
*******************************************************************************)
|
|
|
|
{$I Clipper.inc}
|
|
|
|
interface
|
|
|
|
uses
|
|
Classes, Math, Clipper.Core;
|
|
|
|
function MinkowskiSum(const Pattern, Path: TPath64;
|
|
PathIsClosed: Boolean): TPaths64; overload;
|
|
function MinkowskiSum(const Pattern, Path: TPathD;
|
|
PathIsClosed: Boolean; decimalPlaces: integer = 2): TPathsD; overload;
|
|
function MinkowskiDiff(const path1, path2: TPath64): TPaths64; overload;
|
|
function MinkowskiDiff(const Pattern, Path: TPathD;
|
|
PathIsClosed: Boolean; decimalPlaces: integer): TPathsD; overload;
|
|
|
|
implementation
|
|
|
|
uses
|
|
Clipper;
|
|
|
|
function AddPoints(val1, val2: TPoint64): TPoint64;
|
|
{$IFDEF INLINING} inline; {$ENDIF}
|
|
begin
|
|
Result.X := val1.X + val2.X;
|
|
Result.Y := val1.Y + val2.Y;
|
|
end;
|
|
//------------------------------------------------------------------------------
|
|
|
|
function SubtractPoints(val1, val2: TPoint64): TPoint64;
|
|
{$IFDEF INLINING} inline; {$ENDIF}
|
|
begin
|
|
Result.X := val1.X - val2.X;
|
|
Result.Y := val1.Y - val2.Y;
|
|
end;
|
|
//------------------------------------------------------------------------------
|
|
|
|
function Minkowski(const Base, Path: TPath64;
|
|
IsSum: Boolean; IsClosed: Boolean): TPaths64;
|
|
var
|
|
i,j,k,g,h, delta, baseLen, pathLen: integer;
|
|
tmp: TPaths64;
|
|
quad: TPath64;
|
|
begin
|
|
delta := Iif(IsClosed, 0 , 1);
|
|
baseLen := Length(Base);
|
|
pathLen := Length(Path);
|
|
setLength(tmp, pathLen);
|
|
|
|
for i := 0 to pathLen -1 do
|
|
begin
|
|
setLength(tmp[i], baseLen);
|
|
if IsSum then
|
|
for j := 0 to baseLen -1 do
|
|
tmp[i][j] := AddPoints(Path[i], Base[j])
|
|
else
|
|
for j := 0 to baseLen -1 do
|
|
tmp[i][j] := SubtractPoints(Path[i], Base[j]);
|
|
end;
|
|
|
|
SetLength(quad, 4);
|
|
SetLength(Result, (pathLen - delta) * baseLen);
|
|
g := Iif(IsClosed, pathLen - 1, 0);
|
|
|
|
for i := delta to pathLen - 1 do
|
|
begin
|
|
h := baseLen - 1;
|
|
k := (i - delta) * baseLen;
|
|
for j := 0 to baseLen - 1 do
|
|
begin
|
|
quad[0] := tmp[g][h];
|
|
quad[1] := tmp[i][h];
|
|
quad[2] := tmp[i][(j)];
|
|
quad[3] := tmp[g][(j)];
|
|
if not IsPositive(quad) then
|
|
Result[k + j] := ReversePath(quad) else
|
|
Result[k + j] := copy(quad, 0, 4);
|
|
h := j;
|
|
end;
|
|
g := i;
|
|
end;
|
|
end;
|
|
//------------------------------------------------------------------------------
|
|
|
|
function MinkowskiSum(const Pattern, Path: TPath64; PathIsClosed: Boolean): TPaths64;
|
|
begin
|
|
Result := Union( Minkowski(Pattern, Path, true, PathIsClosed), frNonZero);
|
|
end;
|
|
//------------------------------------------------------------------------------
|
|
|
|
function MinkowskiSum(const Pattern, Path: TPathD;
|
|
PathIsClosed: Boolean; decimalPlaces: integer): TPathsD;
|
|
var
|
|
tmp: TPaths64;
|
|
scale: double;
|
|
begin
|
|
scale := Power(10, decimalPlaces);
|
|
tmp := Union( Minkowski(ScalePath(Pattern, scale),
|
|
ScalePath(Path, scale), true, PathIsClosed), frNonZero);
|
|
Result := ScalePathsD(tmp, 1/scale);
|
|
end;
|
|
//------------------------------------------------------------------------------
|
|
|
|
function MinkowskiDiff(const path1, path2: TPath64): TPaths64;
|
|
begin
|
|
Result := Union( Minkowski(path1, path2, false, true), frNonZero);
|
|
end;
|
|
//------------------------------------------------------------------------------
|
|
|
|
function MinkowskiDiff(const Pattern, Path: TPathD;
|
|
PathIsClosed: Boolean; decimalPlaces: integer): TPathsD;
|
|
var
|
|
tmp: TPaths64;
|
|
scale: double;
|
|
begin
|
|
scale := Power(10, decimalPlaces);
|
|
tmp := Union( Minkowski(ScalePath(Pattern, scale),
|
|
ScalePath(Path, scale), false, PathIsClosed), frNonZero);
|
|
Result := ScalePathsD(tmp, 1/scale);
|
|
end;
|
|
//------------------------------------------------------------------------------
|
|
|
|
end.
|
|
|