Algorithm for nearest edge detection with respect to a point (in all directions)

Question

I'm looking for an algorithm, a set of algorithms, or any pointers/remarks how to solve the following problem:

Given a polygon, a central point, and a set of points scaterred around the central point inside the polygon, I want to find the nearest "edges" being created by those points with respect to the central point. One of the algorithm's parameters should be "distance sensitivity" (meaning how far two points have to be far from eachother to be considered in a different cluster and break the line).

An illustration will maybe explain it better... this could be the input, where the + denotes the central point:

The output would be the following:

I am not very well-versed in computational geometry, so any pointers would be welcome.

I'd naively like to imagine the algorithm as a growing circle spreading outwards from the central point, parts of it getting stuck on the points (larger parts get stuck if the cluster is dense enough), and tearing off at the ends of the cluster because there are no points to support it there.

I have done some research into line-sweep algorithms, which partly fit my criteria. However, what I think I need is some kind of a circle-sweep algorithm.

Answer 1

I would suggest you use a sweep line algorithm, sweeping a line that emanates from the origin and rotating around it. Think of a lighthouse placed at the origin, with a beam of light that rotates around in a circle, and find the closest point illuminated by that beam of light.

In more detail: Convert the points to polar coordinates $(r,\theta)$ and sort them by increasing angle $\theta$. Let $S$ denote the set of resulting points. Then for each angle $\theta$ find the point closest to the origin out of all points whose angle is in the range $[\theta-\epsilon,\theta+\epsilon]$, and use this as the location of the perimeter at that angle. In particular, let $f(\theta) = \min \{r : (r,\theta') \in S, |\theta-\theta'| \le \epsilon\}$; then $f$ defines a curved line/path. You can apply some smoothing to it, and then use that as your red line. If there is no point with angle in the range $[\theta-\epsilon,\theta+\epsilon]$, then there is no red line there; you have a break in the line.

You could of course apply a standard clustering algorithm first, and then do this separately on each cluster, removing clusters that are "hidden" (further away than another cluster). From your image it looks like the clustering problem should be easy and you shouldn't have a difficult time finding a clustering algorithm that does a good job of separating the points into clusters. However, I'm not sure that's even necessary.