6
$\begingroup$

I have been working on a particularly challenging problem and was hoping for some guidance. Here is my problem. I have a point cloud containing millions of points. For each point in the set, I need to determine whether there exists an enclosing circle of radius r that can be drawn around the point (the point can lie anywhere within the circle) but that does not also contain any neighbouring point. Here is a diagram to help illustrate my scenario.

enter image description here

The blue point in the diagram above is the point of interest. The red points all lie within a 2r radius of the point of interest (any neighbouring points beyond this distance couldn't affect the result). In this case it is possible to draw a r radius circle that contains the point of interest and no other points. In fact there are clearly many such candidate circles. I'm not interested in getting all of the candidates, but rather simply knowing whether this condition occurs at all.

Perhaps there is an obvious way of performing this analysis that I am overlooking. I have thought about using Delaunay triangulation (does the point of interest lie inside a triangular facet?) but I'm not convinced that approach will work because of the specified circle size. I know that if there are two or fewer neighbours, then it is always possible to fit a circle that meets the requirements. I also know that if the convex hull of the neighbours doesn't enclose the point of interest, my condition is met. But none of these things help me with the general solution. Does anyone know of an approach or algorithm that could be used to accomplish this task?

$\endgroup$
  • 1
  • $\begingroup$ @k20 By golly, I think you've found it! Do you want to post an answer? $\endgroup$ – whiteboxdev Oct 28 '14 at 19:24
  • $\begingroup$ nah we can just close as duplicate :) $\endgroup$ – k20 Oct 28 '14 at 19:25
  • $\begingroup$ @k20 I'm not sure if the Stack Exchange definition of a duplicate can cross sites. This would be a cross-posting, but given I didn't ask the other question, it's not even that. $\endgroup$ – whiteboxdev Oct 28 '14 at 19:30
6
$\begingroup$

Let the circle centered at your blue point with radius $r$ be denoted as $C_r$ and with radius $2r$ (the solid circle in your diagram) as $C_{2r}$. For each red point $p_i \in C_{2r}$ construct a circle of radius $r$ centered at $p_i$ and call it $C_i$. Any circle centered inside of $C_i$ contains $p_i$ and is therefore invalid. Any circle centered inside of $C_r$ can possibly be valid. Therefore you need to find a point that is inside of $C_r$ but outside of all $C_i$. Your solution is then $C_r\setminus\cup C_i $. Of course finding these points is easier said than done.

The union of the circles can be found using generalized voronoi diagrams as discussed in this mathoverflow question. This is likely overkill for you question though since you don't need the entire space, only a single point.

The algorithm I think you need is this:

  1. Construct a voronoi diagram of your red points.
  2. Find the intersection of $C_r$ (a circle centered at the blue point with radius $r$) with all the edges of the voronoi diagram
  3. Check the distance from each vertex of the voronoi diagram inside $C_r$ and the points constructed in step 2. to one of the red points whose region the point borders. If it is atleast $r$, then you are

By construction they are all within $r$ of the blue point. The vertices around a region of a voronoi diagram are as far as you can possible get from the points from which the diagram was constructed. For example if a vertex is at the border of 3 regions, by definition it must be equidistant from all 3 red points used to construct those three regions of the diagram. Therefore you only need to check its distance from 1 of them.

As an example I have taken the image from the Wikipedia article on Voronoi Diagrams and edited it.

enter image description here

The red and blue points are the same as in your diagram. The yellow circle is a circle of radius $r$ centered at the blue point. All you need to do is check each of the Cyan points distance to a single red point in a neighboring region. If a circle can't be placed centering at one of the cyan points, then no circle can be placed that fits your requirements.

