Find collinear points among the n points on an n/x-by-x grid

[vladkinoman]

Performance bug in FastCollinearPoints of 1-3-collinear-points

Description

The FastCollinearPoints program works too slowly on the n/x-by-x grid.

Honestly, I do not quite understand why we have this grid for input :)

To reproduce

Test 3a-3g: Find collinear points among the n points on an n/4-by-4 grid

                                                  slopeTo()
             n    time     slopeTo()   compare()  + 2*compare()        compareTo()

=> passed    64   0.00       20324        7872          36068                 3118         
=> passed   128   0.01      214318       34175         282668                14897         
=> FAILED   256   0.07     2708030      132057        2972144   (1.4x)       52816         
=> FAILED   512   0.31    35608708      509849       36628406   (4.5x)      206370         
=> FAILED  1024   3.10   524447536     1909013      528265562  (16.9x)      775409         
=> FAILED  2048  45.30  7992559915     7477683     8007515281  (65.0x)     3131084         

Aborting: time limit of 10 seconds exceeded

Test 4a-4g: Find collinear points among the n points on an n/8-by-8 grid

                                                  slopeTo()
             n    time     slopeTo()   compare()  + 2*compare()        compareTo()

=> passed    64   0.00       45754        8245          62244                 3359         
=> passed   128   0.01      515345       39394         594133                13642         
=> FAILED   256   0.06     5980029      176512        6333053   (2.1x)       54747         
=> FAILED   512   0.63    77017630      748450       78514530   (7.0x)      216019         
=> FAILED  1024   7.69  1151489287     3042167     1157573621  (26.9x)      819130         
=> FAILED  2048 102.78 17599604722    12320852    17624246426 (104.4x)     3277980         

Aborting: time limit of 10 seconds exceeded

A possible solution

I guess it would be nice to double-check the inner loops in the FastCollinearPoints constructor. Some of them could be optimized.