La réponse que je comme point de départ a été fourni par Manuel Castro dans les domaines suivants 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;
}
Je continuai d'écrire des tests xUnit autour d'une mise en œuvre qui a commencé à l'aide de la logique exacte exprimée dans la code ci-dessus. Ce qui suit est un peu exagéré, mais j'ai préféré plus de tests pour m'assurer que le refactoring ne créerait pas de problèmes. Utiliser des données inline dans les théories xUnit est si facile, hein, pourquoi pas. Avec tous les tests verts, j'ai alors pu factoriser au contenu de mon cœur:
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);
}
}
}
Cela m'a permis de Refactor le code d'origine à ce qui suit:
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;
}
}
Le code d'origine, bien sûr, est beaucoup moins verbeux. Cependant, il:
- est procédural;
- utilise des noms de variables qui ne révèlent pas l'intention;
- est mutable;
- a une complexité cyclomatique de 12.
Le code refactorisé:
- passe les tests;
- révèle l'intention;
- ne contient pas de duplication;
- contient les éléments plus petit nombre de données (1, 2 et 3, ci-dessus)
Et:
- est orienté objet;
- ne pas utiliser si sauf pour les clauses de garde;
- est immuable;
- masque ses données privées;
- a une couverture de test complète;
- a une méthode avec une complexité cyclomatique de 3, alors que la plupart des méthodes sont à 1, et certains d'entre eux sont à 2.
Maintenant, tout ce que dit, je ne dis pas qu'il y n'y a-t-il pas de refacteurs supplémentaires qui pourraient être suggérés, ou que le réfacteur ci-dessus approche la perfection. Cependant, je pense qu'en termes de mise en œuvre de l'algorithme de numéro d'enroulement pour déterminer si un point est dans un polygone et vraiment comprendre l'algorithme que cela est utile.
J'espère que cela aidera ceux qui, comme moi, ont eu du mal à envelopper la tête.
Cheers