Colinearity in O(n^2 lg(n))

main.go

package main

import (
	"errors"
	"fmt"
	"io"
	"time"
)

type Point struct {
	X, Y int
}

/* CCW determines if segment p->q is counter-clockwise from segment p->r.
 * Returns -1 if counter-clockwise;
 *          0 if colinear; and
 *         +1 if clockwise
 */
func CCW(p, q, r Point) int {
	xproduct := (q.X-p.X)*(r.Y-p.Y) - (r.X-p.X)*(q.Y-p.Y)
	if xproduct > 0 {
		return -1
	}
	if xproduct < 0 {
		return +1
	}
	return 0
}

func checkColinearityCubic(points []Point) [][3]Point {
	var allColinearPoints [][3]Point

	for _, p := range points {
		for _, q := range points {
			if p == q {
				continue // Filter out p
			}
			for _, r := range points {
				if p == r || q == r {
					continue // Filter out p and q, since CCW(p,p,p) == 0
				}
				if CCW(p, q, r) == 0 {
					allColinearPoints = append(allColinearPoints, [3]Point{p, q, r})
				}
			}
		}
	}

	return allColinearPoints
}

func checkColinearity(points []Point) [][3]Point {
	var allColinearPoints [][3]Point

	for _, p := range points { // T(n) = O(n) x [
		others, _ := filter(points, p)       //   O(n)
		sorted := sort(others, p)            // + O(n lg(n))
		for i := 0; i+1 < len(sorted); i++ { // + O(n) ]
			q := sorted[i]
			r := sorted[i+1]
			if CCW(p, q, r) == 0 {
				allColinearPoints = append(allColinearPoints, [3]Point{p, q, r})
			}
		}
	}
	// = O(n^2 lg(n))

	return allColinearPoints
}

func filter(points []Point, p Point) (filtered []Point, err error) {
	position := -1
	for index, q := range points {
		if p == q {
			position = index
			break
		}
	}

	if position < 0 {
		return nil, errors.New("Point p is not in points slice")
	}

	filtered = append(filtered, points[:position]...)
	filtered = append(filtered, points[position+1:]...)

	return filtered, nil
}

func sort(points []Point, origin Point) []Point {
	if len(points) == 1 {
		return points[0:]
	}

	pivot := len(points) / 2
	left, right := points[:pivot], points[pivot:]
	return merge(sort(left, origin), sort(right, origin), origin)
}

func merge(left, right []Point, origin Point) (Merged []Point) {
	//fmt.Printf("left: %v\n", left)
	//fmt.Printf("right: %v\n", right)

	l, r := 0, 0

	for l < len(left) && r < len(right) {
		if CCW(origin, left[l], right[r]) < 0 {
			Merged = append(Merged, left[l])
			l++
		} else {
			Merged = append(Merged, right[r])
			r++
		}
	}

	if r < len(right) {
		Merged = append(Merged, right[r:]...)
	}

	if l < len(left) {
		Merged = append(Merged, left[l:]...)
	}

	//fmt.Printf("Merged: %v\n\n", Merged)
	return
}

func readPoints() (points []Point) {
	var p Point

	for {
		if _, err := fmt.Scanf("%d %d\n", &p.X, &p.Y); err != nil {
			if err == io.EOF {
				break
			}

			fmt.Println("Bad input. Ignoring.")
			continue
		}

		points = append(points, p)
	}

	return
}

func main() {
	fmt.Println("Input N 2-D points (coordinates separated by a space, points by new line)")
	fmt.Println("300 200")

	points := readPoints()
	fmt.Printf("%v\n", points)

	start := time.Now()
	colinears := checkColinearityCubic(points)
	fmt.Printf("%v\n", colinears)
	done := time.Since(start)

	start2 := time.Now()
	colinears = checkColinearity(points)
	fmt.Printf("%v\n", colinears)
	done2 := time.Since(start2)

	fmt.Println()
	fmt.Printf("done: %v\n", done)
	fmt.Printf("done2: %v\n", done2)
}

