I have N points (N is about 12000) and the centroid of these N points Ct is calulated.
I want to know, how many triangles can be found from the N points, that with the centroid Ct in each of them.
What I've done:
1. use pandas to read coordination of N points into a dataframe. (All following data is for illustation only)
PntsDF
x y
a1 1 1
a2 1 2
...
a12000 100 100
2. class the N points into three parts by their polar coordinates, which can reduce computing complexity a lot.
PntsDF
x y Part
a1 1 1 Sec1
a2 1 2 Sec1
...
a12000 100 100 Sec3
3. use cartesian product to get the combinations of points from the three parts, which is faster than itertools.
CombsDF:
p1 p2 p3
1 a1 a2 a1000
2 a1 a2 a1001
...
64000000000 a12000 a200 a201
4. check whether Ct is the triangle combinations or not
4.1 It's very slow to lookup a combination [a1 a2 a1000] 's cooresponding coordinate, it takes about 6 seconds to finish the lookup process.
Since N is in the order of 10 000, it still takes serveral hours to do the calculation, even with my work station.
Any comments on how to short the computing time is highly appreciated.
