代码之家  ›  专栏  ›  技术社区  ›  Eric

凸壳-单调链算法错误

convex-hull polygon 2d python javascript
  •  0
  • Eric  · 技术社区  · 13 年前

    我正在使用 Monotone chain algorithm 以围绕一组多边形创建凸包。它有时效果很好,但在某些形状上却失败了。看看这个例子: http://i.imgur.com/KN40LgV.png

    左边是形状 之前 应用算法,右边是 之后 。某个地方似乎有一些小的计算错误,我想不出来。

    以下是我的源代码(JavaScript)链接: http://pastebin.com/GPVm9dQp

    下面是我用作参考的Python中的实现: http://pastebin.com/RgMKH3XN

    1 回复  |  直到 13 年前
        1
  •  1
  •   user1618143    13 年前

    如果不深入研究,你不应该在某个点上按x位置对点列表进行排序吗?

    推荐文章
    Daniel R. Livingston  ·  用凹域三角化一组点
    8 年前
    Lou  ·  矩形周围的有效凸包(并检查点是否位于包内)
    11 年前
    Eric  ·  凸壳-单调链算法错误
    13 年前
    关于   移动版
    代码之家 - 一站式码农服务社区
    沪ICP备11025650号