Andrew's monotone chain convex hull algorithm constructs the convex hull of a set of 2-dimensional points in O(n\log n) time. I followed the steps of the algorithm and found out that it has O(n Logn) time complexity. Sorting is just finding the lowest X and then in case of equal, find the lower Y. I am not using heap or other sorts initially. On which line, does it has Log operation? More information can be found from the link provided below.
Link: 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;
