使用绕组编号指向多边形

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

这个问题已被多次询问和回答。 有多种方法可用于确定点是否在多边形内。

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

所以，要将这个问题专门改为我将继续提供的答案：

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

Answer 1

我用作起点的答案是由Manuel Castro在以下SO线程Geo Fencing中提供的 – 指向内/外多边形 ：

public static bool PointInPolygon(LatLong p, List 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 <= Py 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 > Py (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 { 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 { 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 { 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 _points; public Polygon(List 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(_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）

和：

5. 面向对象;
6. 除了保护条款外，不使用;
7. 是不可改变的;
8. 隐藏其私人数据;
9. 有完整的测试覆盖率;
10. 有一种方法，圈复杂度为3，而大多数方法都是1，其中一些是2。

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

我希望这有助于一些像我一样的人在他周围缠绕时遇到一些困难。

干杯