You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
88 lines
2.4 KiB
88 lines
2.4 KiB
3 years ago
|
function tf = isIntersect( edge1, edge2 )
|
||
|
|
% isIntersect: detect whether two line segments (=edges) are intersect
|
||
|
|
%
|
||
|
|
% Returns true if line segment edge1 and edge2 intersect.
|
||
|
|
%
|
||
|
|
% input:
|
||
|
|
% edges - N-by-4 array, storing N line segments.
|
||
|
|
% Each line segment (edges(i,:)) is given by coordinates
|
||
|
|
% of two points : [x1 y1 x2 y2].
|
||
|
|
%
|
||
|
|
% Based on orientation. Check following website for the algorithm:
|
||
|
|
% https://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/
|
||
|
|
|
||
|
|
p1 = edge1(1:2); q1 = edge1(3:4);
|
||
|
|
p2 = edge2(1:2); q2 = edge2(3:4);
|
||
|
|
|
||
|
|
% Find the four orientations needed for general and
|
||
|
|
% special cases
|
||
|
|
o1 = orientation(p1, q1, p2);
|
||
|
|
o2 = orientation(p1, q1, q2);
|
||
|
|
o3 = orientation(p2, q2, p1);
|
||
|
|
o4 = orientation(p2, q2, q1);
|
||
|
|
|
||
|
|
% General case
|
||
|
|
if o1 ~= o2 && o3 ~= o4
|
||
|
|
tf = true; return
|
||
|
|
end
|
||
|
|
|
||
|
|
% Special Cases
|
||
|
|
% p1, q1 and p2 are colinear and p2 lies on segment p1q1
|
||
|
|
if o1 == 0 && onSegment(p1, p2, q1)
|
||
|
|
tf = true; return
|
||
|
|
end
|
||
|
|
|
||
|
|
% p1, q1 and q2 are colinear and q2 lies on segment p1q1
|
||
|
|
if o2 == 0 && onSegment(p1, q2, q1)
|
||
|
|
tf = true; return
|
||
|
|
end
|
||
|
|
|
||
|
|
% p2, q2 and p1 are colinear and p1 lies on segment p2q2
|
||
|
|
if o3 == 0 && onSegment(p2, p1, q2)
|
||
|
|
tf = true; return
|
||
|
|
end
|
||
|
|
|
||
|
|
% p2, q2 and q1 are colinear and q1 lies on segment p2q2
|
||
|
|
if o4 == 0 && onSegment(p2, q1, q2)
|
||
|
|
tf = true; return
|
||
|
|
end
|
||
|
|
|
||
|
|
% Doesn't fall in any of the above cases
|
||
|
|
tf = false;
|
||
|
|
end
|
||
|
|
|
||
|
|
function tf = onSegment( p, q, r )
|
||
|
|
% Given three colinear points p, q, r, the function checks if
|
||
|
|
% point q lies on line segment 'pr'
|
||
|
|
|
||
|
|
if q(1) <= max(p(1), r(1)) && q(1) >= min(p(1), r(1)) && ...
|
||
|
|
q(2) <= max(p(2), r(2)) && q(2) >= min(p(2), r(2))
|
||
|
|
tf = true;
|
||
|
|
else
|
||
|
|
tf = false;
|
||
|
|
end
|
||
|
|
end
|
||
|
|
|
||
|
|
function index = orientation( p, q, r )
|
||
|
|
% To find orientation of ordered triplet (p, q, r).
|
||
|
|
% The function returns following values
|
||
|
|
% 0 --> p, q and r are colinear
|
||
|
|
% 1 --> Clockwise
|
||
|
|
% 2 --> Counterclockwise
|
||
|
|
|
||
|
|
% See https://www.geeksforgeeks.org/orientation-3-ordered-points/
|
||
|
|
% for details of below formula.
|
||
|
|
val = (q(2) - p(2)) * (r(1) - q(1)) - ...
|
||
|
|
(q(1) - p(1)) * (r(2) - q(2));
|
||
|
|
|
||
|
|
if val == 0
|
||
|
|
index = 0; % colinear
|
||
|
|
return
|
||
|
|
end
|
||
|
|
|
||
|
|
if val > 0
|
||
|
|
index = 1; % clock wise
|
||
|
|
else
|
||
|
|
index = 2; % counterclock wise
|
||
|
|
end
|
||
|
|
end
|