-
Notifications
You must be signed in to change notification settings - Fork 5
/
polygon_intersection.m
114 lines (83 loc) · 2.74 KB
/
polygon_intersection.m
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
clear all
clear all
clc
% Specify polygon variables
numVert = 8;
radius = 1;
radVar = 1; % variance in the spikiness of vertices
angVar = 1; % variance in spacing of vertices around the unit circle
% preallocate x and y
x = zeros(numVert,1);
y = zeros(numVert,1);
% angle of the unit circle in radians
circleAng = 2*pi;
% the average angular separation between points in a unit circle
angleSeparation = circleAng/numVert;
% create the matrix of angles for equal separation of points
angleMatrix = 0: angleSeparation: circleAng;
% drop the final angle since 2Pi = 0
angleMatrix(end) = [];
% generate the points x and y
for k = 1:numVert
x(k) = (radius + radius*rand(1)*radVar) * cos(angleMatrix(k) + angleSeparation*rand(1)*angVar);
y(k) = (radius + radius*rand(1)*radVar) * sin(angleMatrix(k) + angleSeparation*rand(1)*angVar);
end
% Graph the polygon and connect the final point to the first point
plot([x; x(1)],[y; y(1)],'ro-')
hold on
plot([-2 2],[0 0],'k')
plot([0 0],[-2 2],'k')
Polygon_vertex = [x y];
shifted_polygon_vertex = circshift(Polygon_vertex, -1);
PolygonXY = [Polygon_vertex shifted_polygon_vertex];
%% Generate lines
gap_y = radius./10;
% left limit
l_limit = min(Polygon_vertex(:,1));
down_limit = min(Polygon_vertex(:,2));
up_limit = max(Polygon_vertex(:,2));
%right limit
r_limit = max(Polygon_vertex(:,1));
y1 = down_limit - gap_y;
y2 = up_limit + gap_y;
% coverage parameters
xd = 0.2;
nl = floor((r_limit - l_limit)/xd) +1;
i = 1;
LinesXY = zeros(nl,4);
x1 = l_limit;
x2 = x1;
while(x1 <= r_limit)
LinesXY(i,:) = [x1 y1 x2 y2];
x1 = x1 + xd;
x2 = x1;
i = i + 1;
end
LinesXY;
%% SPEED TEST METHOD 1.
tic
out = lineSegmentIntersect(PolygonXY,LinesXY);
dt_1 = toc;
intersections = [out.intMatrixX(:) out.intMatrixY(:)];
intersections( ~any(intersections,2), : ) = [];
fprintf(1,'Method 1 took %.2f seconds for %.0f line segments...\n',dt_1,nl);
%% PREPARE THE FIGURE.
is_show = true;
if is_show
% Show the intersection points.
figure('Position',[10 100 500 500],'Renderer','zbuffer');
axes_properties.box = 'on';
axes_properties.XLim = [-2 2];
axes_properties.YLim = [-2 2];
axes_properties.DataAspectRatio = [1 1 1];
axes_properties.NextPlot = 'add';
axes(axes_properties,'parent',gcf);
line([PolygonXY(:,1)';PolygonXY(:,3)'],[PolygonXY(:,2)';PolygonXY(:,4)'],'Color','r');
line([LinesXY(:,1)';LinesXY(:,3)'],[LinesXY(:,2)';LinesXY(:,4)'],'Color','k');
scatter(intersections(:,1), intersections(:,2),[],'b');
title('Intersection Points');
figure('Position',[500 90 500 500],'Renderer','zbuffer');
sort(intersections);
plot(intersections(:,1), intersections(:,2));
title('Straight Path');
end