wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Segments in the Plane and Visibility
        
(Message started by: Dudidu on Nov 12^th, 2003, 9:49am)

Title: Segments in the Plane and Visibility
Post by Dudidu on Nov 12^th, 2003, 9:49am

Try this computional geometry question:
Let S = {s₁, s₂, ... , s_n} 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).

8) Look below for example: P "sees" s1, s3 and s4.

Title: Re: Segments in the Plane and Visibility
Post by towr on Nov 12^th, 2003, 10:59am

an O(n²) 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..
::[hide]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 ;)[/hide]::

Title: Re: Segments in the Plane and Visibility
Post by Dudidu on Nov 13^th, 2003, 5:53am

on 11/12/03 at 10:59:49, towr wrote:

an O(n²) 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 ?

Title: Re: Segments in the Plane and Visibility
Post by towr on Nov 13^th, 2003, 9:01am

I made a little animation (see attachment), ::[hide]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]₁, r₁)-([phi]₂, r₂) (polar coordinates) with [phi]₁ > [phi]₂
into two line segments
([phi]₁, r₁)-(2[pi], r₃) and (0, r₃)-([phi]₂, r₂)
[/hide]::
I hope this clears up the brilliance of my algorithm :P

Title: Re: Segments in the Plane and Visibility
Post by Dudidu on Nov 13^th, 2003, 9:42am

on 11/13/03 at 09:01:36, towr wrote:

I made a little animation (see attachment)...,I hope this clears up the brilliance of my algorithm :P

towr, I need some time to fully understand your answer... so, I'll get back to you later ;).

Title: Re: Segments in the Plane and Visibility
Post by visitor on Nov 13^th, 2003, 9:50am

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.

Title: Re: Segments in the Plane and Visibility
Post by visitor on Nov 13^th, 2003, 9:58am

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.

Title: Re: Segments in the Plane and Visibility
Post by towr on Nov 13^th, 2003, 11:20am

on 11/13/03 at 09:50:40, 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.. 8)

::[hide]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)[/hide]::

Title: Re: Segments in the Plane and Visibility
Post by Dudidu on Nov 17^th, 2003, 5:22am

on 11/13/03 at 11:20:04, towr wrote:

But I think you're right, so my approach should work without a problem...[hide]<hide>[/hide]

towr, your general solution seems to be right :) !
but you haven't stated how we get a list of the visible segments from the [hide]angular sweepline[/hide] (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 :P).

Title: Re: Segments in the Plane and Visibility
Post by towr on Nov 17^th, 2003, 5:35am

on 11/17/03 at 05:22:08, 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: [hide]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)[/hide].

Quote:

P.S - I understand that there is no need for "breaking" segments (I didn't get it from the start :P).

Conceptually it makes the eventline and processing simpler.. (There's different ways to make it all work though)