

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_{1}, s_{2}, ... , 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^{2}) 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:
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 linesegments 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}, r_{1})([phi]_{2}, r_{2}) (polar coordinates) with [phi]_{1} > [phi]_{2} into two line segments ([phi]_{1}, r_{1})(2[pi], r_{3}) and (0, r_{3})([phi]_{2}, r_{2}) [/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:


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 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 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:
Quote:


Powered by YaBB 1 Gold  SP 1.4! Forum software copyright © 20002004 Yet another Bulletin Board 