c# - 使用缠绕数点在多边形中

Question

问题是:如何确定一个点是否在多边形内？

这个问题已经被问过很多次了。有多种方法可以确定一个点是否在多边形内。

我已经摸索了绕数算法，将另一个 SO 线程的可靠答案移植到 C# 中，并围绕它编写了 xUnit 测试以确保我可以无情地重构。目标是得到一个答案，所有这些似乎都使用过程编程方法和类似于您在数学公式中找到的变量名，并将其重构为一组合理合理的 OOP 类和方法。

因此，将这个问题具体改写为我将继续提供的答案:

如何确定位置/点(纬度和经度)是否在 OOP C# 中的多边形内？

Answer 1

我用作起点的答案是由 Manuel Castro 提供的在以下 SO 线程中 Geo Fencing - point inside/outside polygon :

public static bool PointInPolygon(LatLong p, List<LatLong> poly)
{
    int n = poly.Count();

    poly.Add(new LatLong { Lat = poly[0].Lat, Lon = poly[0].Lon });
    LatLong[] v = poly.ToArray();

    int wn = 0;    // the winding number counter

    // loop through all edges of the polygon
    for (int i = 0; i < n; i++)
    {   // edge from V[i] to V[i+1]
        if (v[i].Lat <= p.Lat)
        {         // start y <= P.y
            if (v[i + 1].Lat > p.Lat)      // an upward crossing
                if (isLeft(v[i], v[i + 1], p) > 0)  // P left of edge
                    ++wn;            // have a valid up intersect
        }
        else
        {                       // start y > P.y (no test needed)
            if (v[i + 1].Lat <= p.Lat)     // a downward crossing
                if (isLeft(v[i], v[i + 1], p) < 0)  // P right of edge
                    --wn;            // have a valid down intersect
        }
    }
    if (wn != 0)
        return true;
    else
        return false;

}

我开始围绕一个使用上述代码中表达的确切逻辑的实现编写 xUnit 测试。以下内容有点矫枉过正，但我​​更喜欢进行更多测试以确保重构不会产生问题。在 xUnit 理论中使用内联数据是如此简单，嗯，为什么不呢。在所有测试都通过后，我便可以根据自己的喜好进行重构:

public class PolygonTests
{

    public class GivenLine : PolygonTests
    {
        private readonly Polygon _polygon = new Polygon(new List<GeographicalPoint>
        {
            new GeographicalPoint(1, 1),
            new GeographicalPoint(10, 1)
        });
        public class AndPointIsAnywhere : GivenLine
        {
            [Theory]
            [InlineData(5, 1)]
            [InlineData(-1, -1)]
            [InlineData(11, 11)]
            public void WhenAskingContainsLocation_ThenItShouldReturnFalse(double latitude, double longitude)
            {
                GeographicalPoint point = new GeographicalPoint(latitude, longitude);
                bool actual = _polygon.Contains(point);

                actual.Should().BeFalse();
            }
        }
    }

    public class GivenTriangle : PolygonTests
    {
        private readonly Polygon _polygon = new Polygon(new List<GeographicalPoint>
        {
            new GeographicalPoint(1, 1),
            new GeographicalPoint(10, 1),
            new GeographicalPoint(10, 10)
        });

        public class AndPointWithinTriangle : GivenTriangle
        {
            private readonly GeographicalPoint _point = new GeographicalPoint(6, 4);

            [Fact]
            public void WhenAskingContainsLocation_ThenItShouldReturnTrue()
            {
                bool actual = _polygon.Contains(_point);

                actual.Should().BeTrue();
            }
        }

        public class AndPointOutsideOfTriangle : GivenTriangle
        {
            private readonly GeographicalPoint _point = new GeographicalPoint(5, 5.0001d);

            [Fact]
            public void WhenAskingContainsLocation_ThenItShouldReturnFalse()
            {
                bool actual = _polygon.Contains(_point);

                actual.Should().BeFalse();
            }
        }
    }

    public class GivenComplexPolygon : PolygonTests
    {
        private readonly Polygon _polygon = new Polygon(new List<GeographicalPoint>
        {
            new GeographicalPoint(1, 1),
            new GeographicalPoint(5, 1),
            new GeographicalPoint(8, 4),
            new GeographicalPoint(3, 4),
            new GeographicalPoint(8, 9),
            new GeographicalPoint(1, 9)
        });

        [Theory]
        [InlineData(5, 0, false)]
        [InlineData(5, 0.999d, false)]
        [InlineData(5, 1, true)]
        [InlineData(5, 2, true)]
        [InlineData(5, 3, true)]
        [InlineData(5, 4, false)]
        [InlineData(5, 5, false)]
        [InlineData(5, 5.999d, false)]
        [InlineData(5, 6, true)]
        [InlineData(5, 7, true)]
        [InlineData(5, 8, true)]
        [InlineData(5, 9, false)]
        [InlineData(5, 10, false)]
        [InlineData(0, 5, false)]
        [InlineData(0.999d, 5, false)]
        [InlineData(1, 5, true)]
        [InlineData(2, 5, true)]
        [InlineData(3, 5, true)]
        [InlineData(4.001d, 5, false)]
        //[InlineData(5, 5, false)] -- duplicate
        [InlineData(6, 5, false)]
        [InlineData(7, 5, false)]
        [InlineData(8, 5, false)]
        [InlineData(9, 5, false)]
        [InlineData(10, 5, false)]
        public void WhenAskingContainsLocation_ThenItShouldReturnCorrectAnswer(double latitude, double longitude, bool expected)
        {
            GeographicalPoint point = new GeographicalPoint(latitude, longitude);
            bool actual = _polygon.Contains(point);

            actual.Should().Be(expected);
        }
    }
}

