巻線番号を使用してポリゴン内のポイント

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でありながら、3の循環的複雑度を持つ一つの方法を持っており、それらのいくつかは、今2

であり、私はそれがあるとは言わないよ、と述べているすべての提案されるかもしれない追加のリファクタ、または上記のリファクタが完全に近づくことはありません。しかし、私はポイントがポリゴンにあるかどうかを判断するための巻数アルゴリズムを実装するという点で、これが有用であるというアルゴリズムを本当に理解していると思います。

これは、私のように誰かが頭の中に頭を包み込むのに苦労した人に役立つことを願っています。

乾杯