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

罗伊·安克里

在此处输入图片说明

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

有没有一种简单的方法可以找到三角形?

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

如何将其更改为更“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
约翰·C

第一步可能是搜索将一维点数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_rd_cd_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

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章

纹理的使用与绘制三角形冲突,仅显示一个

将一个三角形转换为另一个三角形

使用递归从星星中创建一个三角形

如何确定一个点是否在2D三角形中?

了解类:通过扩展3个点组成一个三角形?

C#在另一个等边三角形的边上绘制等边三角形

从一组随机点生成三角形

是否可以仅使用CSS制作一个圆角三角形?

如何创建一个numpy数组来描述三角形的顶点?

两个三角形组成一个矩形

如何在底部创建一个全角三角形?

如何从同构三角形集中仅返回一个三角形?

Open GL DrawArrays仅绘制一个三角形/直线/点(OpenTK / C#)

如何制作一个始终面对同一点的三角形?

如何用中心坐标和一个点的坐标创建一个三角形?

给定(象限i)中的三个(x,y)点,它们组成一个直角三角形,求出三角形的排列

提取具有属性的相关矩阵的一个三角形

我需要做一个倒三角形

创建一个三角形以防止内部内容溢出

在背景图像上创建一个透明的CSS三角形

从底行开始增加一个三角形

在视图之间实现一个三角形(如Instagram登录屏幕上的三角形)

从一组相邻三角形创建多边形的算法

画一个三角形的高度

给定一组线,我如何计算它们形成多少个三角形

如何仅使用 css 创建一个三角形的 div?

如何围绕JavaFX中的一个点旋转三角形并获取点的值?

Flutter - 使用 customPainter 在右下角绘制一个三角形

gnuplot:如何从文件中绘制一组三角形?