find out which triangle is closest to equilateral triangle, fastest/simplest way

user_15055784 0
Viewed 112

I have tons of triangles defined by three 3d points, like

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))....

What I would like to know is, what is the best way to figure out which of these triangle is closest to equilateral triangle. The best strategy I can think of is, somehow calculate three internal angles of each triangle then get product of those three angles, then see which triangle has biggest product. If I'm not mistaking, closer the triangle is to equilateral triangle product of three angles is bigger(when a triangle is perfect equilateral triangle the product of internal angles is 60 times 60 times 60 = 216000) However, I feel like there are much better way to do this task. I would appreciate if you could comes up with better solution for me. None of those sets of three 3d points are in straight line. There are no edges whose length is 0 in these triangles.

math geometry
1 Answers

There is a clever idea due to a math teacher from Brooklyn, New York named Patrick Honner. It is to take the ratio of the area of a triangle to the area of the equilateral triangle which has the same perimeter. This yields a number between 0 and 1, with 1 corresponding to perfectly equilateral. When combined with Heron's formula for the area of a triangle, you get a fairly easy computation (especially after combining to a single square root and simplifying).

Here is a Python implementation:

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)

For testing purposes I wrote:

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))

Typical output:

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

Generating the 1 million triangles takes longer than finding the most equilateral one. If speed is an issue, you could consider removing the sqrt from the function eq since that would still yield a function taking values in the range [0,1].

user_49962480
Related