/usr/src/castle-game-engine-4.1.1/3d/castleconvexhull.pas is in castle-game-engine-src 4.1.1-1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
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 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 | {
Copyright 2004-2013 Michalis Kamburelis.
This file is part of "Castle Game Engine".
"Castle Game Engine" is free software; see the file COPYING.txt,
included in this distribution, for details about the copyright.
"Castle Game Engine" is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
----------------------------------------------------------------------------
}
{ @abstract(Calculating convex hull.) }
unit CastleConvexHull;
interface
uses CastleVectors, CastleUtils, Math;
{ Calculates ConvexHull ignoring Z coordinates of pixels.
That is, all Points[*][2] are ignored.
Returns newly created array with the indices to Points.
If you want to draw an edge of convex hull,
you want to iterate over these points like (for each i) Points[Result[i]]).
Points.Count must be >= 1. }
function ConvexHull(Points: TVector3SingleList): TIntegerList;
implementation
function ConvexHull(Points: TVector3SingleList): TIntegerList;
{ this is the Jarvis algorithm, based on description in Cormen's
"Introduction to alg." }
var InResult: TBooleanList;
function FindNext(Start: Integer; var NextI: Integer; RightSide: boolean): boolean;
{ Starting from Points[Start], knowing that InResult[Start],
find next vertex on convex hull. If RightSide then we're moving from
lowest vertex to highest, walking over the right edge of the convex hull.
Else we're moving from highest to lowest, walking over the left edge
of hull.
Return false if RightSide and Start is the highest vertex,
or (not RightSide) and Start is the lowest vertex.
Else sets Next as appropriate and returns true.
Returned Next for SURE has InResult[Next] = false. }
var MaxCotanAngle, ThisCotan: Single;
MaxCotanAngleI, i: Integer;
begin
MaxCotanAngle := -MaxSingle;
MaxCotanAngleI := -1;
for i := 0 to Points.Count-1 do
if not InResult[i] then
begin
if FloatsEqual(Points.L[i][1], Points.L[Start][1]) then
begin
if RightSide = (Points.L[i][0] > Points.L[Start][0]) then
begin
MaxCotanAngle := MaxSingle;
MaxCotanAngleI := i;
end;
end else
if RightSide = (Points.L[i][1] > Points.L[Start][1]) then
begin
ThisCotan:=(Points.L[i][0] - Points.L[Start][0]) /
(Points.L[i][1] - Points.L[Start][1]);
if ThisCotan > MaxCotanAngle then
begin
MaxCotanAngle := ThisCotan;
MaxCotanAngleI := i;
end;
end;
end;
Result := MaxCotanAngleI <> -1;
if Result then NextI := MaxCotanAngleI;
end;
procedure MarkNext(i: Integer);
begin
InResult[i] := true;
Result.Add(i);
end;
var MinY: Single;
i0, i, NextI: Integer;
begin
Assert(Points.Count >= 1);
{ find i0, index of lowest point in Points }
MinY := Points.L[0][1];
i0 := 0;
for i := 1 to Points.Count-1 do
if Points.L[i][1] < MinY then
begin
MinY := Points.L[i][1];
i0 := i;
end;
InResult := TBooleanList.Create;
try
InResult.Count := Points.Count; { TFPGList already initializes all to false }
Result := TIntegerList.Create;
try
MarkNext(i0);
i := i0;
while FindNext(i, NextI, true ) do begin i := NextI; MarkNext(i); end;
while FindNext(i, NextI, false) do begin i := NextI; MarkNext(i); end;
except Result.Free; raise end;
finally InResult.Free end;
end;
end.
|