Computing the set of points nearest to a point in a polygon boundary

Question

Let $P$ be a polygon. For each point $x$ on the boundary of $P$, denote by $N_P(x)$ the set of points in $P$, that are nearer to $x$ than to any other point on the boundary of $P$.

Given a subset $X$ of the boundary (e.g. an interval contained in one of the sides of $P$), what is an algorithm for computing $N_P(X)$?

Here is an example: $X$ is the blue interval at the bottom, and $N_P(X)$ is the blue polygon.

Answer 1

The following ideas might help.

The set $X$ can be partitioned into a set of disjoint intervals such that each interval is continuous and lies on one of the sides of polygon. For each interval $I$, we can find $N_{P}(I)$ and union of all $N_{P}(I)'s$ would give the required set $N_{P}(X)$. Now, let us find $N_{P}(I)$ for an interval $I$:

1. For ease of simplification, orient the polygon such that interval $I$ lies on the $x$-axis; similar to the one shown in your figure.
2. Let $a$ and $b$ be the two endpoints of $I$ such that $a\leq b$. It is easy to see that the polygon region that lies within the region $y \in (-\infty,\infty)$ and $x \in (-\infty,a) \cup (b,\infty)$ does not belongs to $N_{P}(I)$.
3. This leaves us with the region $R$ defined as $y \in (-\infty,\infty)$ and $x \in [a,b]$. Find all the segments of the polygon that lies in this region. You can do this by taking each side of the polygon and keeping its that part that lies in $R$. Suppose $S$ be this set of segments that we obtain.
4. For every $q \in [a,b]$, we will find the region $N_{P}(q)$. Let $S_{q} \subseteq S$ be the set of segments that intersects with the line $x = q$. The segment in $S_{q}$ that is closest to the $x$-axis will be the main competitor. Let this segment be $S_{q}^{c}$ and suppose it has height $h$. If the point $(q,h/2)$ lies in the polygon, then all the points: $(q,y)$, where $y\leq|h|/2$ lies in $N_{P}(q)$; otherwise not. If we can follows this process for every $q \in [a,b]$, then the union of $N_{P}(q)$'s will give $N_{P}(I)$.

Now, how can we perform step $4$ efficiently? In other words, we need obtain the segment $S_{q}^{c}$ for every $q \in [a,b]$? It is simple. Run the sweep line algorithm on $S$ with event points being the start and end points of the segments. Keep track of the line segments that are closest to the $x$-axis. In that way, you will find $N_{P}(I)$.