Need expert's view for geometry algos.
Moderator: Board moderators

 Guru
 Posts: 584
 Joined: Thu Jun 19, 2003 3:48 am
 Location: Sanok, Poland
 Contact:

 Learning poster
 Posts: 63
 Joined: Tue Mar 07, 2006 6:51 pm
 Location: india
Hi everybody,
I have a question about Line Segment Intersection: how to determine efficiently whether two segments intersect, when some endpoints of these two segments are colinear? Assume we don't need to find definite intersection point.
More one question: how to find the intersection point with mininal precision error? Can it be done with inner product and cross product operations?
I have a question about Line Segment Intersection: how to determine efficiently whether two segments intersect, when some endpoints of these two segments are colinear? Assume we don't need to find definite intersection point.
More one question: how to find the intersection point with mininal precision error? Can it be done with inner product and cross product operations?
If they intersect, then some endpoint of some segment must be contained in the other segment, so you just check four times if a point is contained in a line segment. A point P is inside segment AB iff (AP)*(BP) <= 0, where * is the dot product. Alternatively, in integers you can check (A <= P && P <= B)  (B <= P && P <= A), where <= is lexicographic comparison; this way you don't need a multiplication.DJWS wrote:how to determine efficiently whether two segments intersect, when some endpoints of these two segments are colinear?
thanks mf and DP,
I also found some Line Segment Intersection problems. I would like to share with you.
Detect if two line segments intersect:
866 (lack of complicated cases)
10902
273
10256 (detect if two convex hulls interesct)
191 (detect if segment intersects with rectangle)
Distance between two line segments:
10709
10514
Find definite intersection point:
378 (find intersection of two lines)
137 (find area of intersection of two convex hulls)
10907 (find visible area in a concave polygon)
I also found some Line Segment Intersection problems. I would like to share with you.
Detect if two line segments intersect:
866 (lack of complicated cases)
10902
273
10256 (detect if two convex hulls interesct)
191 (detect if segment intersects with rectangle)
Distance between two line segments:
10709
10514
Find definite intersection point:
378 (find intersection of two lines)
137 (find area of intersection of two convex hulls)
10907 (find visible area in a concave polygon)
A lot of Thanks to DJWS for his list of problems regarding line intersection.
I have just done 273>good problem.
10709>also good problem.
I will also try the others as soon as possible.
Can any one say something about 819?it is difficult to find the maximum area.
Duleba,Graham scan is also O(n) if points are given clockwise or anticlockwise sorted.What do you mean by "sorted"?
Sorry for my late reply to you.
I have just done 273>good problem.
10709>also good problem.
I will also try the others as soon as possible.
Can any one say something about 819?it is difficult to find the maximum area.
Duleba,Graham scan is also O(n) if points are given clockwise or anticlockwise sorted.What do you mean by "sorted"?
Sorry for my late reply to you.
For 819, I assumed you know how to find the minimum in O(n) time.Anindya wrote:A lot of Thanks to DJWS for his list of problems regarding line intersection.
I have just done 273>good problem.
10709>also good problem.
I will also try the others as soon as possible.
Can any one say something about 819?it is difficult to find the maximum area.
Duleba,Graham scan is also O(n) if points are given clockwise or anticlockwise sorted.What do you mean by "sorted"?
Sorry for my late reply to you.
In fact, what you do is to find all candidates for the minimum and output the global minimum.
Think about it, if you know all candidates for the minimum, the candidates for the maximum must lie somewhere between the candidates for the minimum. For any 2 adjacent candidates for minimum, just do ternary search to find the corresponding candidate for maximum, and output the global maximum you find.
Hello everyone.
I have solved 137 & some other problems on polygon clipping.
But what can you say about 10321 & 805?
I have used a code(SutherlandHodgman algorithm according to Laszlo's book of computational geometry) which can determine the common area of two polygons if the clipper polygon is convex.
But how can i determine the common area if both the polygons are concave? And in problem 805,the resultant area of their intersection can be degenerate.What to do in that case?
Can anyone provide me any useful link/book/slides/codes?
I have solved 137 & some other problems on polygon clipping.
But what can you say about 10321 & 805?
I have used a code(SutherlandHodgman algorithm according to Laszlo's book of computational geometry) which can determine the common area of two polygons if the clipper polygon is convex.
But how can i determine the common area if both the polygons are concave? And in problem 805,the resultant area of their intersection can be degenerate.What to do in that case?
Can anyone provide me any useful link/book/slides/codes?