I use this code to detect if two vectors intersect:
(
function VectorVectorIntersect pA a pB b =
(
local c = pB - pA
local cross1 = cross a b
local cross2 = cross c b
pA + ( a*( (dot cross2 cross1)/((length cross1)^2) ) )
)
-- "should not intersect"
pos01 = [-105.389,-10.7784,0]
pos02 = [-151.377,-5.98802,0]
pos03 = [-117.844,-39.521,0]
-- "should intersect"
-- pos01 = [-151.377,-5.98802,0]
-- pos02 = [-117.844,-39.521,0]
-- pos03 = [-110.659,-73.0539,0]
vect1 = normalize (pos03 - pos02)
vect2 = normalize (pos02 - pos01)
-- "get perpendicular vectors"
perpVect1 = normalize (cross vect1 [0,0,1])
perpVect2 = normalize (cross vect2 [0,0,1])
crossPoint = VectorVectorIntersect pos03 perpVect1 pos01 perpVect2
tmpMat = matrixFromNormal perpVect1
translate tmpMat pos03
if (crossPoint * inverse tmpMat).z > 0 then
print "intersect"
else
print "not intersect"
)
Is there any smarter method?
Two previous questions:
- Are you talking about segment intersection or line (‘infinite segment’) intersection?
- Are you talking about 2D segments (in the same plane, XY in your example) or 3D segments?
Edit: third additional question: - Do you need the intersection point or just to know if they intersect?
Wait! How do you define 2 vectors with 3 points? I don’t understand your input data, sorry.
This is a fast algorithm to check 2D segment intersection, but I really don’t know if it’s what you are asking for.
NOTES:
- Doesn’t gives the intersection point
- Total or partial overlapping of segments gives a result of FALSE
- Segments are defined by their start/end points
function FastSegmentIntersection p1 p2 p3 p4 =
(
a = p2 - p1;
b = p3 - p4;
c = p1 - p3;
alphaNumerator = b.y * c.x - b.x * c.y;
betaNumerator = a.x * c.y - a.y * c.x;
Denominator = a.y * b.x - a.x * b.y;
if (Denominator == 0) then
(
return false;
)
else
(
if (Denominator > 0) then
(
if (alphaNumerator < 0 or alphaNumerator > Denominator or betaNumerator < 0 or betaNumerator > Denominator) then
(
return false;
)
)
else if (alphaNumerator > 0 or alphaNumerator < Denominator or betaNumerator > 0 or betaNumerator < Denominator) then
(
return false;
)
)
return true;
)
1- No. Vectors.
2- vectors are in 2D plane.
3- i need to know if both vectors intersects.
4- i define vect1 by two points. Then i find perpendicular vector to vect1. The same happens with vect2. And finally I need to know if perpVect1 and perpVect2
intersects. Please see this image. I hope that it will explain what i need and what i mean by vector intersection
https://drive.google.com/file/d/1iAZxHXLW9SRXFe5tHPpSKdiARi4blXxC/view?usp=drivesdk
From top to bottom: intersection, no intersection, no intersection.
Sorry for the image, but i don’t t have access to a PC.
can you reupload or give permission to googledisk?
I can’t see the image either (but vectors don’t intersect eachother).
Here is the image:
https://drive.google.com/open?id=1iAZxHXLW9SRXFe5tHPpSKdiARi4blXxC
Oh! I see…
Always in the XY plane, or in any plane ( ortogonal to XYZ or not)?
In any plane. The 3 points that I use are in one plane, so its orientation is not important(i think).
If vec1 and vector defined by p1 and intersection point are co-directional and If vec2 and vector defined by p2 and intersection point are co-directional then vectors intersect
fn vecVecIntersect p1 vec1 p2 vec2 = (
if (abs (dot vec1 vec2)) > (1.0 - 0.0001) then (
false -- are parallel
) else (
vec3 = p2 - p1
c1 = cross vec1 vec2
c2 = cross vec3 vec2
intersectionPoint = p1 + vec1 * ( (dot c2 c1)/((length c1)^2) )
dot vec1 (intersectionPoint - p1) > 0 and dot vec2 (intersectionPoint - p2) > 0
)
)
Can’t improve it in performance.
Just one caution: Sergey’s parallel test is only valid if input vectors are normalized.
You can use “if (abs (length (cross vec1 vec2))) < Error do return false” that is always valid -but slower- so you don’t have to normalize anything (vect1, vect2, perpVect1, perpVect2).
Note: both ‘normalize’ in last Sergey’s code line are not needed but doesn’t affect performance very much.