使用缠绕数点在多边形中

Question

问题是：如何判断一个点是否在多边形内？

这个问题已经被问过很多次了。有多种判断点是否在多边形内的方法。

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

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

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

Answer 1

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

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;
    }
}

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

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

重构代码：

通过测试；
表露意图；
没有重复；
包含最少的元素（上面给定的 1、2 和 3）

并且：

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

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

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

干杯

使用缠绕数点在多边形中

Point in Polygon using Winding Number

c#

oop

point

polygon

geolocation