使用绕组编号指向多边形 [英] Point in Polygon using Winding Number

问题描述

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

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

我已经习惯了绕线数算法，从另一个SO线程移植到C＃中并写入了一个可靠的答案并写入了xUnit围绕它进行测试，以确保我可以无情地重构。目标是得到一个答案，所有这些似乎都使用程序化编程方法和变量名称，这些名称与您在数学公式中找到的类似，并将其重构为一套合理的OOP类和方法。 / p>

所以，为了更详细地解释这个问题，我将继续提供：

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

解决方案

我的出发点是由 Manuel Castro 在以下SO线程 Geo Fencing - 指向内部/外部多边形
：

 
 $ n $ poly $（pre $ p $） 
 
 poly.Add（new LatLong {Lat = poly [0] .Lat，Lon = poly [0] .Lon}）; 
 LatLong [] v = poly.ToArray（）; 
 
 int wn = 0; //绕组编号计数器
 
 //循环遍历多边形的所有边
 for（int i = 0; i  {// edge from如果（v [i] .Lat <= p.Lat）
 {//开始y <= Py 
 if（v [i]到V [i + 1] （v [i]，v [i + 1]，p）> 0）// P向左边缘
 ++ wn; //有一个有效的相交
} 
 else 
 {// start y> Py（不需要测试）
 if（v [i + 1] .Lat <= p.Lat）//向下穿越
 if（isLeft（v [i]，v [i + 1 ]，p）<0）// P边缘右边
 --wn; //有一个有效的向下相交
} 
} 
 if（wn！= 0）
 return true; 
 else 
