У меня есть N точек (N около 12000), и вычисляется центроид этих N точек Ct. Я хочу знать, сколько треугольников можно найти из N точек, с центроидом Ct в каждом из них.
Что я сделал:
1. используйте панды, чтобы прочитать координацию 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. проверьте, является ли Ct комбинацией треугольников или нет
4.1 Очень медленно выполняется поиск соответствующей координаты комбинации [a1 a2 a1000], для завершения процесса поиска требуется 6 секунд .
Так как N составляет порядка 10 000, вычисления все еще занимают несколько часов, даже с моей рабочей станцией.
Любые комментарии о том, как сократить вычислительное время, очень приветствуются.