时间戳

首页 > 解决方案 > 绕线算法和浮点误差

floating-point - 绕线算法和浮点误差

问题描述

我编写了一个用于解决多边形问题中的点的缠绕算法的 Java 实现。

这是代码：

public boolean isPointInsidePolyline(final Vec3D pt) {
    boolean isCw = this.isPolylineClockwise();
    float count = 0;
    for (Line line : this.getLines()) { // gets all the line segments of the polyline
        if (line.contains(pt)) { // checks if the point is located on the line
            return false;
        }
        Vec3D pt1 = line.getStart();
        Vec3D pt2 = line.getEnd();
        Vec3D dir1 = pt1.sub(pt).normalize();
        Vec3D dir2 = pt2.sub(pt).normalize();
        float angle = dir1.angleBetween(dir2);
        if (dir1.dot(dir2) < 1) {
            if (angle != 0) {
                if (Points.isPointSequenceClockwise(
                    Arrays.asList(pt,pt1,pt2)) == isCw
                ) {
                    count += angle;
                } else {
                    count -= angle;
                }
            }
        }
    }
    return count > eps; // eps = 0.001f;
}

使用的向量库来自toxiclibs。

该算法总体上似乎运行良好，但我遇到了由于计算中的浮点错误而失败的边缘情况。仅更改 eps 值似乎不是一个可靠的解决方案，因为 epsilon 值不是基于某些东西。

我想问一下遇到类似问题的其他人是否已经设法找到更好的解决方案来减轻浮点错误。

示例数据来演示下面失败的示例。

折线（由其带有 x,y,z 坐标的点描述）：

-199.21376f, -2.1003783E-5f, 0,
-204.51433f, -1.302136E-4f, 0,
-204.79602f, -6.259075E-6f, 0,
-212.74092f, 7.808674E-8f, 0,
-223.72076f, 1.8734062E-6f, 0,
-224.89467f, -4.392134E-6f, 0,
-225.87766f, 1.9165287E-7f, 0,
-327.65207f, 1.855702E-5f, 0,
-355.3976f, 3.3298825E-6f, 0,
-366.83472f, 3.8695987E-5f, 0,
-367.7069f, -2.677933E-5f, 0,
-368.92123f, 1.2206072E-4f, 0,
-370.22495f, 2.6854828E-5f, 0,
-371.65765f, 3.9196784E-5f, 0,
-399.56082f, 3.5489844E-5f, 0,
-400.69135f, 0.013866073f, 0,
-401.04166f, 0.0067931935f, 0,
-399.67267f, 48.833225f, 0,
-398.56805f, 84.82277f, 0,
-397.50436f, 92.38736f, 0,
-397.18918f, 93.921135f, 0,
-397.0501f, 94.37826f, 0,
-395.92285f, 97.33734f, 0,
-393.09155f, 104.53852f, 0,
-392.62076f, 105.47283f, 0,
-387.8274f, 113.93879f, 0,
-387.5292f, 114.346664f, 0,
-386.7448f, 115.26469f, 0,
-379.80237f, 122.86422f, 0,
-374.12714f, 127.701904f, 0,
-372.0301f, 129.37302f, 0,
-370.6804f, 130.21136f, 0,
-365.25098f, 133.43129f, 0,
-363.58215f, 134.21275f, 0,
-357.24515f, 136.94856f, 0,
-352.32858f, 138.49944f, 0,
-348.04324f, 139.74101f, 0,
-344.63644f, 140.3836f, 0,
-340.69135f, 141.17427f, 0,
-339.6991f, 142.09425f, 0,
-337.85547f, 143.91138f, 0,
-336.91998f, 150.82086f, 0,
-336.6831f, 151.84744f, 0,
-335.75406f, 151.8479f, 0,
-335.27155f, 151.84789f, 0,
-327.8963f, 151.84781f, 0,
-290.45605f, 151.84741f, 0,
-286.98816f, 138.05928f, 0,
-285.6575f, 132.89183f, 0,
-282.18118f, 120.361824f, 0,
-280.883f, 116.26616f, 0,
-281.07944f, 113.260635f, 0,
-281.1565f, 105.80201f, 0,
-281.10834f, 103.23026f, 0,
-280.75845f, 92.780136f, 0,
-237.04051f, 92.7801f, 0,
-215.375f, 92.77999f, 0,
-199.18573f, 92.78001f, 0,
-199.20132f, 65.52554f, 0,
-199.23079f, 8.813348f, 0,
-199.21376f, -2.1003798E-5f, 0

我检查包含的点有坐标 (201.28201f, 2.0f, 0)

只需查看最小和最大 x 坐标，我们可以很容易地看到该点不在折线内，但我编写的单元测试仍然返回 true。

标签： floating-pointprecisioncomputational-geometrypoint-in-polygon

解决方案

由于浮点表示，多边形中的点问题一直很棘手。特别是，当点非常接近时，测试点位于边缘的哪一侧是不明确的。使用公差确实不是解决方案，因为值的选择是任意的（您事先不知道顶点本身的准确度），而这只是解决了问题：接近公差限制的点也是模棱两可的。测试点对齐很困难。

另一方面，我不喜欢缠绕数算法有两个原因：

  • 它使用昂贵的反三角函数，
  • 错误分析很困难。

我更喜欢简单的半线方法：

  • 考虑测试点的水平线；
  • 找到所有穿过这条线的多边形边。测试简单快速，基于纵坐标比较；
  • 对于所有交叉边，确定测试点位于与线相交的左侧还是右侧。这需要 2x2 行列式计算（无需显式计算交集）；
  • 如果交叉点的数量是奇数，则该点在内部。

我并不是说这种方法可以避免歧义问题（这是永远存在的）。无论如何，它提供了更好的安全性，更容易解释，并且成本低。如果您通过为每个顶点分配“上方”或“下方”状态（但没有“开启”状态）来检测交叉，那么无论配置如何，都可以保证交叉边的数量是偶数。该算法永远不会失败（而当测试点是顶点时，绕组数无法得出结论）。

更新：

抱歉，我没有注意到您正在解决 3D 问题。（在 3D 中，多边形实际上并不是完全平坦的，这可能会导致额外的歧义：一个点不能被分类为倾斜多边形内部或外部）。您可以通过将所有点投影到平面（例如坐标平面或最佳拟合平面）来解决此问题。

推荐阅读