在凸多边形中内切两个圆，半径之和最大 [英] Inscribing two circles in convex polygon, with max sum of radiuses

问题描述

我正在尝试解决问题在凸多边形中内切两个圆，半径之和最大".我可以在具有最大半径的凸多边形中内切一个圆，但是两个圆呢?有什么算法可以解决我的问题.

分析算法优于数值算法.

解决方案

我能想到的唯一可以在约束范围内工作的方法就是分而治之:

1. 迭代所有"可能通过简单的线条将您的形状切成两半

   我会使用贪婪的 2x 嵌套搜索，例如

   并且正确的点很可能稍微"靠近中心点；由切割线和平均"之间的角度之间的比率偏移；切割线两侧圆周角

然而，这只是我的直觉，认为这样的结果将是最好的".而不仅仅是一些贪婪的结果几乎是最好的，可能会错过正确的答案！几何/数学证明不是我的事.

最重要的是，切割线很可能接近垂直于形状主轴(如果存在最长的中心线)，因此计算

如果你不想实现OBB,PCA，你也可以用O(log(n)^2)搜索和切割线搜索类似的搜索最大的中心线...>

I'm trying to solve problem "Inscribing two circles in convex polygon, with max sum of radiuses". I can inscribe one circle in convex polygon with max radius, but what about two circles? Is there any algorithms that solves my problem.

Analytical algorithms are preferable to numerical ones.

解决方案

The only thing that I can think of that could work within the constraints is to divide and conquer the problem:

1. iterate "all" possible cuts of your shape into two by simple line

   I would use greedy 2x nested search like approximation search as heuristics so the brute force will turn into much better complexity of O(log^2(n)) where n = shape_circumference/accuracy.

   So simply nest 2 for loops/searches that go along the whole circumference and cut the shape by the line they form. To boost speed you can add another heuristics like:

   No need to test the same 2 points in reverse order so the other for loop can start from the first point.

   No need to test full circumference for the second for loop as the correct answer will be most likely as close to perpendicular to circumference at both points as its possible so you can search only angles near by with some margin of error for example +/-30 degrees

2. compute inscribed circle for both shapes sharing the same point along the cut line

   this can be another search so adding another O(n) or O(n^2) resulting in O(log(n)^3) or O(log(n)^4) which is not that bad.

   I see it like this:

   And the correct point will be most likely near center "slightly" offset by the ratio between angle between cut line and "average" circumference angle on both sides of cut line

However this is just my intuition that such result will be the "best" and not just some greedy result in almost the best with possibility of missing correct answers! Geometric/Math proofs are not my thing.

On top of all this the cut line will be most likely close to perpendicular to shape major axis (longest center line if exist) so computing OBB or PCA or the biggest center line directly could speed up the points search and also the cut line position will be offset from shapes center by the "average" perpendicular width to the center line of the cuts which can be used to speed up the search again ...

width (brown) ratios offset (orange) the cut line from center:

You can also search the biggest center line with O(log(n)^2) search similarly to the cut line search if you do not want to implement OBB,PCA...

这篇关于在凸多边形中内切两个圆，半径之和最大的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！