Hi Harry Larkim,
It seems you are trying to calculate the intersection between line segments and edges, and you have provided two methods for doing so. The first method uses vector projection to determine if the endpoints of a line segment project onto an edge in such a way that indicates intersection. The second method, based on Tamas Kis's MATLAB code, uses slope-intercept form to calculate the intersection point of two lines if they are not parallel or coincident.
Below are the modified MATLAB functions:
Projection Method Modified:
function [intersect, intersectionX, intersectionY] = checkIntersection(lineSegment, edge, intersectionThreshold, noIntersectionThreshold)
% Check if line segment intersects with edge using projection method
% intersectionThreshold: Number of consecutive intersection points required to detect an intersection
% noIntersectionThreshold: Number of consecutive non-intersection points required to detect no intersection
intersect = false;
intersectionX = NaN;
intersectionY = NaN;
persistent countIntersect countNoIntersect lastIntersect
% Compute projection of line segment endpoints onto edge
x1 = lineSegment(1,1);
y1 = lineSegment(1,2);
x2 = lineSegment(2,1);
y2 = lineSegment(2,2);
x3 = edge(1,1);
y3 = edge(2,1);
x4 = edge(1,2);
y4 = edge(2,2);
proj1 = projectPoint([x1 y1], [x3 y3], [x4 y4]);
proj2 = projectPoint([x2 y2], [x3 y3], [x4 y4]);
% Check if projection of endpoints are on opposite sides of edge
if sign(proj1(1) - x3) ~= sign(proj2(1) - x3)
% Compute intersection point
intersectionX = ((proj2(1) - proj1(1)) / (proj2(2) - proj1(2))) * (y3 - proj1(2)) + proj1(1);
intersectionY = y3;
intersect = true;
end
% Count intersection and non-intersection points
if intersect
countIntersect = countIntersect + 1;
countNoIntersect = 0;
else
countIntersect = 0;
countNoIntersect = countNoIntersect + 1;
end
if countIntersect >= intersectionThreshold && lastIntersect
intersect = true;
lastIntersect = true(1, intersectionThreshold);
elseif ~all(countIntersect < intersectionThreshold) && ~lastIntersect
intersect = false;
lastIntersect = false(1, intersectionThreshold);
elseif ~all(countNoIntersect >= noIntersectionThreshold) && all(lastIntersect)
intersect = false;
lastIntersect = false(1, intersectionThreshold);
elseif all(countNoIntersect < noIntersectionThreshold) && any(lastIntersect == false)
intersect = true;
lastIntersect = true(1, intersectionThreshold);
end
% Reset counters if necessary
if intersect == 0 && ~all(lastIntersect == 1)
countIntersect = 0;
elseif intersect == 1 && ~all(lastIntersect == 0)
countNoIntersect = 0;
end
end
function proj = projectPoint(point, edgeStart, edgeEnd)
% Compute projection of point onto line defined by edgeStart and edgeEnd
% From the formula proj = s + tproj,where
% tproj = (p-s) . (t-s) / ||t-s||^2
% Where ||t-s||^2 is a vector projection of t-s
% An example can be found at https://www.demonstrations.wolfram.com/IntersectionOfTwoLinesUsingVectors/
u = edgeEnd - edgeStart;
v = point - edgeStart;
t = dot(u, v) / dot(u, u);
proj = edgeStart + t * u;
end
Tamas Method Modified:
function [intersect, x_int, y_int] = checkLineIntersection(p1, p2, p3, p4)
% Initialize intersection flag and coordinates
intersect = false;
x_int = NaN;
y_int = NaN;
% Compute the coefficients for the equations of the lines
A1 = p2(2) - p1(2);
B1 = p1(1) - p2(1);
C1 = A1 * p1(1) + B1 * p1(2);
A2 = p4(2) - p3(2);
B2 = p3(1) - p4(1);
C2 = A2 * p3(1) + B2 * p3(2);
% Calculate the determinant
det = A1 * B2 - A2 * B1;
% Check if lines are parallel
if abs(det) < eps
return; % The lines are parallel
end
% Compute the intersection point
x_int = (B2 * C1 - B1 * C2) / det;
y_int = (A1 * C2 - A2 * C1) / det;
% Check if the intersection point is within both line segments
if (min(p1(1), p2(1)) <= x_int && x_int <= max(p1(1), p2(1))) && ...
(min(p1(2), p2(2)) <= y_int && y_int <= max(p1(2), p2(2))) && ...
(min(p3(1), p4(1)) <= x_int && x_int <= max(p3(1), p4(1))) && ...
(min(p3(2), p4(2)) <= y_int && y_int <= max(p3(2), p4(2)))
intersect = true;
end
end
I hope this helps!
Best Regards,
Abhishek Chakram
