Line Segment intersection

[roticv]

Hello,

I am trying to implement line segment intesection based on CLR, but I felt like there's somethign wrong with my code. It does not give correct value

for the line (x1,y1,x2,y2)
4 6 4 9
and
4 5 6 7

Code: Select all

int isintersect(line l1, line l2){
	int tmp, tmp2,tmp3,tmp4,flag=0;
	points p, q;
	if (max(l1.p1.x,l1.p2.x) >= min(l2.p1.x,l2.p2.x) &&
	max(l2.p1.x,l2.p2.x) >= min(l1.p1.x,l1.p1.x) && 
	max(l1.p1.y,l1.p2.y) >= min(l2.p1.y,l2.p2.y) &&
	max(l2.p1.y,l2.p2.y) >= min(l1.p1.x,l1.p1.y))
		flag = 1;
	if (flag == 0)
		return 0;
	p.x = l2.p1.x - l1.p1.x;
	p.y = l2.p1.y - l1.p1.y;
	q.x = l1.p2.x - l1.p1.x;
	q.y = l1.p2.y - l1.p1.y;
	tmp = cross(p,q);
	p.x = l2.p2.x - l1.p1.x;
	p.y = l2.p2.y - l1.p1.y;
	tmp2 = cross(p,q);
	if (tmp == 0 || tmp2 == 0)
		return 1;
	if (tmp != tmp2)
		return 1;
	return 0;
}

If anyone has more information on CLR's method can paste me a link or tell me what's wrong?

[_Rifat_]

I find several mistakes in your code:
1) instead
if (max(l1.p1.x,l1.p2.x) >= min(l2.p1.x,l2.p2.x) &&
max(l2.p1.x,l2.p2.x) >= min(l1.p1.x,l1.p1.x) &&
max(l1.p1.y,l1.p2.y) >= min(l2.p1.y,l2.p2.y) &&
max(l2.p1.y,l2.p2.y) >= min(l1.p1.x,l1.p1.y))
should be
if (max(l1.p1.x,l1.p2.x) >= min(l2.p1.x,l2.p2.x) &&
max(l2.p1.x,l2.p2.x) >= min(l1.p1.x,l1.p2.x) &&
max(l1.p1.y,l1.p2.y) >= min(l2.p1.y,l2.p2.y) &&
max(l2.p1.y,l2.p2.y) >= min(l1.p1.y,l1.p2.y))
2) I do not know what do cross function, but I think this is not correct.
if (tmp == 0 || tmp2 == 0)
return 1;
if (tmp != tmp2)
return 1;

I use following algorithm for determine either two segments intersect.
P1, P2 - first segment, P2, P3 - second segment.
Xmin1 and Xmax1 - min and max x coordinats of first segment
Ymin1 and Ymax1 - min and max y coordinats of first segment
Xmin2 and Xmax2 - min and max x coordinats of second segment
Ymin2 and Ymax2 - min and max y coordinats of second segment
Segments intersect when:
1) Xmax1>=Xmin2 and Xmax2>=Xmin1 and Ymax1>=Ymin2 and Ymax2>=Ymin1;
2) [P1P3, P1P2]*[P1P4, P1P2]<=0;
3) [P3P1, P3P4]*[P3P2, P3P4]<=0;
where P1P3, P1P2, P1P4, P3P1, P3P4, P3P2 - vectors,
[vector1, vector2] = vector1.x*vector2.y-vector1.y*vector2.x.

P.S. What is CLR method?

[roticv]

thanks alot. It's nice to see a reply on my birthday