Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- function [As,PsPolys] = stakeareas( Ps )
- n = size( Ps, 1 );
- PIs = allperms( 1:n );
- nP = size( PIs, 1 );
- if anycolinear( Ps )
- As = [];
- return;
- end
- As = [];
- PsPolys_ = [];
- for i = 1:nP
- PsPoly = Ps(PIs(i,:),:);
- if ~isjordan( PsPoly )
- continue;
- end
- A = abs( area( PsPoly ) );
- if ~ismember( A, As )
- PsPolys_ = [PsPolys_; PsPoly]; %#ok<AGROW>
- As = [As, A]; %#ok<AGROW>
- end
- end
- As = sort( As );
- if nargout >= 2
- PsPolys = PsPolys_;
- end
- end
- function PIs = allperms( Is )
- n = length( Is );
- if n == 1
- PIs = Is;
- elseif n == 2
- PIs = [Is; fliplr( Is )];
- else
- PIs = [];
- for i = 1:n
- i1 = Is(i);
- IsRem = allperms( Is(setdiff( 1:n, i )) );
- PIs = [PIs; i1*ones( size( IsRem, 1 ), 1 ), IsRem]; %#ok<AGROW>
- end
- end
- end
- function b = isjordan( Ps )
- n = size( Ps, 1 );
- b = true;
- for i = 1:n-2
- for j = i+2:n
- if intersect( Ps(i,:), Ps(i+1,:), Ps(j,:), Ps(mod( j, n )+1,:) )
- b = false;
- return;
- end
- end
- end
- % Detects edges that "sneak through" a vertex. A complete hack, but guaranteed to work for integer coordinates.
- for i = 1:n
- P_nr = (Ps(i,:) + Ps(mod( i, n )+1,:)*63)/64;
- P_fr = (Ps(mod( i+1, n )+1,:) + Ps(mod( i, n )+1,:)*63)/64;
- for j = setdiff( 1:n, [i, mod( i, n )+1] )
- if intersect( P_nr, P_fr, Ps(j,:), Ps(mod( j, n )+1,:) )
- b = false;
- return;
- end
- end
- end
- end
- function b = intersect( P11, P12, P21, P22 )
- x1 = P12(1) - P11(1);
- y1 = P12(2) - P11(2);
- x2 = P22(1) - P21(1);
- y2 = P22(2) - P21(2);
- b = ((y1*(P21(1) - P11(1))-(P21(2) - P11(2))*x1)* ...
- (y1*(P22(1) - P11(1))-(P22(2) - P11(2))*x1) < 0) && ...
- ((y2*(P11(1) - P21(1))-(P11(2) - P21(2))*x2)* ...
- (y2*(P12(1) - P21(1))-(P12(2) - P21(2))*x2) < 0);
- end
- function A = area( Ps )
- n = size( Ps, 1 );
- A = Ps(n,1)*Ps(1,2) - Ps(n,2)*Ps(1,1);
- for i = 2:n
- A = A + Ps(i-1,1)*Ps(i,2) - Ps(i-1,2)*Ps(i,1);
- end
- A = A/2;
- end
- function b = anycolinear( Ps )
- b = false;
- n = size( Ps, 1 );
- for i = 1:n-2
- for j = i+1:n-1
- for k = j+1:n
- if colinear( Ps(i,:), Ps(j,:), Ps(k,:) )
- b = true;
- return;
- end
- end
- end
- end
- end
- function b = colinear( P_m1, P, P_p1 )
- y21 = P(2) - P_m1(2);
- y13 = P_m1(2) - P_p1(2);
- y32 = P_p1(2) - P(2);
- L = y21*y21 + (P(1) - P_m1(1))*(P(1) - P_m1(1));
- L2 = y13*y13 + (P_m1(1) - P_p1(1))*(P_m1(1) - P_p1(1));
- if L2 > L
- L = L2;
- end
- L2 = y32*y32 + (P_p1(1) - P(1))*(P_p1(1) - P(1));
- if L2 > L
- L = L2;
- end
- b = L < 1e-9 || (abs( P(1)*y13 + P_p1(1)*y21 + P_m1(1)*y32 ) < 1e-9*sqrt( L ));
- end
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement