## Need expert's view for geometry algos.

Moderator: Board moderators

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
Note that monotone chain is O(n) if you're given points in sorted order.
For millions of years, mankind lived just like the animals. Then something happened which unleashed the power of our imagination. We learned to talk and we learned to listen...

mukeshtiwari
Learning poster
Posts: 63
Joined: Tue Mar 07, 2006 6:51 pm
Location: india
Still i have not found a problem about finding common area of two polygons.But this algo is mentioned in Shahriar Manjoor's article.
hello anidya would u like to post the link of Shahriar Manjoor's article.
thnkx

DJWS
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:
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?

DP
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Contact:

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
DJWS wrote:how to determine efficiently whether two segments intersect, when some endpoints of these two segments are colinear?
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 (A-P)*(B-P) <= 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
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:
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)

Anindya
New poster
Posts: 28
Joined: Sun Feb 04, 2007 4:34 am
Location: EEE,BUET,DHAKA
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.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
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.
For 819, I assumed you know how to find the minimum in O(n) time.

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.

Anindya
New poster
Posts: 28
Joined: Sun Feb 04, 2007 4:34 am
Location: EEE,BUET,DHAKA
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(Sutherland-Hodgman 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?