Segment crossings

Find segment crossings and proximate points (e.g., for polygon intersection testing).

% Syntax:

%

% [flag,pt,ipt1,ipt2] = segmentx(pt,iseg1,iseg2,tol);

% [flag,pt,ipt1,ipt2] = segmentx(pt,iseg1,iseg2);

%

% Inputs:

%

% pt: 2-column matrix of points ([x,y] coordinate pairs), in any

% sequencing order

%

% iseg1: 2-column matrix of first segments' end-point indices in the

% range 1:size(pt,1). iseg1(j,:) represents a line segment from

% pt(iseg1(j,1),:) to pt(iseg2(j,2),:).

%

% iseg2: 2-column matrix of second segments' end-point indices in the

% range 1:size(pt,1), same format as iseg1.

%

% tol: scalar, non-negative, proximity tolerance for point equality

% testing, OPTIONAL, default = 0. Points [x1,y1] and [x2,y2] are

% considered to be proximate if norm([x1-x2,y1-y2])<=tol.

%

% Outputs:

%

% flag: logical, true if any point in the first segment list is proximate

% to a point from the second segment list, excluding shared points.

% Points are "shared" if they have the same pt index in iseg1 and iseg2.

% (Equality of point coordinates in pt does not make them "shared".)

% Proximity testing between two segments sharing a single end point only

% considers proximate point pairs where one of the points is a segment

% end point.

%

% pt:same as input, but with rows added for proximate points

%

% ipt1,ipt2: sparse matrices of intersection point indices in pt, of size

% [size(iseg1,1),size(iseg2,1)] and in the range 0:size(pt,1). If

% segments iseg1(j1,:) and iseg2(j2,:) have (non-shared) proximate

% points, then one such point pair, pt1 from the first segment and pt2

% from the second segment, will be in the pt list with pt1 =

% pt(ipt1(j1,j2),:) and pt2 = pt(ipt2(j1,j2),:). If the segments have no

% such proximate points, then ipt1(j1,j2) and ipt2(j1,j2) will be zero.