ios - 如何创建嵌入多边形的圆形地理围栏区域以进行地理围栏？

Question

我正在尝试为 IOS 实现多边形地理围栏的最佳方式。我已经提到了这个question

我正在尝试第一种方法。我需要一些代码方面的帮助来实现该方法。

如何使用多边形坐标创建圆形地理围栏区域？有没有算法可以创建一个嵌入多边形坐标的圆形区域？

任何帮助将不胜感激。谢谢!

Answer 1

您面临的问题称为最小圆问题。

本质上，您正在寻找包含点列表的最小圆。

谷歌搜索一下发现它可以在线性时间内完成。

算法是这样描述的...

The algorithm processes the points of S in a random order, maintaining as it does the set P of processed points and the smallest circle that encloses the union of P and Q. At each step, it tests whether the next point r to be processed belongs to this circle; if it does not, the algorithm replaces the enclosing circle by the result of a recursive call of the algorithm on the sets P and Q+r. Whether the circle was replaced or not, r is then included in the set P. Processing each point, therefore, consists of testing in constant time whether the point belongs to a single circle and possibly performing a recursive call to the algorithm. It can be shown that the ith point to be processed has probability O ( 1 / i ) O(1/i) of generating a recursive call, and therefore that the overall time is linear.

Here is the Wikipedia link about the problem.

您可能可以从这里找到更多有关此问题的资源。

希望对您有所帮助。

Here is another site that possibly provides a more complete solution