Блог

У меня есть тонны треугольников, определенных тремя 3d-точками, такими как

 T1 = ((x1, y1, z1), (x2, y2, z2), (x3, y3, z3))
T2 = ((x1, y1, z1), (x2, y2, z2), (x3, y3, z3))
T3 = ((x1, y1, z1), (x2, y2, z2), (x3, y3, z3))
T4 = ((x1, y1, z1), (x2, y2, z2), (x3, y3, z3))....
 

Я хотел бы знать, каков наилучший способ выяснить, какой из этих треугольников ближе всего к равностороннему треугольнику.
Лучшая стратегия, которую я могу придумать, — это каким-то образом вычислить три внутренних угла каждого треугольника, затем получить произведение этих трех углов, а затем посмотреть, какой треугольник имеет наибольшее произведение. Если я не ошибаюсь, ближе треугольник к равностороннему треугольнику, произведение трех углов больше(когда треугольник является идеальным равносторонним треугольником, произведение внутренних углов 60 раз 60 раз 60 = 216000)
Тем не менее, я чувствую, что есть гораздо лучший способ выполнить эту задачу.
Я был бы признателен, если бы вы могли придумать для меня лучшее решение.
Ни один из этих наборов из трех 3d-точек не находится на прямой линии.
В этих треугольниках нет ребер, длина которых равна 0.

Есть умная идея, придуманная учителем математики из Бруклина, штат Нью-Йорк, по имени Патрик Хоннер. Он состоит в том, чтобы принять отношение площади треугольника к площади равностороннего треугольника, имеющего тот же периметр. Это дает число от 0 до 1, причем 1 соответствует совершенно равностороннему. В сочетании с формулой Херона для площади треугольника вы получаете довольно простое вычисление (особенно после объединения в один квадратный корень и упрощения).

Вот реализация Python:

 import math

#computation given the sides:

def eq(a,b,c):
    p = a b c
    s = p/2
    e = p/3
    return math.sqrt((s-a)*(s-b)*(s-c)/(s-e)**3)

def dist(p,q):
    return math.sqrt(sum((x-y)**2 for x,y in zip(p,q)))

#computation given the vertices:
    
def eq_vertices(vertices):
    p,q,r = vertices
    a = dist(p,q)
    b = dist(p,r)
    c = dist(q,r)
    return eq(a,b,c)

def most_equilateral(triangles):
    return max(triangles,key = eq_vertices)
 

В целях тестирования я написал:

 import random

def rand_triangle():
    nums = tuple(random.uniform(0,10) for _ in range(9))
    return nums[:3],nums[3:6],nums[6:]

def rand_triangles(n):
    return [rand_triangle() for _ in range(n)]

p,q,r = most_equilateral(rand_triangles(10**6))
print(p)
print(q)
print(r)
print(dist(p,q),dist(p,r),dist(q,r))
 

Типичный выход:

 (5.78980790676774, 9.853230008053409, 4.974470485333855)
(8.824990996578379, 4.403159314576518, 3.1039937224539615)
(2.7571861861239597, 5.607135338917225, 1.0725696230700976)
6.512625451616404 6.515438955183434 6.511105693852511
 

Создание 1 миллиона треугольников занимает больше времени, чем поиск самого равностороннего. Если скорость является проблемой, вы можете рассмотреть возможность удаления sqrt из функции eq , так как это все равно приведет к функции, принимающей значения в диапазоне [0,1].