Issues with the miscalculation of different line intersect functions
1 vue (au cours des 30 derniers jours)
Afficher commentaires plus anciens
Hi, I have continous issues with calculating if one a startpoint and a number of endpoints intersects an obstacle. In the past i have been successful however i have had issues with this particular case. I tried to use number of different methods , but i have included best functions , 1. which uses the projection method and 2. which uses a function based on the someelses work line_intersection-MATLAB/line_intersection.m at main · tamaskis/line_intersection-MATLAB · GitHub. Both functions produce the same graph which i have included. I have also included a different graph that shows a ict cubes layout where function 1 was successful. I have also tried cross product and determinant method which also created worst results. Also the graph i have provided at end which shows the issue , uses a random x and y scatter and is only an example
- Projection method with error checking:
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
2. Tamas method modified - line_intersection-MATLAB/line_intersection.m at main · tamaskis/line_intersection-MATLAB · GitHub:
function [intersect, x_int, y_int] = checkLineIntersection(p1, p2, p3, p4)
[x1, y1, m1] = extractLineInfo(p1, p2);
[x2, y2, m2] = extractLineInfo(p3, p4);
if (~isnan(m1)) && (~isnan(m2)) && (m1 ~= m2)
x_int = ((m1*x1-m2*x2)-(y1-y2))/(m1-m2);
y_int = y1+m1*(x_int-x1);
intersect = true;
elseif isnan(m1) && (~isnan(m2))
x_int = x1;
y_int = y2+m2*(x_int-x2);
intersect = true;
elseif ~isnan(m1) && isnan(m2)
x_int = x2;
y_int = y1+m1*(x_int-x1);
intersect = true;
elseif ((isnan(m1) && isnan(m2) && x1 == x2) || (m1 == m2 && (y1 - m1*x1) == (y2 - m2*x2)))
x_int = NaN;
y_int = NaN;
intersect = false;
elseif ((isnan(m1) && isnan(m2) && x1 ~= x2) || (m1 == m2 && (y1 - m1*x1) ~= (y2 - m2*x2)))
x_int = Inf;
y_int = Inf;
intersect = false;
end
end
function [x, y, m] = extractLineInfo(p1, p2)
% Compute slope and intercept of line
if abs(p2(1) - p1(1)) < eps
% Vertical line
x = p1(1);
y = 0;
m = NaN;
else
m = (p2(2) - p1(2)) / (p2(1) - p1(1));
x = p1(1);
y = p1(2) - m * x;
end
end
Graph of issue quesition:
Example of function 1 working->:
Please and thank you for any assistance
0 commentaires
Réponses (1)
Abhishek Chakram
le 6 Fév 2024
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
0 commentaires
Voir également
Catégories
En savoir plus sur Transportation Engineering dans Help Center et File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!