$\endgroup$
  • $\begingroup$ Thank you for your answer. Unless I'm missing something, your method implies that the circle must be centred on the point of interest, which is not the case. Have I mis-interpreted the solution? $\endgroup$ – whiteboxdev Oct 28 '14 at 19:32
  • 1
    $\begingroup$ No, the circle is not centered at the point of interest. The circle can be centered at any of the cyan points in the image. The yellow circle simply shows a maximum distance the centerpoint can be from the point of interest. $\endgroup$ – Godric Seer Oct 28 '14 at 19:34
  • $\begingroup$ Ah, it's all clear now. It'll take me a little longer to digest all the details of this solution but how would you compare this algorithm to the one k20 linked to? I like your solution in that it only requires calculating the Voronoi diagram once. Would you say they are equivalent in their result? $\endgroup$ – whiteboxdev Oct 28 '14 at 19:36
  • $\begingroup$ They should give the same answers since the voronoi diagram in mine is identical to the second voronoi diagram calculated in his. Also mine requires that the voronoi diagram of the red points be calculated for every point of interest while his simply updates a global diagram by removing the point of interest. If the red points are always the same you could calculated it once and keep it around though. Mine may require checking a few extra points than his, but that would only hurt efficiency by a few 10's of percent. $\endgroup$ – Godric Seer Oct 28 '14 at 19:38
  • $\begingroup$ For my application, I would end up having to calculate the Voronoi diagram for each neighbourhood of each point anyhow, since I have a constraint that will drop out certain points (based on a z value) from the neighbourhood. So there is no global diagram in my case anyhow. $\endgroup$ – whiteboxdev Oct 28 '14 at 19:44
2
$\begingroup$

I don't think this is optimal, but this doesn't fit into a comment. A maximal enclosing circle around a point would have to pass through at least three other points, as otherwise it can be enlarged or is infinite in some directions. So for a given point, it might be possible to look at all triples of "nearby" points (in the sense of being within a few hops in the Delaunay triangulation graph, for example) and check whether the unique circle passing through that triple has radius $\geq r$ and encloses one and only one other point. Then that enclosed point satisfies the conditions.

Given that the centre of the enclosing circle isn't necessarily the point it encloses, the Delaunay graph wouldn't easily produce the optimal sets of triples to check, I think. So checking lots of nearby points might be a start.

The issue is that it's not at all clear how to pick "nearby" triples so that the result is optimal, so maybe this only makes sense as an approximation. The accuracy might depend on how uniformly distributed the points are.

$\endgroup$
  • $\begingroup$ Thank you for your reply (+1). Is this three-point constraint true? Considering the diagram above, I would think that the maximum radius circle that encloses the blue point would be one of the possible circles that has both of the TWO nearest points on its circumference. There is no circle defined by three of the points that enclose the point of interest. At least there isn't one that doesn't also contain another neighbouring point. $\endgroup$ – whiteboxdev Oct 28 '14 at 16:22
  • $\begingroup$ @whiteboxdev In your diagram the maximal circle is infinite (it's a half-plane with the boundary line passing through two red points). If there were another red point on the other side, above the blue, that would be the third point, and the maximal circle would be a circle. In general, a circle is specified by three points, not two, so I believe this is right. $\endgroup$ – Kirill Oct 28 '14 at 16:26
  • $\begingroup$ Yes, you're right that the maximal circle is infinite in the diagram above. Three points are required to define a unique circle, but two points can define a set of circles (two I should think, one of which could enclose the point of interest). Unless I'm missing something. $\endgroup$ – whiteboxdev Oct 28 '14 at 16:29
  • $\begingroup$ @whiteboxdev Yes, and the centres of the circles defined by two points lie on the line passing halfway between them, perpendicular to the line between them. If the blue point is outside the convex hull of the red points, the problem is trivial anyway, so the tricky case is the case with a finite maximal circle. $\endgroup$ – Kirill Oct 28 '14 at 16:32
  • 1
    $\begingroup$ My first thought is to look at the voronoi cell. If it contains a point that is at least r distance from the 'blue' point then you are done. Otherwise I'm not sure, maybe look along the line segment between the 'blue' point and its most distant point in its voronoi cell? $\endgroup$ – k20 Oct 28 '14 at 18:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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