Witam,
Odświeżę temat z racji tego, że nie bardzo jestem w stanie poradzić sobie z implementacją w C#. Poczyniłem taką klasę:
using System.Linq;
namespace Algorithm
{
public class PointConvexSheath : System.Collections.Generic.List<Point>
{
public PointConvexSheath(System.Collections.Generic.List<Point> current)
{
if (current.Count < 3)
{
throw new System.ArgumentException("Too short list", "current");
}
unique = new System.Collections.Generic.List<Point>
(
);
current.ForEach
(
(target) =>
{
if
(
!unique.Exists
(
(match) => target.X == match.X && target.Y == match.Y
)
)
{
unique.Add(target);
}
}
);
if (unique.Count < 3)
{
throw new System.ArgumentException("Too short list", "unique");
}
var minY = unique.Min
(
(target) => target.Y
);
var minX =
(
from
item in unique
where
item.Y == minY
orderby
item.X
select
item.X
).First();
unique.Sort
(
new PointVectorsSort(minX, minY)
);
this.Add(unique[0]);
this.Add(unique[1]);
this.Add(unique[2]);
for (int i = 3; i < unique.Count; i++)
{
while (this.SkretPrawo(unique[i]) == false)
{
var last = this.LastOrDefault();
if (last != null)
{
this.Remove(last);
}
else
{
break;
}
}
this.Add(unique[i]);
}
}
private bool SkretPrawo(Point p3)
{
Point p2 = unique[unique.Count - 1];
Point p1 = unique[unique.Count - 2];
if (Delta(p1, p2, p3) > 0)
{
return false;
}
else
{
return true;
}
}
private decimal Delta(Point point, Point point1, Point point2)
{
return point.X * (point1.Y - point2.Y) + point1.X * (point2.Y - point.Y) + point2.X * (point.Y - point1.Y);
}
#region Definition variable
private System.Collections.Generic.List<Point> unique;
#endregion
}
}
Nestety w przypadku testowym obejmującym punkty:
addPoint(new Point(0, 0));
addPoint(new Point(0, 4));
addPoint(new Point(4, 4));
addPoint(new Point(4, 0));
addPoint(new Point(1, 3));
Uzyskuję błędny wynik.
Nie bardzo widzę gdzie zrobiłem błąd.
Pozdrawiam,
Grzegorz