Intersect between 2 lines in 3D space
Here is the problem: I have 2 lines in 3D space (represented by a pair of points) and need to find the intersect point of these two lines. They WILL intersect, i know that, I just need some c++ code that I can use to find the point of intersection. I need this to find the centroid of a triangle. With this centroid point I will be drawing a line representing the triangle''s normal.
Thank you
parametric equations use u must!
first Line:
p = first pt
q = second pt
second Line:
r = first pt
s = second pt
first Line parametric equation:
x = (1-t)p + tq , where t is from 0 to 1
second Line parametric equation:
y = (1-t)r + ts , where t is from 0 to 1
then:
x = y must! find t u will, only then will you feel the force!
edit i must!
...................................................
[edited by - kuladus on June 2, 2003 12:39:56 AM]
first Line:
p = first pt
q = second pt
second Line:
r = first pt
s = second pt
first Line parametric equation:
x = (1-t)p + tq , where t is from 0 to 1
second Line parametric equation:
y = (1-t)r + ts , where t is from 0 to 1
then:
x = y must! find t u will, only then will you feel the force!
edit i must!
...................................................
[edited by - kuladus on June 2, 2003 12:39:56 AM]
Sorry, I think you misunderstood the question. I understand the math behind getting the intersect point, but I am confused as to how I can solve the equation in c++. Well, I dont understand all the math, for instance when I multiply a point by t is it like this: t(x, y, z) = (tx, ty, tz)?
This is what I have as of right now:
At this point my brain hurts, plus I dont know how I would adapt this to c++ code. Im gunna get some more coffee and see if that helps me...
This is what I have as of right now:
x1 = line 1 point 1 = (-1.00, 0.00, 0.00)x2 = line 1 point 2 = ( 0.00, 0.50,-0.25);x3 = line 2 point 1 = ( 0.00, 1.00, 0.00);x4 = line 2 point 2 = (-0.50, 0.00,-0.25);(these are actual points taken from my simple app)t = ts = 1 - tx = s(x1.x, x1.y, x1.z) + t(x2.x, x2.y, x2.z)y = s(x3.x, x3.y, x3.z) + t(x4.x, x4.y, x4.z)(s(x1.x), s(x1.y), s(x1.z)) + (t(x2.x), t(x2.y), t(x2.z)) = (s(x3.x), s(x3.y), s(x3.z)) + (t(x4.x), t(x4.y), t(x4.z))(s(x1.x) + t(x2.x), s(x1.y) + t(x2.y), s(x1.z) + t(x2.z)) = (s(x3.x) + t(x4.x), s(x3.y) + t(x4.y), s(x3.z) + t(x4.z))((t-1), t(.5), t(-.25)) = (t(-.5), (1-t), t(-.25))
At this point my brain hurts, plus I dont know how I would adapt this to c++ code. Im gunna get some more coffee and see if that helps me...
code for u i must hmmm?
note: haven''t tested it fully yet, but it should work for most/all cases
...................................................
#include <stdio.h>#include <math.h>typedef struct{ float x; float y; float z;} Point;typedef struct{ Point pt1; Point pt2;} Line;void Intersect(Line line1, Line line2);int main(){ Line L1, L2; L1.pt1.x = -1; L1.pt2.x = 0; L1.pt1.y = 0; L1.pt2.y = 0.5; L1.pt1.z = 0; L1.pt2.z = -0.25; L2.pt1.x = 0; L2.pt2.x = -0.5; L2.pt1.y = 1; L2.pt2.y = 0; L2.pt1.z = 0; L2.pt2.z = -0.25; Intersect(L1, L2); return 0;}void Intersect(Line line1, Line line2){/* Line1Param = (1-t)*line1.pt1 + t*line2.pt2 , where t is from 0 to 1 Line2Param = (1-t)*line2.pt1 + t*line2.pt2 , where t is from 0 to 1 Therefore Line1Param.x = (1-t1)*line1.pt1.x + t1*line1.pt2.x = line1.pt1.x - t1*(line1.pt1.x - line1.pt2.x) And also Line2Param.x = (1-t2)*line2.pt1.x + t2*line2.pt2.x = line2.pt1.x - t2*(line2.pt1.x - line2.pt2.x) These have to equal hmm? line1.pt1.x - t1*(line1.pt1.x - line1.pt2.x) == line2.pt1.x - t2*(line2.pt1.x - line2.pt2.x)(1) therefore t1 = (line1.pt1.x - line2.pt1.x + t2*(line2.pt1.x - line2.pt2.x))/(line1.pt1.x - line1.pt2.x) still following me? =) Now...Line1Param.y = (1-t1)*line1.pt1.y + t1*line1.pt2.y = line1.pt1.y - t1*(line1.pt1.y - line1.pt2.y) And also Line2Param.y = (1-t2)*line2.pt1.y + t2*line2.pt2.y = line2.pt1.y - t2*(line2.pt1.y - line2.pt2.y) line1.pt1.y - t1*(line1.pt1.y - line1.pt2.y) == line2.pt1.y - t2*(line2.pt1.y - line2.pt2.y)(2) therefore t1 = (line1.pt1.y - line2.pt1.y + t2*(line2.pt1.y - line2.pt2.y))/(line1.pt1.y - line1.pt2.y) (1) == (2) // == (3) (line1.pt1.x - line2.pt1.x + t2*(line2.pt1.x - line2.pt2.x))*(line1.pt1.y - line1.pt2.y) = (line1.pt1.y - line2.pt1.y + t2*(line2.pt1.y - line2.pt2.y))*(line1.pt1.x - line1.pt2.x) float d1y = line1.pt1.y - line2.pt1.y; //diff between y @ pt1 float d1x = line1.pt1.x - line2.pt1.x; //diff between x @ pt1 float s2y = line2.pt1.y - line2.pt2.y; float s1y = line1.pt1.y - line1.pt2.y; float s2x = line2.pt1.x - line2.pt2.x; float s1x = line1.pt1.x - line1.pt2.x; (d1x + t2*(s2x))*s1y = (d1y + t2*(s2y))*s1x d1x*s1y + t2*s2x*s1y = d1y*s1x + t2*s2y*s1x t2*(s2x*s1y-s2y*s1x) = d1y*s1x - d1x*s1y; t2 = (d1y*s1x - d1x*s1y)/(s2x*s1y-s2y*s1x); */ float d1y = line1.pt1.y - line2.pt1.y; //diff between y @ pt1 float d1x = line1.pt1.x - line2.pt1.x; //diff between x @ pt1 float s2y = line2.pt1.y - line2.pt2.y; float s1y = line1.pt1.y - line1.pt2.y; float s2x = line2.pt1.x - line2.pt2.x; float s1x = line1.pt1.x - line1.pt2.x; float t2 = (d1y*s1x - d1x*s1y)/(s2x*s1y-s2y*s1x); printf("T2: %f\n", t2); float t1 = (-d1y*s2x - -d1x*s2y)/(s1x*s2y-s1y*s2x); printf("T1: %f\n", t1); Point intersectPt; if ( (fabs(((1-t1)*line1.pt1.x + t1*line1.pt2.x)-((1-t2)*line2.pt1.x + t2*line2.pt2.x))<0.1)&& (fabs(((1-t1)*line1.pt1.y + t1*line1.pt2.y)-((1-t2)*line2.pt1.y + t2*line2.pt2.y))<0.1)&& (fabs(((1-t1)*line1.pt1.z + t1*line1.pt2.z)-((1-t2)*line2.pt1.z + t2*line2.pt2.z))<0.1)) { intersectPt.x = (1-t1)*line1.pt1.x + t1*line1.pt2.x; intersectPt.y = (1-t1)*line1.pt1.y + t1*line1.pt2.y; intersectPt.z = (1-t1)*line1.pt1.z + t1*line1.pt2.z; printf("Lines intersect at (%f, %f, %f)\n", intersectPt.x, intersectPt.y, intersectPt.z); } else printf("No intersection.\n");}
note: haven''t tested it fully yet, but it should work for most/all cases
...................................................
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement