在采访之后,我有了这个问题并且现在我没有任何好主意来解决它 .
给定二维平面上的圆形输出与中心距离最大的圆的边界中或上的积分点 . 中心和半径的坐标是浮点数 . 任何极客都可以给我一些建议吗?
假设您的圆圈位于 (X,Y) ,半径为 R .
(X,Y)
R
1)生成所有可能 x 的列表:
x
xList=[ceil(X-R):1:floor(X+R)]
2)寻找潜力 y :
y
yUpperList=Y+sqrt(R^2 - (xList-X).^2) yLowerList=Y-sqrt(R^2 - (xList-X).^2)
3)将 y 候选者缩小为整数
yUpperList = floor(yUpperList) yLowerList = ceil(yLowerList)
4)重新计算距离
distance=sqrt([yUpperList;yLowerList].^2 + [xList;xList].^2)
5)找到最大距离:
maxDistance = max(distance(:))
这给你 O(R) 复杂性 .
O(R)
我猜解决方案的大小与 R 呈线性关系,所以我认为你不能做得更好 .
如果你正在寻找一个可以开始的地方,不要害怕思考“一种可能有用的坏方法” .
这是一个数学/逻辑问题,而不是计算问题,一旦你知道如何在无限时间“手动”完成这个任务,用编程语言实现它应该是解决方案的更容易的部分 .
例如...
我们的策略可能是:
列举围绕圆圈的正方形中的所有“积分点”(效率低下,但考虑到这将使你的大脑至少进入装备状态) .
1)编写一个函数,输出该正方形中所有点的列表 . 在C中,您可能希望实现
struct IntPoint{ int x; int y; }; std::vector<IntPoint> getPointsAroundCircle(float center, float radius);
2)遍历所有点 . 弄清楚哪些点实际上在圆圈中(/上),并“记住”哪个点具有最大距离 . 您可能希望实现以下辅助函数:
float distance(float center, float radius, const IntPoint & p);
提示:如何知道一个点与圆心的距离有助于我们判断它是否在圆圈内?
注意:涉及浮点数/双打的计算(或更确切地说比较)需要考虑舍入 . 您可能希望使用某种"epsilon"作为容差进行比较 . 一些阅读材料,如果你有兴趣:https://randomascii.wordpress.com/2012/02/25/comparing-floating-point-numbers-2012-edition/
3)完成所有点后,您将知道要打印哪个点的x,y坐标 .
2 回答
假设您的圆圈位于
(X,Y)
,半径为R
.1)生成所有可能
x
的列表:2)寻找潜力
y
:3)将
y
候选者缩小为整数4)重新计算距离
5)找到最大距离:
这给你
O(R)
复杂性 .我猜解决方案的大小与
R
呈线性关系,所以我认为你不能做得更好 .如果你正在寻找一个可以开始的地方,不要害怕思考“一种可能有用的坏方法” .
这是一个数学/逻辑问题,而不是计算问题,一旦你知道如何在无限时间“手动”完成这个任务,用编程语言实现它应该是解决方案的更容易的部分 .
例如...
我们的策略可能是:
列举围绕圆圈的正方形中的所有“积分点”(效率低下,但考虑到这将使你的大脑至少进入装备状态) .
1)编写一个函数,输出该正方形中所有点的列表 . 在C中,您可能希望实现
2)遍历所有点 . 弄清楚哪些点实际上在圆圈中(/上),并“记住”哪个点具有最大距离 . 您可能希望实现以下辅助函数:
提示:如何知道一个点与圆心的距离有助于我们判断它是否在圆圈内?
注意:涉及浮点数/双打的计算(或更确切地说比较)需要考虑舍入 . 您可能希望使用某种"epsilon"作为容差进行比较 . 一些阅读材料,如果你有兴趣:https://randomascii.wordpress.com/2012/02/25/comparing-floating-point-numbers-2012-edition/
3)完成所有点后,您将知道要打印哪个点的x,y坐标 .