-
Notifications
You must be signed in to change notification settings - Fork 8
/
lineIntersect.m
72 lines (59 loc) · 2.46 KB
/
lineIntersect.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
function [intAdjacencyMatrix,intMatrixX,intMatrixY] = lineIntersect(XY1,XY2)
% -----------------------------------------------------
% -- Fast mmWave Ray Tracing Simulator (v0.2)
% -- 2018 (c) junquan.deng@aalto.fi
% -----------------------------------------------------
% XY1 and XY2 are N1x4 and N2x4 matrices. Rows correspond to line segments.
% Each row is of the form [x1 y1 x2 y2] where (x1,y1) is the start point and
% (x2,y2) is the end point of a line segment:
% o--------------------------------o
% ^ ^
% (x1,y1) (x2,y2)
% 'intAdjacencyMatrix' : N1xN2 indicator matrix where the entry (i,j) is 1 if
% line segments XY1(i,:) and XY2(j,:) intersect.
%
% 'intMatrixX' : N1xN2 matrix where the entry (i,j) is the X coordinate of the
% intersection point between line segments XY1(i,:) and XY2(j,:).
%
% 'intMatrixY' : N1xN2 matrix where the entry (i,j) is the Y coordinate of the
% intersection point between line segments XY1(i,:) and XY2(j,:).
%%% Argument check.
%-------------------------------------------------------------------------------
validateattributes(XY1,{'numeric'},{'2d','finite'});
validateattributes(XY2,{'numeric'},{'2d','finite'});
[n_rows_1,n_cols_1] = size(XY1);
[n_rows_2,n_cols_2] = size(XY2);
if n_cols_1 ~= 4 || n_cols_2 ~= 4
error('Arguments must be a Nx4 matrices.');
end
%%% Prepare matrices for vectorized computation of line intersection points.
%-------------------------------------------------------------------------------
X1 = repmat(XY1(:,1),1,n_rows_2);
X2 = repmat(XY1(:,3),1,n_rows_2);
Y1 = repmat(XY1(:,2),1,n_rows_2);
Y2 = repmat(XY1(:,4),1,n_rows_2);
XY2 = XY2';
X3 = repmat(XY2(1,:),n_rows_1,1);
X4 = repmat(XY2(3,:),n_rows_1,1);
Y3 = repmat(XY2(2,:),n_rows_1,1);
Y4 = repmat(XY2(4,:),n_rows_1,1);
X4_X3 = (X4-X3);
Y1_Y3 = (Y1-Y3);
Y4_Y3 = (Y4-Y3);
X1_X3 = (X1-X3);
X2_X1 = (X2-X1);
Y2_Y1 = (Y2-Y1);
numerator_a = X4_X3 .* Y1_Y3 - Y4_Y3 .* X1_X3;
numerator_b = X2_X1 .* Y1_Y3 - Y2_Y1 .* X1_X3;
denominator = Y4_Y3 .* X2_X1 - X4_X3 .* Y2_Y1;
u_a = numerator_a ./ denominator;
u_b = numerator_b ./ denominator;
% Find the adjacency matrix A of intersecting lines.
INT_X = X1+X2_X1.*u_a;
INT_Y = Y1+Y2_Y1.*u_a;
INT_B = (u_a >= 0) & (u_a <= 1) & (u_b >= 0) & (u_b <= 1);
% Arrange output.
intAdjacencyMatrix = INT_B;
intMatrixX = INT_X .* INT_B;
intMatrixY = INT_Y .* INT_B;
end