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