How to Sorting?

Nov 20, 2012 at 7:58 AM

Dears

I wonder how work for Graham scan algorithm, so I try to trace the C# code. Before doing Graham scan algorithm, we should sorting all points. My question is how to sorting?

Check the following code, (P.S. In CCT.NUI.Core.Shape.GrahamScan.cs)

        private IList<Point> SortPointsByAngle()
        {
            var p0 = this.FindMinimalOrdinatePoint();
            var comparer = new PointAngleComparer2D(p0);
            var sortedPoints = new List<Point>(this.points);
            sortedPoints.Remove(p0);
            sortedPoints.Insert(0, p0);
            sortedPoints.Sort(1, sortedPoints.Count - 1, comparer);
            return sortedPoints;
        }

the red line, I know sorting from point 1 to Count-1 and use comparer sorting. In class PointAngleComparer2D, I can found the comparing method (means comparer).From document (http://msdn.microsoft.com/en-us/library/8ce6t5ad.aspx), it's also tell me it's binary search.

But, I don't know the detail about how to getting the two points (by binary search? how to select the two point? ) and compare (by comparer?) sorting and then get the final result.  Does somebody tell me the detail? Or tell me where to get the detail information. Thanks!

 

Coordinator
Nov 20, 2012 at 5:47 PM

FindMinimalOrdinatePoint will look for the point with the lowest x / y combination, which is the "zero" point. The PointAngleComparer2D takes two points and calculates the angle between the "zero" point and the two selected points. The Sort() method will repeat the process until the list is sorted.

Sort is implemented (as you found out) in the list class (which itself uses Array.Sort). The algorithm is not binary search but quick sort.

- Stefan

Nov 23, 2012 at 7:30 AM

Dear Stefan,

I wonder the method for sorting point sequence for Graham Scan. so, I try to run step by step by binary sort by manual. From MSDN's document, it tells me to use binary sorting. It's why I use it. I compared the C# program result to my manual operating result. It doesn't match. It's why I ask you this question. Well, I will try to use quick sort and double check it again! thanks for your reply.

- tasi tsai