Lines and a point

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
User avatar
N|N0
New poster
Posts: 36
Joined: Tue Jan 25, 2005 10:33 pm
Location: Ljubljana, Slovenija
Contact:

Lines and a point

Post by N|N0 » Sat May 21, 2005 10:20 pm

You're given a list of lines in the plane (which don't intersect) and a point.
The question is, which lines are seen from the point. (We can see the line if we can see more than 1 point of it.)

Any-one any idea???

Sanny
Learning poster
Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET
Contact:

Post by Sanny » Sun May 22, 2005 2:24 pm

I think it can be done in the following way:

1. First convert all the points into polar co-ordinate system taking the given point as origin.

2. Sort all the points by their angles.

3. Now between two consecutive points, draw a big enough line segment from the origin and determine which line it intersects first. Mark that line.

There may be some special cases to take care of, I guess.


Regards
Sanny

nibbler
New poster
Posts: 22
Joined: Fri Jun 04, 2004 10:30 pm

Post by nibbler » Sun May 22, 2005 2:24 pm

This is something like usaco fence4 problem. general idea of my solution was to keep line segments that are visible so far, to add one new at a time, checking those you examined so far: if part of a line segment is not visible, we can break it in two ( or less ) visible parts and continue checking recursivly. I remember that usaco coaches used different approach.

jakabjr
Learning poster
Posts: 56
Joined: Wed Mar 23, 2005 9:21 pm
Location: Timisoara, Romania

Post by jakabjr » Wed May 25, 2005 5:17 pm

if no 2 lines intersect, they are all paralell

if u have your lines in form y=mx+n (if not u can get to this from other forms). lines are paralell so m[0]=m[1]=...=m[max-1] = (notation) mm.
there is only one line y=mm*x+a that contains your point (use x,y coordinates of point to find a=?).
the lines seen are the greatest n smaller then a and the smallest n greater then a.
if there is a line that has n==a, i guess it has two visible points (the ones just near your point) and the other two lines mentioned above.
Understanding a problem in a natural way will lead to a natural solution

User avatar
N|N0
New poster
Posts: 36
Joined: Tue Jan 25, 2005 10:33 pm
Location: Ljubljana, Slovenija
Contact:

Post by N|N0 » Wed May 25, 2005 7:27 pm

I'm sorry that i wrote "lines" but i meant "line segments".

By the way:
A line can't be always in the y=kx+n form. For instance, x=3 is also a valid line. The ax+by-c=0 form is more convenient.

Post Reply

Return to “Algorithms”