这让我可以将原始代码重构为以下内容:

public interface IPolygon
{
    bool Contains(GeographicalPoint location);
}

public class Polygon : IPolygon
{
    private readonly List<GeographicalPoint> _points;

    public Polygon(List<GeographicalPoint> points)
    {
        _points = points;
    }

    public bool Contains(GeographicalPoint location)
    {
        GeographicalPoint[] polygonPointsWithClosure = PolygonPointsWithClosure();

        int windingNumber = 0;

        for (int pointIndex = 0; pointIndex < polygonPointsWithClosure.Length - 1; pointIndex++)
        {
            Edge edge = new Edge(polygonPointsWithClosure[pointIndex], polygonPointsWithClosure[pointIndex + 1]);
            windingNumber += AscendingIntersection(location, edge);
            windingNumber -= DescendingIntersection(location, edge);
        }

        return windingNumber != 0;
    }

    private GeographicalPoint[] PolygonPointsWithClosure()
    {
        // _points should remain immutable, thus creation of a closed point set (starting point repeated)
        return new List<GeographicalPoint>(_points)
        {
            new GeographicalPoint(_points[0].Latitude, _points[0].Longitude)
        }.ToArray();
    }

    private static int AscendingIntersection(GeographicalPoint location, Edge edge)
    {
        if (!edge.AscendingRelativeTo(location)) { return 0; }

        if (!edge.LocationInRange(location, Orientation.Ascending)) {  return 0; }

        return Wind(location, edge, Position.Left);
    }

    private static int DescendingIntersection(GeographicalPoint location, Edge edge)
    {
        if (edge.AscendingRelativeTo(location)) { return 0; }

        if (!edge.LocationInRange(location, Orientation.Descending)) { return 0; }

        return Wind(location, edge, Position.Right);
    }

    private static int Wind(GeographicalPoint location, Edge edge, Position position)
    {
        if (edge.RelativePositionOf(location) != position) { return 0; }

        return 1;
    }

    private class Edge
    {
        private readonly GeographicalPoint _startPoint;
        private readonly GeographicalPoint _endPoint;

        public Edge(GeographicalPoint startPoint, GeographicalPoint endPoint)
        {
            _startPoint = startPoint;
            _endPoint = endPoint;
        }

        public Position RelativePositionOf(GeographicalPoint location)
        {
            double positionCalculation =
                (_endPoint.Longitude - _startPoint.Longitude) * (location.Latitude - _startPoint.Latitude) -
                (location.Longitude - _startPoint.Longitude) * (_endPoint.Latitude - _startPoint.Latitude);

            if (positionCalculation > 0) { return Position.Left; }

            if (positionCalculation < 0) { return Position.Right; }

            return Position.Center;
        }

        public bool AscendingRelativeTo(GeographicalPoint location)
        {
            return _startPoint.Latitude <= location.Latitude;
        }

        public bool LocationInRange(GeographicalPoint location, Orientation orientation)
        {
            if (orientation == Orientation.Ascending) return _endPoint.Latitude > location.Latitude;

            return _endPoint.Latitude <= location.Latitude;
        }
    }

    private enum Position
    {
        Left,
        Right,
        Center
    }

    private enum Orientation
    {
        Ascending,
        Descending
    }
}

public class GeographicalPoint
{
    public double Longitude { get; set; }

    public double Latitude { get; set; }

    public GeographicalPoint(double latitude, double longitude)
    {
        Latitude = latitude;
        Longitude = longitude;
    }
}

当然，原始代码远没有那么冗长。然而，它:

1. 是程序性的；
2. 使用不透露意图的变量名；
3. 是可变的；
4. 圈复杂度为 12。

重构后的代码:

1. 通过考试；
2. 表明意图；
3. 不包含重复；
4. 包含最少的元素(上面给定的 1、2 和 3)

和:

1. 是面向对象的；
2. 不使用 if 除了保护子句；
3. 是不可变的；
4. 隐藏其私有(private)数据；
5. 具有完整的测试覆盖率；
6. 有一种方法的圈复杂度为 3，而大多数方法的圈复杂度为 1，少数为 2。

现在，综上所述，我并不是说没有可能建议的额外重构，或者上述重构接近完美。但是，我认为在实现用于确定点是否在多边形中的绕数算法以及真正理解该算法方面，这是有帮助的。

我希望这对像我一样难以理解它的人有所帮助。

干杯