返回false; 
 
 
 
 
 $ b我开始编写xUnit测试，使用上面代码中表达的确切逻辑。以下是有点矫枉过正，但我​​更喜欢更多的测试，以确保重构不会产生问题。在xUnit理论中使用内联数据非常简单，呃，为什么不呢。所有的测试都是绿色的，然后我可以重构我心中的内容： 
 
 
  public class PolygonTests 
 {
 
 public class GivenLine：PolygonTests 
 {
 private只读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（）; 
 
 
 
 $ b公共类GivenTriangle：PolygonTests 
 {
 private readonly Polygon _polygon = new Polygon（new List< GeographicalPoint> 
 {
新GeographicalPoint（1,1），
新地理点（10,1），
新地理点（10,10）
}）; 
 
 public class AndPointWithinTriangle：GivenTriangle 
 {
 private只读GeographicalPoint _point = new GeographicalPoint（6，4）; 
 
 [Fact] 
 public void WhenAskingContainsLocation_ThenItShouldReturnTrue（）
 {
 bool actual = _polygon.Contains（_point）; 
 
 actual.Should（）。BeTrue（）; 
 
 
 
公共类AndPointOutsideOfTriangle：GivenTriangle 
 {
 private readonly GeographicalPoint _point = new GeographicalPoint（5，5.0001d）; 
 
 [Fact] 
 public void WhenAskingContainsLocation_ThenItShouldReturnFalse（）
 {
 bool actual = _polygon.Contains（_point）; 
 
 actual.Should（）。BeFalse（）; 
 
 
 
 $ b公共类GivenComplexPolygon：PolygonTests 
 {
 private readonly Polygon _polygon = new Polygon（new List< GeographicalPoint> 
 {
新的GeographicalPoint（1,1），
新的GeographicalPoint（5,1），
新的GeographicalPoint（8,4），
新的GeographicalPoint（3， 4），
新地理点（8,9），
新地理点（1，9）
}）; 
 
 [理论] 
 [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， （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）; 
} 
 
公共类多边形：IPolygon 
 {
私有只读列表< GeographicalPoint> _points; 
 
 public Polygon（List< GeographicalPoint> points）
 {
 _points = points; 
 
 $ b公共bool包含（GeographicalPoint位置）
 {
 GeographicalPoint [] polygonPointsWithClosure = PolygonPointsWithClosure（）; 
 
 int windingNumber = 0; 
 
（int pointIndex = 0; pointIndex< polygonPointsWithClosure.Length  -  1; pointIndex ++）
 {
 Edge edge = new Edge（polygonPointsWithClosure [pointIndex]，polygonPointsWithClosure [pointIndex + 1]）; 
 windingNumber + = AscendingIntersection（location，edge）; 
 windingNumber  -  = DescendingIntersection（位置，边缘）; 
} 
 
返回windingNumber！= 0; 
 
 $ b $ private GeographicalPoint [] PolygonPointsWithClosure（）
 {
 // _points应该保持不变，从而创建一个闭点集合（重复出发点）
返回新的列表< GeographicalPoint>（_ points）
 {
 new GeographicalPoint（_points [0] .Latitude，_points [0] .Longitude）
} .ToArray（）; 
 
 $ b $ private static int AscendingIntersection（GeographicalPoint location，Edge edge）
 {
 if（！edge.AscendingRelativeTo（location））{return 0; } 
 
 if（！edge.LocationInRange（location，Orientation.Ascending））{return 0; } 
 
返回Wind（location，edge，Position.Left）; 
 
 $ b $ 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; 
} 
 
私人类边缘
 {
私人只读GeographicalPoint _startPoint; 
私有只读GeographicalPoint _endPoint; 
 
 public Edge（GeographicalPoint startPoint，GeographicalPoint endPoint）
 {
 _startPoint = startPoint; 
 _endPoint = endPoint; 
 
 
位置RelativePositionOf（GeographicalPoint位置）
 {
 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; 
 
 $ b $ public bool LocationInRange（GeographicalPoint location，Orientation orientation）
 {
 if（orientation == Orientation.Ascending）return _endPoint.Latitude> location.Latitude; 
 
 return _endPoint.Latitude< = location.Latitude; 
} 
} 
 
私有枚举位置
 {
离开，
对，
中心
} 
 
私有枚举定向
 {
递增，
递减
} 
} 
 
公共类地理位置
 {
 public double Longitude {get;组; } 
 
 public double Latitude {get;组; } 
 
 public GeographicalPoint（双纬度，双倍经度）
 {
纬度=纬度; 
经度=经度; 
} 
} 
  
当然，原始代码要少得多。但是，它：
 $ b $ ol 
 
是程序性的; 
 
使用不显示意图的变量名; 
 / li> 
 
是可变的; 
 
具有12的圈复杂度。 
 
重构后的代码：
 $ b 
 
 
通过测试; 
 
显示意图; 
 li> 
 
不包含重复; 
 
包含最少的元素（给出上面的1,2和3）
 
 
 
 
和：
 
 
 
 
是面向对象的; 
 $ b如果除了guard子句，$ b 
不会使用; 
 
是不可变的; 
 
隐藏其私有数据; 
 
具有完整的测试覆盖率; 
 
有一个方法，其复杂度为3，而大多数方法为1，其中一些方法为2。 / li> 
 
现在，我所说的并不是说没有可能会提出的额外重构，或者上述重构方法完美。不过，我认为就实现绕线数算法来说，它是用来确定一个点是否在一个多边形中，并且真正理解这个算法是有用的。
 
 
 
我希望这有助于像我这样的人在围绕它时遇到困难。
 
 
 
干杯
 
The question is: how do you determine if a point is within a polygon?

This question has been asked and answered many times. There are multiple methods for determining whether a point is within a polygon.

I've grokked the Winding Number algorithm, ported a solid answer from another SO thread into C# and written xUnit tests around it to ensure that I could refactor ruthlessly. The goal was to take an answer, all of which seem to use a procedural programming approach and variable names that are similar to those you'd find in a mathematical formula, and refactor it into a reasonably sound set of OOP classes and methods.

So, to rephrase this question specifically to the answer that I will go on to provide:

How do I determine if a location / point (latitude and longitude) is within a polygon in OOP C#?
解决方案
The answer that I used as my starting point was provided by Manuel Castro in the following SO thread 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;

}
I proceeded to write xUnit tests around an implementation that started out using the exact logic expressed in the above code. The following are a bit overkill, but I preferred more tests to ensure that refactoring would not create issues. Using inline data in xUnit theories is so easy, eh, why not. With all the tests green, I was then able to refactor to my heart's content:
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);
        }
    }
}
This allowed me to refactor the original code to the following:
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;
    }
}
The original code, of course, is far less verbose. However, it:

is procedural;
uses variable names that do not reveal intent;
is mutable;
has a cyclomatic complexity of 12.
The refactored code:

passes the tests;
reveals intention;
contains no duplication;
contains the fewest elements (given 1, 2 and 3, above)
And:

is object oriented;
does not use if except for guard clauses;
is immutable;
hides its private data;
has complete test coverage;
has one method with a cyclomatic complexity of 3, while most of the methods are at 1, and a few of them are at 2.
Now, all that said, I'm not saying that there are no additional refactors that might be suggested, or that the above refactor approaches perfection. However, I think that in terms of implementing the Winding Number algorithm for determining whether a point is in a polygon and really understanding the algorithm that this is helpful.

I hope that this helps some who, like me, had some difficulty wrapping their heads around it.

Cheers

                        
这篇关于使用绕组编号指向多边形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！