0
$\begingroup$

I'd like to devise an algorithm which, given n non-intersecting line segments in the plane and a point p that does not lie on any of these segments, determines the region of the plane that is “visible” to p (see the image I've provided below). Ideally, this algorithm should run in O(n log n) time.

An example of the situation I described

$\endgroup$
4
  • 2
    $\begingroup$ And what is your question? Since you want to devise this algorithm, what do you have so far? $\endgroup$
    – Evil
    Commented Feb 22, 2017 at 2:00
  • $\begingroup$ Essentially, my question is this: How would I do this? I've thought about some sort of radial sweep process in the clockwise direction. It would account for whether or not a point has been "seen" by the sweep. For example, it could see if a segment is "open", and if the sweep finds an "open" segment, it would consider this segment to be visible. $\endgroup$
    – montagne
    Commented Feb 22, 2017 at 2:09
  • $\begingroup$ Aren't sweeps commonly used for set problems rather than query type problems? In a plane, for a set of non-intersecting segments $S$ and a set of points $P$ determine the "visible region" for all points $p$ from $P$. radial sweep I hear transformation (to a polar system around $p$). With non-intersecting line segments, pick any distance from each segment. $\endgroup$
    – greybeard
    Commented Feb 22, 2017 at 7:51
  • $\begingroup$ Transforming the points to polar coordinates is a bit overkill. Indeed, a 'radial sweep' is the right approach. However, you should determine which segments are visible from $p$, not all the points. Once you have determined the segments, it is simple to find the other boundaries of the visible region. $\endgroup$
    – Discrete lizard
    Commented Feb 25, 2017 at 18:25

1 Answer 1

-1
$\begingroup$

This is a rather easy geometry problem.

First of all, here's a similar competitive programming problem I solved:

https://www.beecrowd.com.br/judge/en/problems/view/1497

This problem called "Hide and Seek" gives you several points where the first 10 are "seekers". Also, several walls are given, represented as segments. For each of the 10 seekers, count how many other points can be seen. Both walls and points are up to $10^4$ (including seekers and non-seekers). In this problem, walls are also non-intersecting and no three points are collinear (among points or wall endpoints).

The algorithm involved is polar sort plus radial sweep, and runs in $O(N \log N)$ for each seeker, so the algorithm must be run 10 times.

My solution in C++ is here (https://github.com/ChrisVilches/Algorithms/blob/main/urionlinejudge/1497-hide_and_seek_2.cpp) and I will explain the most important things.

First, create the events:

// For every wall, create two events, one for each endpoint.
// Store the point centered on the seeker, and the wall index.
for (int j = 0; j < W; j++) {
  events.push_back({walls[j].p - seeker, j});
  events.push_back({walls[j].q - seeker, j});
}

// Polar sort the events. Refer to the Point comparator
// in order to see how the polar sort is done.
sort(events.begin(), events.end());

When performing the radial sweep, you need to have a mechanism to know which wall is the closest one. In the problem I linked to, it's also necessary, and I implemented it like this:

struct Segment {
  Point p, q;
  // ...

  pair<Point, Point> sorted_endpoints() const {
    return p.cross(q) > 0 ? make_pair(p, q) : make_pair(q, p);
  }

  bool operator<(const Segment& s) const {
    const auto [p1, q1] = sorted_endpoints();
    const auto [p2, q2] = s.sorted_endpoints();

    if (p1.cross(p2) > 0) {
      return p1.to(q1).cross(p1.to(p2)) < 0;
    } else {
      return p2.to(q2).cross(p2.to(p1)) > 0;
    }
  }
};

Note the comparator (operator<). This comparator will be used to store the segments in a std::set<Segment> while doing the sweep. This comparator is a special type of comparator which has the property that's specifically designed to work during a radial sweep, and cannot be used elsewhere (i.e. the order will get messed up).

So in order to make this comparator work, you insert into the set the segment when it enters the sweep, and remove it when it leaves.

Then for this particular problem, you can do something like this (I haven't implemented it, so you might need to tweak):

  1. The expected solution will be an array of points that form a (concave) polygon.
  2. Point $A$ enters the radial sweep. Is it the segment that's closest to $p$? If no, then do nothing.
  3. (Similar to previous step) If yes, then find the intersection of the ray starting from $p$ and stretching towards the point $A$ (current sweep event) with the previous closest segment. Find the intersection point, and add this point to the polygon. Also add point $A$ next.
  4. Similar cases are handled in a similar fashion.
  5. Runs in $O(N \log N)$ since at every step we insert/query the set in $O(\log N)$ and/or do some $O(1)$ operations.
  6. If at any point the set becomes empty, this means the region is infinite, and the area is infinite as well (visibility is not obstructed).

One observation is that if one segment is completely covered by another one closer to $p$, then nothing will happen with this segment (no points will be added). Points are only added when the closest segment becomes another segment at some enter/leave event.

One problem of this algorithm is that I haven't thought about where to start the radial sweep, and what work needs to be previously done. In Hide and Seek (problem linked above), I had to first "activate" the segments that cross the angle $0°$ so that when the sweep starts, they are already activated even if no endpoints have been sweeped through yet.

Also, is this problem part of a competitive programming problem? If so, can you share the link? I only found a paper containing this statement though. It'd be fun to implement it 😉.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.