3

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.

Valuex
  • 104
  • 1
  • 10
  • Could you post your code? With only the result its a bit hard to optimize it. – Markus Oct 09 '19 at 14:19
  • 1
    if you have 12k points, there are about 1.7e12 possible triangles, you may filter out probably about 1/2 of them, it's still quite a few terabytes just to store the coordinates. Are you really equipped to do that? `several hours` you say??? – lenik Oct 09 '19 at 15:11
  • Not that big. Combin(12000,3) is about 2.9E11. And the triangles with centoid in won't be more than 64 billion based on my estimation. So it can be done with modern computer. But more effcience is required. – Valuex Oct 11 '19 at 00:43

1 Answers1

0

Work in progress, but a first thought:

By checking the following 4 conditions you can drop 43.75% (1 - (3/4)**2) of your triangles already (assuming your points are evenly distributed):

  • (triangles['x1'] > ct_x) & (triangles['x2'] > ct_x) & (triangles['x3'] > ct_x)
  • (triangles['x1'] < ct_x) & (triangles['x2'] < ct_x) & (triangles['x3'] < ct_x)
  • (triangles['y1'] > ct_y) & (triangles['y2'] > ct_y) & (triangles['y3'] > ct_y)
  • (triangles['y1'] < ct_y) & (triangles['y2'] < ct_y) & (triangles['y3'] < ct_y)

This will reduce the computational burden by a lot already.

To then check the remaining triangles I implemented the algorithm described by @Andreas Brinck in stackoverflow - algorithm. One of the comments also tests his algorithm in jsfiddle.

Btw, I don't completely understand your segmentation technique, if you're only going to make combinations of points selected from the 3 different segments you will ignore a lot of triangles that still include our ct?:

ignored-triangle

Arno Maeckelberghe
  • 377
  • 1
  • 7
  • the centroid was set as the origin, and the points were put in a section every 120 degree. Points in the same section won't form a triqngle with centroid in. – Valuex Oct 11 '19 at 00:36