Алгоритм Эндрю для выпуклой оболочки с монотонной цепью строит выпуклую оболочку из набора двумерных точек за O (n \ log n) времени. Я следовал за шагами алгоритма и обнаружил, что у него есть O (n Logn) временная сложность. Сортировка - это просто поиск самого низкого значения X, а затем, в случае равного, определение более низкого значения Y. Сначала я не использую кучу или другие сортировки. На какой линии он работает Log ? Дополнительную информацию можно найти по приведенной ниже ссылке.
Ссылка: https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain
points.Sort();
if (points.Count <= 3)
{
return new List<PlaceOfInterest>(points);
}
List<PlaceOfInterest> upperHull = new List<PlaceOfInterest>();
foreach (PlaceOfInterest point in points)
{
PlaceOfInterest p2 = point;
while (upperHull.Count >= 2)
{
PlaceOfInterest pivot = upperHull[upperHull.Count - 2];
PlaceOfInterest p1 = upperHull[upperHull.Count - 1];
if (Calculation.SignedArea(pivot, p1, p2) <= 0)
{
upperHull.RemoveAt(upperHull.Count - 1);
}
else
{
break;
}
}
upperHull.Add(p2);
}
upperHull.RemoveAt(upperHull.Count - 1);
List<PlaceOfInterest> lowerHull = new List<PlaceOfInterest>();
for (int i = points.Count - 1; i >= 0; i--)
{
PlaceOfInterest p2 = points[i];
while (lowerHull.Count >= 2)
{
PlaceOfInterest pivot = lowerHull[lowerHull.Count - 2];
PlaceOfInterest p1 = lowerHull[lowerHull.Count - 1];
if (Calculation.SignedArea(pivot, p1, p2) <= 0)
{
lowerHull.RemoveAt(lowerHull.Count - 1);
}
else
{
break;
}
}
lowerHull.Add(p2);
}
lowerHull.RemoveAt(lowerHull.Count - 1);
if (!(Enumerable.SequenceEqual(upperHull, lowerHull)))
{
upperHull.AddRange(lowerHull);
}
return upperHull;