Проверьте, описан ли набор точек треугольником

Question

Я пытался решить этот вопрос, но не смог найти простое решение, не пройдя все строки и не обнаружив, какие числа находятся в одной строке.

Есть ли простой способ найти треугольники?

это мое решение для поиска треугольника:

Как я могу изменить его на более "pythoni c"? (или даже лучший способ ее решения)

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

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

Показывает положительное значение root: (sqrt(8*t + 1) - 1)/2. Чтобы быть строго меньшим, формула, которая справляется с небольшими ошибками аппроксимации, могла бы быть:

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

Следующая идея, учитывая список индексов:

• , преобразует их в xy координаты
• найти их центр (сумма и разделить на длину списка)
• найти расстояния каждого xy до центра
• проверить, что все расстояния равны

Чтобы преобразовать в положение xy, обратите внимание, что высота равностороннего треугольника с основанием 1 равна sqrt(3)/2, поэтому расстояния между положениями y следует умножить на этот коэффициент. Позиции х должны быть центрированы, что можно получить, вычитая 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

Обратите внимание, что этот код находит геометрические фигуры c, для которых все точки l ie на окружности. Это не работает для параллелограмма. Актуальный вопрос также имеет несколько дополнительных критериев: все ребра должны следовать линиям сетки, и все ребра должны быть равны по длине.

Поэтому полезно иметь 3 координаты для каждой точки: строка, столбец и диагональ (3 направления сетки).

Длина в каждом направлении - это максимум максимум минус минимум для этого направления. Эти длины называются d_r, d_c и d_d в приведенном ниже коде.

Проверка правильности треугольника, 3 длины должны быть равны. Один из способов проверить это - проверить, что минимум длин равен максимальному.

Для правильного параллелограмма две длины должны быть равны, а третья должна быть двойной. Проверка того, что максимальная длина в два раза меньше минимальной длины, должна охватывать это. Но, поскольку это уже может быть достигнуто с использованием 3 точек, мы также должны проверить, что для заданного направления есть ровно 2 точки как минимум и 2 как максимум. Суммирование всех точек и двойное сравнение суммы максимума и минимума должно выполнить sh this.

Для правильного шестиугольника 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