Find all largest empty circles in a list of points

2 次查看（过去 30 天）
Ian Wood
Ian Wood 2013-9-26
回答： THERESA NYOROH 2019-12-22
Hi everyone,
I want to find all of the largest empty circles, which pass through any 3 points in a large list of points (~50). I have a code already, with which I have attempted to arrive at a proper solution, but my algorithm does not check for all empty circles accurately. It only checks if there are circles in a sequence of 3 points starting at the highest y-value and continuing all the way down the list of points in this manner.
i.e. first check (1,2,3); second check (2,3,4); third check (3,4,5); etc.
This is not feasible since we could have an empty circle corresponding to points (1,3,6) for example. This is not a sequence of three indices.
What is the proper algorithm to use in this case?
Thanks
  2 个评论
Image Analyst
Image Analyst 2013-9-27
编辑：Image Analyst 2013-9-27
I'm not sure I understand. So you have a cluster of points scattered around. And you want to take any and all possible combinations of three of those points and fit a circle to every possible triplet of points as in the FAQ and then check all other points that you have to see if any of them lie inside that circle. If a point does , then skip checking all other points and move on to checking the next triplet of points. Does that basically describe what you want to do?
Ian Wood
Ian Wood 2013-9-27
Yes that describes exactly what I want to do. The circle is not valid unless there are no other points lying inside it. It's not the circle calculation i'm looking for, I already have the formula for that. What i'm wondering about is the proper search method (how to determine the points that you can find the largest empty circle with).

请先登录，再进行评论。

请先登录，再回答此问题。

采纳的回答

Roger Stafford
Roger Stafford 2013-9-27
I am not sure what you mean by "largest empty circles". Empty of what? However, if the actual question you are asking is how to list all possible combinations of three points chosen from a set of about 50, that is easily done. I assume the numerals you used to identify the points are indices. Just call on matlab's 'nchoosek' function to get all possible combinations of three indices out of a set.
c = nchoosek(1:n,3);
where n is the number of points. The output 'c' will be an array of size n*(n-1)*(n-2)/6 by 3. Each row will have a different combination of three distinct indices ranging from 1 to n.
  2 个评论
Ian Wood
Ian Wood 2013-9-27
编辑：Ian Wood 2013-9-27
My apologies, what I mean by "largest empty circles" is that they only include 3 points, and that there are no other points inside of these circles. This function you provided looks useful, although it is not the optimal approach I think this is going to do what I need it to. I will experiment with this method in my code and let you know if it works.

请先登录，再进行评论。

更多回答（2 个）

Teja Muppirala
Teja Muppirala 2013-9-27
编辑：Teja Muppirala 2013-9-27
You don't have to try all combinations. You just need to calculate the Delaunay triangulation. Assuming that no 4 points lie on the same circle (which is a very reasonable assumption, since you could always just slighly perturb them if they do), then every triangle that does not contain any other points in it is part of the Delaunay triangulation, and this Delaunay triangulation is unique.
In other words, given some points in a plane, the Delaunay triangulation consists of all the triangles whose circumcircles do not contain other points, and any triangle whose circumcircle does not contain other points, must be part of the Delaunay triangulation.
n = 50;
x = rand(n,1);
y = rand(n,1);
dt = delaunayTriangulation(x,y)
triplot(dt);
hold all;
plot(x,y,'ko');
  3 个评论
显示 1更早的评论
Teja Muppirala
Teja Muppirala 2013-9-27
For 50 points, I am pretty sure that one call to delaunayTriangulation and using the result will be much faster than testing out all nchoosek(50,3) = 19600 combinations of 3 points.

请先登录，再进行评论。

THERESA NYOROH
THERESA NYOROH 2019-12-22
Thanks a lot for your contributions.Please Ian,I am really in need of the code for the empty circle.Also,please what is the code for getting the radius of the empty circle? I look forward to hearing from you,Ian.Thanks a lot.

类别

在 Help Center 和 File Exchange 中查找有关 Delaunay Triangulation 的更多信息

标签

产品

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by