c# - Point in Polygon using Winding Number -
the question is: how determine if point within polygon?
this question has been asked , answered many times. there multiple methods determining whether point within polygon.
i've grokked winding number algorithm, ported solid answer thread c# , written xunit tests around ensure refactor ruthlessly. goal take answer, of seem use procedural programming approach , variable names similar you'd find in mathematical formula, , refactor reasonably sound set of oop classes , methods.
so, rephrase question answer go on provide:
how determine if location / point (latitude , longitude) within polygon in oop c#?
the answer used starting point provided manuel castro in following 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; // winding number counter // loop through edges of polygon (int = 0; < n; i++) { // edge v[i] v[i+1] if (v[i].lat <= p.lat) { // start y <= p.y if (v[i + 1].lat > p.lat) // upward crossing if (isleft(v[i], v[i + 1], p) > 0) // p left of edge ++wn; // have valid intersect } else { // start y > p.y (no test needed) if (v[i + 1].lat <= p.lat) // downward crossing if (isleft(v[i], v[i + 1], p) < 0) // p right of edge --wn; // have valid down intersect } } if (wn != 0) return true; else return false; } i proceeded write xunit tests around implementation started out using exact logic expressed in above code. following bit overkill, preferred more tests ensure refactoring not create issues. using inline data in xunit theories easy, eh, why not. tests green, able refactor 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 refactor original code 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; (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, creation of 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, far less verbose. however, it:
- is procedural;
- uses variable names not reveal intent;
- is mutable;
- has cyclomatic complexity of 12.
the refactored code:
- passes tests;
- reveals intention;
- contains no duplication;
- contains fewest elements (given 1, 2 , 3, above)
and:
- is object oriented;
- does not use if except guard clauses;
- is immutable;
- hides private data;
- has complete test coverage;
- has 1 method cyclomatic complexity of 3, while of methods @ 1, , few of them @ 2.
now, said, i'm not saying there no additional refactors might suggested, or above refactor approaches perfection. however, think in terms of implementing winding number algorithm determining whether point in polygon , understanding algorithm helpful.
i hope helps who, me, had difficulty wrapping heads around it.
cheers
Comments
Post a Comment