5 or more points on line segments in FastCollinearPoints

[vladkinoman]

Correctness bug in FastCollinearPoints of 1-3-collinear-points assignment

Description

The program fails on the test cases with 5 or more on some line segments. I actually thought that I was able to prevent this problem from happening.

To reproduce

Test 5a: points from a file with 5 or more on some line segments

• filename = input9.txt

• filename = input10.txt

• filename = input20.txt

  • segments() contains a subsegment of a segment in reference solution
  • student segment 2: (5120, 20992) -> (8128, 20992)
  • reference segment 0: (4096, 20992) -> (5120, 20992) -> (6144, 20992) -> (7168, 20992) -> (8128, 20992)
  • number of entries in student solution: 9
  • number of entries in reference solution: 5
  • 4 extra entries in student solution, including:
    '(5120, 29184) -> (8192, 29184)'

• filename = input50.txt

• filename = input80.txt

  • segments() contains a subsegment of a segment in reference solution
  • student segment 27: (28000, 14000) -> (13000, 29000)
  • reference segment 3: (30000, 12000) -> (28000, 14000) -> (26000, 16000) -> (23000, 19000) -> (13000, 29000)
  • number of entries in student solution: 32
  • number of entries in reference solution: 31
  • 1 extra entry in student solution:
    '(28000, 14000) -> (13000, 29000)'

• filename = input300.txt

• filename = inarow.txt

  • segments() contains the same segment more than once
  • segment 0: (0, 0) -> (30000, 0)
  • segment 3: (0, 0) -> (30000, 0)
  • segments() contains a subsegment of a segment in reference solution
  • student segment 4: (0, 0) -> (0, 11000)
  • reference segment 4: (0, 0) -> (0, 5000) -> (0, 10000) -> (0, 11000) -> (0, 15000) -> (0, 20000) -> (0, 25000) -> (0, 30000)
  • number of entries in student solution: 9
  • number of entries in reference solution: 5
  • 4 extra entries in student solution, including:
    '(10000, 3100) -> (25000, 12400)'

==> FAILED

Test 5b: points from a file with 5 or more on some line segments

• filename = kw1260.txt

  • segments() contains the same segment more than once
  • segment 37: (15267, 11395) -> (15407, 11815)
  • segment 39: (15267, 11395) -> (15407, 11815)
  • segments() contains a subsegment of a segment in reference solution
  • student segment 7: (16507, 473) -> (16666, 1529)
  • reference segment 253: (16454, 121) -> (16507, 473) -> (16560, 825) -> (16613, 1177) -> (16666, 1529)
  • number of entries in student solution: 413
  • number of entries in reference solution: 288
  • 125 extra entries in student solution, including:
    '(15979, 30308) -> (14764, 30467)'

• filename = rs1423.txt
  ==> FAILED

A possible solution

It would be nice to double-check the algorithm in the constructor of the FastCollinearPoints class. Roughly speaking, it would be so difficult to fix :)

Because I spent two days on writing this algorithm.