使用缠绕数的多边形中的点

作为起点的答案是 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;

}

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. 使用不显示意图的变量名;
4. 圈复杂度为12。

重构代码:

3. 不包含重复项;
4. 包含最少的元素(上面给出了1、2和3)

以及:

6. 除保护条款外,不使用if;
7. 是不变的;
9. 具有完整的测试覆盖范围;

尽管如此,我并不是说没有其他重构可以推荐,或者上述重构接近完美。然而,我认为在实现用于确定点是否在多边形中的缠绕数算法方面,并真正理解该算法,这是有帮助的。

我希望这能帮助一些像我这样的人,让他们的头脑在这个问题上有些困难。

干杯