wu :: forums « wu :: forums - Segments in the Plane and Visibility » Welcome, Guest. Please Login or Register. Jul 24th, 2014, 6:33pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    cs (Moderators: Eigenray, william wu, Grimbal, SMQ, Icarus, towr, ThudnBlunder)    Segments in the Plane and Visibility « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Segments in the Plane and Visibility  (Read 3721 times)
Dudidu
Full Member

Posts: 227
 Segments in the Plane and Visibility   CG-visual.gif « on: Nov 12th, 2003, 9:49am » Quote Modify

Try this computional geometry question:
Let S = {s1, s2, ... , sn} be a set of n disjoint line segments in the plane, and let p be a point which doesn't lie on any of the segments in S.

Devise an algorihtm that will determine all the segments of S that p can "see" (i.e. all the segments of S that contain some point q such that the segment pq does not intersect any segment of S).

Look below for example: P "sees" s1, s3 and s4.
 IP Logged

towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13092
 Re: Segments in the Plane and Visibility   « Reply #1 on: Nov 12th, 2003, 10:59am » Quote Modify

an O(n2) algorithm wouldn't be too hard.. but I suppose you want something more efficient again, I'm guessing O(n log(n)), though I haven't worked out how to do that quite yet.. it'd help if I had a guaranteed angle at which there wasn't anything in sight, but there isn't really..
::I suppose I could start by sorting the segments at distance from p.
Better yet, I could cut some segments in two, and just use angular projection (I was worried about segments going over the edge and showing back up at the other side if you used a rectangle, but if you just cut them in half that's not a problem).. And then sort them angularly, and in depth. And I suppose use an angular sweepline? And a much simpler one than in that other question I didn't fill out the details at..
I think that pretty much solves it (in my own mind at least ;)
::
 « Last Edit: Nov 12th, 2003, 11:00am by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Dudidu
Full Member

Posts: 227
 Re: Segments in the Plane and Visibility   « Reply #2 on: Nov 13th, 2003, 5:53am » Quote Modify

on Nov 12th, 2003, 10:59am, towr wrote:
 an O(n2) algorithm wouldn't be too hard.. but I suppose you want something more efficient again, I'm guessing O(n log(n))...
towr, you're right in you guess (the O(n logn)).
However, I do not understand your solution. For example,
* what do you get by "breaking" the segments ?
* when you say "sort them angularly, and in depth" what do you mean ? how will you sort them (e.g. sorting by both end points of each segment) ?

Can you be a little bit more specific ?
 « Last Edit: Nov 13th, 2003, 5:54am by Dudidu » IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13092
 Re: Segments in the Plane and Visibility   segvis.zip « Reply #3 on: Nov 13th, 2003, 9:01am » Quote Modify

I made a little animation (see attachment), ::the bottom left corner shows which line-segments lie on the sweepline untill the next event (with the lowest one being visible, and the others also in order of distance).

The end points of the segments, and crossingpoints are laid out on an eventline, to do this the segments are first sorted according to their starting point (the first point the sweepline will encounter, which is easily found by taking the point of the segment which has the smallest angle)
As for breaking up segments, that simply means splitting the linesegment
([phi]1, r1)-([phi]2, r2) (polar coordinates) with  [phi]1 > [phi]2
into two line segments
([phi]1, r1)-(2[pi], r3) and (0, r3)-([phi]2, r2)
::
I hope this clears up the brilliance of my algorithm
 « Last Edit: Nov 13th, 2003, 9:19am by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Dudidu
Full Member

Posts: 227
 Re: Segments in the Plane and Visibility   « Reply #4 on: Nov 13th, 2003, 9:42am » Quote Modify

on Nov 13th, 2003, 9:01am, towr wrote:
 I made a little animation (see attachment)...,I hope this clears up the brilliance of my algorithm
towr, I need some time to fully understand your answer... so, I'll get back to you later .
 IP Logged
visitor
Guest

 Re: Segments in the Plane and Visibility   « Reply #5 on: Nov 13th, 2003, 9:50am » Quote Modify Remove

I assumed "disjoint" means the lines don't cross, which would make the problem a little simpler than towr's illustration.
I think I would calculate 3 things for each line, the angle of each endpoint and the distance from p at the closest point. Sort by distance, then, starting with the closest line, create a sorted list of blocked fields of vision. If a new line's endpoints both lie within one of those fields, it is unseen. If one endpoint is within a field and the other is not, it is seen and you record it as one larger field. If the endpoints are behind two different fields, it is seen and you merge those two fields into one (including all fields that previously existed between the two). If you reach the point where all 360 degrees are one field, you can stop calculating. But I'm not a trained programmer, so I have no idea what the O() of that algorithm works out to be.
 IP Logged
visitor
Guest

 Re: Segments in the Plane and Visibility   « Reply #6 on: Nov 13th, 2003, 9:58am » Quote Modify Remove

Sorry, that doesn't quite work. It's possible for a long line to come very close to p, yet have a short line that sorts farther away at its closest point to still be in front of the long line. I should just keep my mouth shut in these riddles where I don't actually have any training.
 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13092
 Re: Segments in the Plane and Visibility   « Reply #7 on: Nov 13th, 2003, 11:20am » Quote Modify

on Nov 13th, 2003, 9:50am, visitor wrote:
 I assumed "disjoint" means the lines don't cross, which would make the problem a little simpler than towr's illustration.
Ah yes.. I forgot about that..
I was allready starting to get worried I might have problems if the lines crossed maximally and where all in view (which is possible). And though that could be optimized a great deal, I'm not sure I could keep it O(n logn)..
But I think you're right, so my approach should work without a problem..

::The sweepline thus only needs to keep track of the order of the segments, which is easily done with a balanced tree.
On encountering a starting point the segment it belongs to is added, and on encountering an endpoint the corresponding segment is removed.
So it's then just a matter of working through the eventline (which consists of the starting and end points, ordered by angle)
::
 « Last Edit: Nov 13th, 2003, 11:31am by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Dudidu
Full Member

Posts: 227
 Re: Segments in the Plane and Visibility   « Reply #8 on: Nov 17th, 2003, 5:22am » Quote Modify

on Nov 13th, 2003, 11:20am, towr wrote:
 But I think you're right, so my approach should work without a problem...
towr, your general solution seems to be right !
but you haven't stated how we get a list of the visible segments from the angular sweepline (I belive that you know how to do it - so leave it).

P.S - I understand that there is no need for "breaking" segments (I didn't get it from the start ).
 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13092
 Re: Segments in the Plane and Visibility   « Reply #9 on: Nov 17th, 2003, 5:35am » Quote Modify

on Nov 17th, 2003, 5:22am, Dudidu wrote:
 towr, your general solution seems to be right ! but you haven't stated how we get a list of the visible segments
hmm.. I thought I had, quite simple really: any segments that are ever at the bottom of the heap on the sweepline. So whenever there's a change of closest segment just add it to a heap (which makes it easy to check you didn't allready include it. If you don't care about double mentionings a list or array will do).

Quote:
 P.S - I understand that there is no need for "breaking" segments (I didn't get it from the start ).
Conceptually it makes the eventline and processing simpler.. (There's different ways to make it all work though)

 « Last Edit: Nov 17th, 2003, 5:39am by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft => cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »