#### Archived

This topic is now archived and is closed to further replies.

# Intersect between 2 lines in 3D space

This topic is 5676 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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

##### Share on other sites
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]

##### Share on other sites
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:

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...

##### Share on other sites
code for u i must hmmm?

#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

...................................................

1. 1
2. 2
Rutin
18
3. 3
khawk
15
4. 4
A4L
14
5. 5

• 10
• 13
• 26
• 10
• 11
• ### Forum Statistics

• Total Topics
633744
• Total Posts
3013666
×