python - 检查一组点是否描述了一个三角形

Question

我试图解决这个问题，但如果不传递所有行并找出哪些数字在同一行上，就找不到简单的解决方案。

有没有简单的方法来找到三角形？

这是我找到三角形的解决方案：

如何将其更改为更“pythonic”？（甚至更好的解决方法）

from sympy.solvers import solve
from sympy import Symbol
from collections import Counter

vals = [8,17,19] # the triangle
dicl = []   #list of dics
for v in vals:
    dic = {}
    dic['val'] = v
    v1 = v
    done = 0
    stepsb = 0
    while done == 0:  #going backword untill reaching the big triabgle edges
        x = Symbol('x')
        k = solve((x**2 + x)/2 +1 - v1, x)
        k = list(filter(lambda x:x>0, k))
        if k[0]%1 == 0:               
            done = 1
        else:
            v1 -= 1
            stepsb += 1

    dic['line'] = k[0]
    dic['stepsb'] = stepsb  #dist from the left edge
    dic['stepsf'] = (k[0]**2 + 3*k[0] + 2)/2 - v  #dist from the right edge
    dicl.append(dic)
    print(dic)


lines = [l['line'] for l in dicl]
mc = Counter(lines).most_common(1)[0][0]   #finding the numbers on the same line

minv = min([l['val'] for l in dicl if l['line'] == mc])
maxv = max([l['val'] for l in dicl if l['line'] == mc])
stb = [l['stepsb'] for l in dicl if l['val'] == minv][0]
stf = [l['stepsf'] for l in dicl if l['val'] == maxv][0]
for k in dicl:
    if k['stepsb'] == stb and k['stepsf'] == stf:
        print("good")
        break

标签： pythonmath

Answer 1

第一步可能是搜索将一维点数t转换为x,y坐标的公式。

所以，搜索n这样一个n*(n+1)/2 < t：

from sympy import solve, Eq
from sympy.abc import n, t

f = Eq(n * (n + 1), 2 * t)
print(solve(f, n))  

这显示为正根：(sqrt(8*t + 1) - 1)/2。严格来说，处理小近似误差的公式可以是：

floor((sqrt(8*t + 1) - 1)/2 - 0.0000001

下面的想法是，给定一个索引列表：

• 将它们转换为 xy 坐标
• 找到他们的中心（总和除以列表的长度）
• 找到每个 xy 到中心的距离
• 检查所有距离是否相等

要转换为 xy 位置，请注意以 1 为底的等边三角形的高度为sqrt(3)/2，因此 y 位置之间的距离应乘以该因子。x 位置需要居中，这可以通过减去 来实现n/2。

import math

def find_xy(t):
    # convert the numerical position into an xy coordinate in the plane
    # first find largest n such that n*(n+1)/2 < t
    n = math.floor((math.sqrt(8 * t + 1) - 1) / 2 - 0.0000001)
    return (n + 1) * math.sqrt(3) / 2, t - n * (n + 1) // 2 - n/2

def sq_dist(p, q):
    return (p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2

def center(points):
    # find the center of a list of points
    l = len(points)
    x = sum(p[0] for p in points)
    y = sum(p[1] for p in points)
    return x / l, y / l

def is_regular(tri_points):
    points = [find_xy(t) for t in tri_points]
    cent = center(points)
    dists = [sq_dist(cent, p) for p in points]
    return max(dists) - min(dists) < 0.000001

请注意，此代码查找所有点都位于一个圆上的几何图形。这不适用于平行四边形。实际问题还有一些额外的标准：所有边都应该遵循网格线，并且所有边的长度必须相等。

因此，为每个点设置 3 个坐标是很有用的：行、列和对角线（网格的 3 个方向）。

每个方向的长度，只是该方向的最大值减去最小值。这些长度称为d_r,d_c并d_d在下面的代码中。

检查一个有效的三角形，3 个长度必须相等。检查这一点的一种方法是检查长度的最小值是否等于最大值。

对于有效的平行四边形，两个长度必须相等，第三个应该是双倍。检查最大长度是否是最小长度的两倍应该涵盖这一点。但是，因为这已经可以使用 3 个点来达到，所以我们还应该检查对于给定的方向，在最小值处恰好有 2 个点，在最大值处正好有 2 个点。将所有点相加并比较最大值和最小值之和的两倍应该可以做到这一点。

对于有效的六边形，3 个长度应该相等。因此，与三角形相同的测试：长度的最小值等于最大值。并且还需要对总和进行测试，因为 4 个点已经可以满足长度条件。

import math

def find_row_col_diag(t):
    # convert the numerical position into an row,col,diag coordinate in the plane
    # first find largest n such that n*(n+1)/2 < t
    n = math.floor((math.sqrt(8 * t + 1) - 1) / 2 - 0.0000001)
    row, col = n + 1, t - n * (n + 1) // 2
    return row, col, row - col

def check_valid_figure(tri_points):
    points = [find_row_col_diag(t) for t in tri_points]
    rs = [r for (r, c, d) in points]
    cs = [c for (r, c, d) in points]
    ds = [d for (r, c, d) in points]
    sum_r = sum(rs)
    min_r = min(rs)
    max_r = max(rs)
    d_r = max_r - min_r
    sum_c = sum(cs)
    min_c = min(cs)
    max_c = max(cs)
    d_c = max_c - min_c
    sum_d = sum(ds)
    min_d = min(ds)
    max_d = max(ds)
    d_d = max_d - min_d
    if len(points) == 3:
        is_ok = max(d_r, d_c, d_d) == min(d_r, d_c, d_d)
    elif len(points) == 4:
        is_ok = max(d_r, d_c, d_d) == 2 * min(d_r, d_c, d_d) \
                and sum_r == 2 * (min_r + max_r) and sum_c == 2 * (min_c + max_c) and sum_d == 2 * (min_d + max_d)
    elif len(points) == 6:
        is_ok = max(d_r, d_c, d_d) == min(d_r, d_c, d_d) \
                and len(set(rs)) == 3 and len(set(cs)) == 3 and len(set(ds)) == 3
    else:
        is_ok = False
    print(" ".join([str(t) for t in tri_points]), end=" ")
    if is_ok:
        print("are the vertices of a",
              "triangle" if len(points) == 3 else "parallelogram" if len(points) == 4 else "hexagon")
    else:
        print("are not the vertices of an acceptable figure")

tri_point_lists = [[1, 2, 3],
                   [11, 13, 22, 24],
                   [11, 13, 29, 31],
                   [11, 13, 23, 25],
                   [26, 11, 13, 24],
                   [22, 23, 30],
                   [4, 5, 9, 13, 12, 7]]
for lst in tri_point_lists:
    check_valid_figure(lst)

最后的代码可以使用列表推导进一步压缩：

def check_valid_figure_bis(tri_points):
    points = [find_row_col_diag(t) for t in tri_points]
    rs, cs, ds = [[p[i] for p in points] for i in range(3)]
    sums = [sum(xs) for xs in (rs, cs, ds)]
    mins = [min(xs) for xs in (rs, cs, ds)]
    maxs = [max(xs) for xs in (rs, cs, ds)]
    lens = [ma - mi for mi, ma in zip(mins, maxs)]
    if len(points) == 3:
        is_ok = max(lens) == min(lens)
    elif len(points) == 4:
        is_ok = max(lens) == 2 * min(lens) and all([su == 2 * (mi + ma) for su, mi, ma in zip(sums, mins, maxs)])
    elif len(points) == 6:
        is_ok = max(lens) == min(lens) and all([len(set(xs)) == 3 for xs in (rs, cs, ds)])
    else:
        is_ok = False
    return is_ok