pts.741

503	137
647	320
143	478
547	979
952	609
400	828
882	517
48	633
620	401
970	425
501	418
223	324
314	725
967	510
330	68
646	453
943	631
335	76
552	760
483	525
187	897
918	155
250	3
645	256
250	80
112	798
795	820
914	602
172	959
110	697
545	990
263	749
186	281
381	806
914	342
676	841
986	311
738	325
248	937
88	484
718	876
402	743
199	47
164	418
731	240
473	623
322	6
275	8
253	980
653	255
200	358
894	630
211	252
480	511
421	276
492	331
907	96
903	981
886	17
958	692
776	700
634	148
237	692
922	347
805	784
551	632
784	902
999	816
703	509
497	785
641	515
770	21
349	281
379	737
329	298
922	787
448	800
486	698
80	16
729	771
575	789
135	827
363	440
558	220
1	15
189	532
246	462
678	692
602	81
395	382
881	268
570	943
448	382
365	978
898	666
300	424
685	936
213	575
501	555
989	872
521	679
954	115
992	872
118	105
533	961
761	316
45	7
1000	576
760	90
820	525
26	949
425	87
680	214
360	66
937	282
948	156
291	772
585	549
816	996
105	237
996	514
658	391
903	232
117	424
371	270
66	147
459	380
318	52
153	875
923	639
508	636
70	7
739	901
546	753
713	222
172	740
479	296
617	97
646	956
825	942
367	643
953	91
529	827
228	41
734	33
756	372
77	440
743	710
300	224
502	296
117	639
350	799
183	181
41	102
534	421
126	487
427	421
34	587
519	639
320	576
757	91
305	535
727	274
982	268
546	348
528	249
91	908
64	139
494	294
856	182
642	362
86	928
964	93
263	420
230	753
476	465
339	791
278	865
200	518
434	408
387	749
560	359
933	666
896	86
158	992
69	6
877	251
1	944
346	515
297	243
370	158
932	550
876	645
475	102
338	311
724	26
820	417
675	855
194	592
649	105
144	249
367	695
130	133
335	333
548	911
858	451
649	883
362	615
629	690
467	927
468	980
738	335
438	615
218	920
42	770
366	966
33	199
808	332
410	945
714	902
59	316
355	465
986	438
516	136
826	917
476	336
819	383
831	938
928	384
819	974
369	460
420	200
872	558
541	217
897	157
264	101
537	34
393	696
373	892
465	335
956	7
297	105
300	842
400	525
155	848
419	783
650	107
301	509
691	684
9	23
619	94
175	72
717	325
980	833
294	687
26	427
44	312
502	48
625	382
490	87
422	125
960	225
86	432
424	729
138	884
651	930
735	238
687	223
862	156
335	774
870	104
986	247
933	7
108	199
746	454
978	601
971	820
254	724
171	816
726	169
718	416
844	702
773	576
397	40
813	629
824	678
124	659
853	784
322	765
450	94
618	485
958	337
214	960
678	529
936	12
350	598
421	913
867	865
946	619
57	405
256	860
372	412
966	143
174	480
885	676
1	637
487	125
786	674
394	785
983	95
417	436
897	335
709	206
294	625
728	913
848	754
392	910
748	798
542	14
342	329
508	23
10	403
728	679
530	546
661	464
809	356
851	154
917	893
499	586
34	168
586	747
896	117
775	544
518	508
471	591
56	307
873	675
769	226
739	406
831	154
747	257
231	47
647	879
789	198
681	508
543	422
332	373
352	622
526	747
173	227
805	495
461	224
768	415
833	512
47	767
295	37
463	312
92	187
371	90
591	375
239	418
299	209
623	115
851	284
647	482
770	406
451	958
909	909
242	816
916	991
90	723
662	796
825	942
128	383
836	81
614	867
474	2
734	139
587	421
432	371
537	613
860	836
396	800
160	446
290	126
855	358
943	176
968	279
402	360
82	557
365	698
300	582
368	849
24	725
811	914
678	266
430	699
909	175
516	896
469	119
386	448
289	556
938	998
746	744
685	644
540	970
321	774
99	860
420	914
245	815
204	822
480	632
579	482
280	526
952	58
214	719
236	970
412	879
584	177
497	354
459	687
826	93
386	711
595	151
848	678
557	600
934	395
73	646
882	692
718	743
346	408
712	620
928	501
440	732
62	391
999	687
581	621
804	975
790	541
42	203
548	429
570	572
208	55
772	66
817	595
170	324
434	447
315	922
49	337
878	951
279	815
404	16
220	602
316	137
300	192
305	483
308	25
699	590
517	464
854	593
699	224
634	451
543	776
974	855
43	390
102	519
706	930
730	784
802	19
593	710
406	923
617	276
249	885
91	884
827	953
2	476
1000	862
740	226
218	669
910	42
185	385
330	728
221	141
384	458
65	869
864	540
583	591
905	790
253	762
518	763
533	792
941	481
776	829
27	639
220	970
620	277
490	291
332	669
321	674
349	306
685	937
979	179
800	772
870	421
248	871
747	423
403	865
957	372
790	183
744	64
511	747
849	270
801	109
126	63
462	132
369	371
286	623
602	14
572	232
926	363
451	527
481	54
433	930
761	718
414	54
33	192
307	766
559	201
966	511
202	56
332	267
230	563
489	36
926	360
800	515
836	897
493	814
356	2
849	614
442	798
994	127
824	227
763	35
874	300
447	211
740	760
653	812
162	865
236	518
963	353
349	187
414	985
716	334
910	877
528	455
177	243
316	580
486	847
314	751
429	544
496	106
628	994
213	362
246	12
624	191
435	259
282	964
288	260
206	138
947	501
321	990
851	217
493	917
489	290
756	69
817	9
40	540
470	364
753	126
904	805
696	698
361	211
671	451
20	541
278	267
224	661
26	863
552	323
998	770
516	454
699	51
436	954
847	339
513	767
60	401
559	54
346	438
75	739
466	788
224	508
748	453
862	218
930	217
606	22
950	419
992	230
23	751
613	608
376	294
293	464
49	203
48	53
313	58
871	958
895	172
121	877
430	1000
735	427
701	692
174	782
872	737
859	892
153	787
808	156
634	69
435	953
224	468
42	877
762	427
166	513
627	747
288	262
503	836
510	597
815	246
897	392
686	903
508	704
650	160
214	904
635	889
801	236
314	689
896	979
40	168
978	863
374	688
713	266
802	610
420	534
686	650
337	912
378	774
729	617
175	613
961	324
810	342
718	51
631	561
743	975
71	52
10	466
850	967
645	742
336	404
715	516
710	259
544	566
849	122
228	145
609	282
383	114
270	749
548	43
37	834
315	242
633	925
748	162
727	513
719	2
211	707
994	680
389	846
361	537
12	222
461	328
855	200
760	500
221	1000
818	69
767	461
990	44
122	804
675	27
353	223
71	931
422	536
95	280
627	147
783	499
926	756
119	715
417	399
243	193
625	728
145	555
836	457
200	309
314	685
775	272
756	278
764	305
315	245
737	969
552	283
985	412
389	639
7	928
205	7
983	741
80	973
311	682
958	803
870	787
40	140
826	930
899	940
711	244
945	916
954	864
527	26
255	808
726	761
846	128
822	313
816	365
821	589
220	232
278	201
684	399
840	507

pts.colinear

1 2
5 5
9 3
15 15
0 100
10 10

run.bash

#!/bin/bash
cat pts.colinear | go run main.go