1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69
|
procedure SimplifyInt2D(var ArrayOfTPointf: array of TPointf;
var Tol2: double;
var Marker: array of boolean; const j, k: integer);
// Simplify polyline in OrigList between j and k. Marker[] will be set to True
// for each point that must be included
var
i, MaxI: integer; // Index at maximum value
MaxD2: double; // Maximum value squared
CU, CW, B: double;
DV2: double;
P0, P1, PB, U, W, Oi: TPoint3Df;
begin
// Is there anything to simplify?
if k <= j + 1 then exit;
P0 := ArrayOfTPointf[j];
P1 := ArrayOfTPointf[k];
U := VecMinInt2D(P1, P0); // Segment vector
CU := DotProdInt2D(U, U); // Segment length squared
MaxD2 := 0;
MaxI := 0;
// Loop through points and detect the one furthest away
for i := j + 1 to k - 1 do begin
Oi := ArrayOfTPointf[i];
W := VecMinInt2D(Oi, P0);
CW := DotProdInt2D(W, U);
// Distance of point Orig[i] from segment
if (CW <= 0) then
begin
// Before segment
DV2 := DistSquaredInt2D(Oi, P0)
end
else
begin
if (CW > CU) then
begin
// Past segment
DV2 := DistSquaredInt2D(Oi, P1);
end else
begin
// Fraction of the segment
B := SafeDivide(CW, CU, 0.00);
PB.X := P0.X + B * U.X;
PB.Y := P0.Y + B * U.Y;
DV2 := DistSquaredInt2D(Oi, PB);
end;
end;
// test with current max distance squared
if (DV2 > MaxD2) then
begin
// Orig[i] is a new max vertex
MaxI := i;
MaxD2 := DV2;
end;
end;
// If the furthest point is outside tolerance we must split
if (MaxD2 > Tol2) then
begin // error is worse than the tolerance
// split the polyline at the farthest vertex from S
Marker[MaxI] := True; // mark Orig[maxi] for the simplified polyline
// recursively simplify the two subpolylines at Orig[maxi]
SimplifyInt2D(Tol2, Marker, j, MaxI); // polyline Orig[j] to Orig[maxi]
SimplifyInt2D(Tol2, Marker, MaxI, k); // polyline Orig[maxi] to Orig[k]
end;
end; |
Partager