The convexhull from allfii

convexhull's People

Stargazers

Watchers

convexhull's Issues

infinite loop (jarvis)

the following test fails for the Jarvis Match, while it run ok for the Grahams
all point coordinates are in the range of Int.MaxValue

static void Main(string[] args)
        {
            var listPoints = new List<Point>();
            listPoints.Add(new Point(0, 472420000));
            listPoints.Add(new Point(125490000, 1542750000));
            listPoints.Add(new Point(701250000, 974370000));
            listPoints.Add(new Point(1151530000, 575760000));
            listPoints.Add(new Point(1446790000, 0));
            listPoints.Add(new Point(1564899999, 1719899999));
            listPoints.Add(new Point(1933980000, 435510000));            

            // int.MaxValue = 2147483647

            {
                GrahamScan gs = new GrahamScan();

                var stopwatch = new Stopwatch();
                stopwatch.Start();
                gs.convexHull(listPoints);
                stopwatch.Stop();
                float elapsed_time = stopwatch.ElapsedMilliseconds;
                Console.WriteLine("Elapsed time: {0} milliseconds", elapsed_time);
                Console.WriteLine("Press enter to close...");
                Console.ReadLine();
            }

            {
                JarvisMatch jm = new JarvisMatch();

                var stopwatch = new Stopwatch();
                stopwatch.Start();
                jm.convexHull(listPoints);
                stopwatch.Stop();
                float elapsed_time = stopwatch.ElapsedMilliseconds;
                Console.WriteLine("Elapsed time: {0} milliseconds", elapsed_time);
                Console.WriteLine("Press enter to close...");
                Console.ReadLine();
            }
        }

Recommend Projects