Point in polygon using winding number

Question

The question arises: how do you determine if a point is inside a polygon?

This question has been asked and answered many times. There are many methods for determining if a point is inside a polygon.

I tested the Winding Number algorithm, put a solid answer from another SO thread in C #, and wrote xUnit tests around it so that I could reorganize mercilessly. The goal was to accept the answer, all of which seem to use a procedural approach to programming and variable names that are similar to those you find in the mathematical formula, and reorganize them into a reasonably sound set of OOP classes and methods.

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

How to determine if a location / point (latitude and longitude) is inside a polygon in OOP C #?

Answer 1

The answer I used as a starting point was provided by Manuel Castro in the following SO Geo Fencing - point stream inside / outside the 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 <= 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; } 

I started writing xUnit tests around an implementation that started by using the exact logic expressed in the code above. The following are a bit overkill, but I prefer more tests so that refactoring does not cause problems. Using embedded data in xUnit theories is so easy, why not. When all the tests were green, I was able to reorganize my heart:

 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 source code into 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 source code is, of course, much less verbose. However, he:

• is procedural;
• Uses variable names that do not display intent.
• is mutable;
• has cyclomatic complexity 12.

Reorganized Code:

• passes tests;
• shows intention;
• does not contain duplication;
• contains the smallest elements (taking into account 1, 2 and 3, above)

and

5. is object oriented;
6. not used unless for defensive offers;
7. is unchanged;
8. hides his personal data;
9. has full testing coverage;
10. has one method with cyclic complexity of 3, while most methods are in 1, and some of them are 2.

Now, all that is said, I am not saying that there are no additional refactors that can be offered, or that the above refactor is perfect. However, I think that from the point of view of implementing the Winding Number algorithm to determine whether a point is in a polygon and whether it really understands the algorithm, this is useful.

I hope this helps those who, like me, have difficulty wrapping them around them.

Greetings