java - 使用 java/android 中的给定点绘制凸包

Question

我有一些二维点，我想用这些点绘制一个多边形。这个多边形必须通过所有给定的点，这意味着多边形内部或外部没有这样的点。

例如：如果我有如下点：(0,0)、(1,1)、(-1,-1)、(-1,1) 和 (1,-1)，如果我想绘制多边形使用那些然后我的点数组应该按以下方式排序：

(1,1) -> (1,-1) -> (-1,-1) -> (-1,1) -> (0,0) -> (1,1) 或

(1,1) -> (0,0) -> (-1,1) -> (-1,-1) -> (1,-1) -> (1,1)

但它不能是：

(1,1) -> (0,0) -> (-1,-1) -> (-1,1) -> (-1,1) -> (1,-1) -> (1, 1)

为了绘制多边形，我使用drawLine函数并从一个点画线到另一个点，最后从最后一个点画到第一个点。

有没有可用的算法或代码？

谢谢！！

Answer 1

I think your problem is not as trivial as it seems. IMHO its a special form of the travelling salesman problem, but without intersecting paths.

Answer 2

在 google 中快速搜索：凸包算法，这里是Java 实现。

编辑：重新阅读您的问题并意识到这不是您想要的。标题“凸壳”可能会产生误导......