提问人：Valuex 提问时间：10/9/2019 更新时间：10/9/2019 访问量：126
从 N 个点可以找到多少个三角形，其中有 N 个点的质心？
How many triangles can be found from N points that with the centroid of the N points in them?
问：
我有 N 个点（N 约为 12000），并计算出这些 N 点的质心。
我想知道，从 N 个点可以找到多少个三角形，每个三角形都有质心。CtCt
我做了什么：
1.使用 pandas 将 N 个点的坐标读取到数据帧中。（以下数据仅供参考）
PntsDF
x y
a1 1 1
a2 1 2
...
a12000 100 100
2. 根据极坐标将N点分为三个部分，可以大大降低计算复杂度。
PntsDF
x y Part
a1 1 1 Sec1
a2 1 2 Sec1
...
a12000 100 100 Sec3
3.使用笛卡尔积从三个部分得到点的组合，比IterTools更快。
CombsDF:
p1 p2 p3
1 a1 a2 a1000
2 a1 a2 a1001
...
64000000000 a12000 a200 a201
4.检查三角形组合是否为三角形组合
4.1 查找组合的咕咕坐标非常慢，完成查找过程大约需要 6 秒。Ct[a1 a2 a1000]
由于 N 的量级为 10 000，因此即使使用我的工作站，仍然需要数小时才能进行计算。
任何关于如何缩短计算时间的意见都非常感谢。
答：
0赞
Arno Maeckelberghe
10/9/2019
#1
工作正在进行中，但首先想到的是：
通过检查以下 4 个条件，您可以已经下降 43.75% （） 的三角形（假设您的点是均匀分布的）：1 - (3/4)**2
(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)
这将大大减轻计算负担。
然后，为了检查剩余的三角形，我实现了 @Andreas Brinck 在 stackoverflow - algorithm 中描述的算法。其中一条评论还在 jsfiddle 中测试了他的算法。
顺便说一句，我不完全理解您的分割技术，如果您只打算从 3 个不同的分割中选择点进行组合，您将忽略许多仍然包含我们的 ct 的三角形？
评论
0赞
Valuex
10/11/2019
将质心设置为原点，并且每隔 120 度将点放在一个部分中。同一截面中的点不会形成质心在的三角形。
评论
several hours