38 lines
1.4 KiB
Text
38 lines
1.4 KiB
Text
func real CosAng(A, B); \Return cosine of angle between vectors A and B
|
|
int A, B; \Cos(Ang) = DotProd / (|A|*|B|)
|
|
real DotProd, Magnitude;
|
|
[DotProd:= float( A(0)*B(0) + A(1)*B(1));
|
|
Magnitude:= sqrt(float( sq(B(0)-A(0)) + sq(B(1)-A(1)) ));
|
|
return DotProd / Magnitude;
|
|
];
|
|
|
|
proc ConvexHull(N, P);
|
|
int N, P;
|
|
int Min, I, HullI, EndI, A(2), B(2), J, SJ;
|
|
real Ang, MinAng;
|
|
[Min:= -1>>1; \find index of point with smallest X coordinate
|
|
for I:= 0 to N-1 do
|
|
if P(I,0) < Min then
|
|
[Min:= P(I,0); HullI:= I];
|
|
EndI:= HullI;
|
|
|
|
A(0):= 0; A(1):= -1;
|
|
repeat ChOut(0, ^();
|
|
IntOut(0, P(HullI,0)); ChOut(0, ^,); IntOut(0, P(HullI,1));
|
|
ChOut(0, ^));
|
|
MinAng:= -1e12; \find index of point with smallest diverting angle
|
|
for J:= 0 to N-1 do
|
|
[B(0):= P(J,0) - P(HullI,0); B(1):= P(J,1) - P(HullI,1);
|
|
Ang:= CosAng(A, B);
|
|
if Ang > MinAng and J # HullI then
|
|
[MinAng:= Ang; SJ:= J];
|
|
];
|
|
A(0):= P(SJ,0) - P(HullI,0); A(1):= P(SJ,1) - P(HullI,1);
|
|
HullI:= SJ;
|
|
if HullI # EndI then Text(0, ", ");
|
|
until HullI = EndI;
|
|
];
|
|
|
|
ConvexHull(20, [[16,3], [12,17], [0,6], [-4,-6], [16,6], [16,-7], [16,-3],
|
|
[17,-4], [5,19], [19,-8], [3,16], [12,13], [3,-4], [17,5],
|
|
[-3,15], [-3,-9], [0,11], [-9,-3], [-4,-2], [12,10]])
|