是的。集合 C 的切比雪夫中心 x* 是中心位于 C 内部的最大球的直径。 [Boyd, p. 17] 416]当C是凸集时，那么这个问题就是凸优化问题。
更好的是，当 C 是多面体时，这个问题就变成了线性规划。
假设 m 边多面体 C 由一组线性不等式定义：ai^T x <= bi，对于 i in {1, 2, ..., m}。那么问题就变成了
maximize R
such that ai^T x + R||a|| <= bi, i in {1, 2, ..., m}
R >= 0
最小化的变量是R和x，而||a||是a的欧几里得范数。
Yes. The Chebyshev center, x*, of a set C is the center of the largest ball that lies inside C. [Boyd, p. 416] When C is a convex set, then this problem is a convex optimization problem.
Better yet, when C is a polyhedron, then this problem becomes a linear program.
Suppose the m-sided polyhedron C is defined by a set of linear inequalities: ai^T x <= bi, for i in {1, 2, ..., m}. Then the problem becomes
maximize R
such that ai^T x + R||a|| <= bi, i in {1, 2, ..., m}
R >= 0
where the variables of minimization are R and x, and ||a|| is the Euclidean norm of a.
Perhaps these "too messy" solutions are what you actually looking for, and there are no simplier ones?
I can suggest a simple, but potentially imprecise solution, which uses numerical analysis. Assume you have a resilient ball, and you inflate it, starting from radius zero. If its center is not in the center you're looking for, then it will move, because the walls would "push" it in the proper direction, until it reaches the point, from where he can't move anywhere else. I guess, for a convex polygon, the ball will eventually move to the point where it has maximum radius.
You can write a program that emulates the process of circle inflation. Start with an arbitrary point, and "inflate" the circle until it reaches a wall. If you keep inflating it, it will move in one of the directions that don't make it any closer to the walls it already encounters. You can determine the possible ways where it could move by drawing the lines that are parallel to the walls through the center you're currently at.
In this example, the ball would move in one of the directions marked with green:
Then, move your ball slightly in one of these directions (a good choice might be moving along the bisection of the angle), and repeat the step. If the new radius would be less than the one you have, retreat and decrease the pace you move it. When you'll have to make your pace less than a value of, say, 1 inch, then you've found the centre with precision of 1 in. (If you're going to draw it on a screen, precision of 0.5 pixel would be good enough, I guess).
If an imprecise solution is enough for you, this is simple enough, I guess.
Your problem is not trivial, and there
is no C# code that does this straight
out of the box. You will have to write
your own. I found the problem
intriguing, and did some research, so
here are a few clues that may help.
First, here's an answer in "plain
English" from mathforum.org:
The answer references Voronoi Diagrams
as a methodology for making the
process more efficient. In researching
Voronoi diagrams, in conjunction with
the "maximum empty circle" problem
(same problem, different name), I came
across this informative paper:
It was written by Martin Held, a
Computational Geometry professor at
the University of Salzberg in Austria.
Further investigation of Dr. Held's
writings yielded a couple of good
articles:
This site has lots of information,
code in various languages, and links
to other resources.
Finally, here is the URL to the
Mathematics and Computational Sciences
Division of the National Institute of
Standards and Technology (U.S.), a
wealth of information and links
regarding mathematics of all sorts:
The largest inscribed circle (I'm assuming it's unique) will intersect some of the faces tangentially, and may fail to intersect others. Let's call a face "relevant" if the largest inscribed circle intersects it, and "irrelevant" otherwise.
If your convex polygon is in fact a triangle, then the problem can be solved by calculating the triangle's incenter, by intersecting angle bisectors. This may seem a trivial case, but even when
your convex polygon is complicated, the inscribed circle will always be tangent to at least three faces (proof? seems geometrically obvious), and so its center can be calculated as the incenter of three relevant faces (extended outwards to make a triangle which circumscribes the original polygon).
Here we assume that no two such faces are parallel. If two are parallel, we have to interpret the "angle bisector" of two parallel lines to mean that third parallel line between them.
This immediately suggests a rather terrible algorithm: Consider all n-choose-3 subsets of faces, find the incenters of all triangles as above, and test each circle for containment in the original polygon. Maximize among those that are legal. But this is cubic in n and we can do much better.
But it's possible instead to identify faces that are irrelevant upfront: If a face is tangent
to some inscribed circle, then there is a region of points bounded by that face and by the two angle bisectors at its endpoints, wherein the circle's center must lie. If even the circle whose center lies at the farthest tip of that triangular region is "legal" (entirely contained in the polygon), then the face itself is irrelevant, and can be removed. The two faces touching it should be extended beyond it so that they meet.
By iteratively removing faces which are irrelevant in this sense, you should be able to reduce the
polygon to a triangle, or perhaps a trapezoid, at which point the problem will be easily solved, and its solution will still lie within the original polygon.
发布评论
评论（4）
是的。集合 C 的切比雪夫中心 x* 是中心位于 C 内部的最大球的直径。 [Boyd, p. 17] 416]当C是凸集时，那么这个问题就是凸优化问题。
更好的是，当 C 是多面体时，这个问题就变成了线性规划。
假设 m 边多面体 C 由一组线性不等式定义：ai^T x <= bi，对于 i in {1, 2, ..., m}。那么问题就变成了
最小化的变量是
R和x，而||a||是a的欧几里得范数。Yes. The Chebyshev center, x*, of a set C is the center of the largest ball that lies inside C. [Boyd, p. 416] When C is a convex set, then this problem is a convex optimization problem.
Better yet, when C is a polyhedron, then this problem becomes a linear program.
Suppose the m-sided polyhedron C is defined by a set of linear inequalities: ai^T x <= bi, for i in {1, 2, ..., m}. Then the problem becomes
where the variables of minimization are
Randx, and||a||is the Euclidean norm ofa.也许这些“太混乱”的解决方案正是您真正寻找的，并且没有更简单的解决方案？
我可以建议一个简单但可能不精确的解决方案，它使用数值分析。假设你有一个有弹性的球，你从半径零开始给它充气。如果它的中心不在你正在寻找的中心，那么它就会移动，因为墙壁会将它“推”向正确的方向，直到它到达他无法移动到其他地方的点。我猜想，对于凸多边形，球最终会移动到其半径最大的点。
您可以编写一个程序来模拟循环膨胀的过程。从任意点开始，然后“膨胀”圆圈，直到到达墙壁。如果你继续给它充气，它会向一个方向移动，而不会使其更接近它已经遇到的墙壁。您可以通过绘制穿过您当前所在中心与墙壁平行的线来确定它可能移动的方式。
在此示例中，球将沿绿色标记的方向之一移动：
(source: coldattic.info)
然后，朝这些方向之一稍微移动球（一个不错的选择可能是沿着角的平分线移动），然后重复该步骤。如果新的半径小于您的半径，请后退并降低移动速度。当您必须使步速小于某个值（例如 1 英寸）时，您就会以 1 英寸的精度找到中心。（如果您要在屏幕上绘制它，则精度为 0.5 像素）我想就足够了）。
如果一个不精确的解决方案对您来说足够了，我想这很简单。
Perhaps these "too messy" solutions are what you actually looking for, and there are no simplier ones?
I can suggest a simple, but potentially imprecise solution, which uses numerical analysis. Assume you have a resilient ball, and you inflate it, starting from radius zero. If its center is not in the center you're looking for, then it will move, because the walls would "push" it in the proper direction, until it reaches the point, from where he can't move anywhere else. I guess, for a convex polygon, the ball will eventually move to the point where it has maximum radius.
You can write a program that emulates the process of circle inflation. Start with an arbitrary point, and "inflate" the circle until it reaches a wall. If you keep inflating it, it will move in one of the directions that don't make it any closer to the walls it already encounters. You can determine the possible ways where it could move by drawing the lines that are parallel to the walls through the center you're currently at.
In this example, the ball would move in one of the directions marked with green:
(source: coldattic.info)
Then, move your ball slightly in one of these directions (a good choice might be moving along the bisection of the angle), and repeat the step. If the new radius would be less than the one you have, retreat and decrease the pace you move it. When you'll have to make your pace less than a value of, say, 1 inch, then you've found the centre with precision of 1 in. (If you're going to draw it on a screen, precision of 0.5 pixel would be good enough, I guess).
If an imprecise solution is enough for you, this is simple enough, I guess.
摘要：这并不是一件小事。所以它不太可能不会变得混乱。但有一些讲座幻灯片，您可能会觉得有用。
来源： http://www.eggheadcafe.com/software/aspnet/30304481/finding-the-maximum-inscribed-circle-in-c.aspx
Summary: It is not trivial. So it is very unlikely that it will not get messy. But there are some lecture slides which you may find useful.
Source: http://www.eggheadcafe.com/software/aspnet/30304481/finding-the-maximum-inscribed-circle-in-c.aspx
最大的内切圆（我假设它是唯一的）将与某些面相切，并且可能无法与其他面相交。如果最大的内切圆与一个面相交，我们称该面为“相关”，否则称为“不相关”。
如果您的凸多边形实际上是一个三角形，那么可以通过计算三角形的中心、通过角平分线相交来解决该问题。这似乎是一个微不足道的案例，但即使
你的凸多边形很复杂，内切圆总是与至少三个面相切（证明？似乎在几何上很明显），因此它的中心可以计算为三个相关面的中心（向外延伸以形成一个外接三角形）原始多边形）。
这里我们假设没有两个这样的面是平行的。如果两条平行线平行，我们必须将两条平行线的“角平分线”解释为它们之间的第三条平行线。
这立即表明了一个相当糟糕的算法：考虑所有 n-choose-3 个面子集，如上所述找到所有三角形的内心，并测试每个圆是否包含在原始多边形中。最大化那些合法的。但这是 n 的三次方，我们可以做得更好。
但可以预先识别不相关的面：如果面相切
到某个内切圆，则存在一个由该面及其端点处的两个角平分线界定的点区域，圆的中心必定位于其中。如果即使其中心位于该三角形区域最远尖端的圆也是“合法的”（完全包含在多边形中），则该面本身是无关紧要的，并且可以被删除。接触它的两个面应该延伸到它之外，以便它们相遇。
通过迭代地删除在这个意义上不相关的面孔，您应该能够减少
多边形到三角形，或者可能是梯形，此时问题将很容易解决，并且其解决方案仍然位于原始多边形内。
The largest inscribed circle (I'm assuming it's unique) will intersect some of the faces tangentially, and may fail to intersect others. Let's call a face "relevant" if the largest inscribed circle intersects it, and "irrelevant" otherwise.
If your convex polygon is in fact a triangle, then the problem can be solved by calculating the triangle's incenter, by intersecting angle bisectors. This may seem a trivial case, but even when
your convex polygon is complicated, the inscribed circle will always be tangent to at least three faces (proof? seems geometrically obvious), and so its center can be calculated as the incenter of three relevant faces (extended outwards to make a triangle which circumscribes the original polygon).
Here we assume that no two such faces are parallel. If two are parallel, we have to interpret the "angle bisector" of two parallel lines to mean that third parallel line between them.
This immediately suggests a rather terrible algorithm: Consider all n-choose-3 subsets of faces, find the incenters of all triangles as above, and test each circle for containment in the original polygon. Maximize among those that are legal. But this is cubic in n and we can do much better.
But it's possible instead to identify faces that are irrelevant upfront: If a face is tangent
to some inscribed circle, then there is a region of points bounded by that face and by the two angle bisectors at its endpoints, wherein the circle's center must lie. If even the circle whose center lies at the farthest tip of that triangular region is "legal" (entirely contained in the polygon), then the face itself is irrelevant, and can be removed. The two faces touching it should be extended beyond it so that they meet.
By iteratively removing faces which are irrelevant in this sense, you should be able to reduce the
polygon to a triangle, or perhaps a trapezoid, at which point the problem will be easily solved, and its solution will still lie within the original polygon.