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

Question

[no-pasaran]

Не ругайте сильно я новичёк в этом языке. Наскорую накидал програму чтобы проверить является ли набор векторов многоугольником
Поправьте теги если что-то нетак простити

def is_sum_zero_vector(vectors):
    vector_length = len(vectors[0])
    zero_vector = [0] * vector_length

    vector_sum = [sum(values) for values in zip(*vectors)]

    return vector_sum == zero_vector

Что думаете?

Comments

[Модератор]

Фрагменты кода надо размещать в виде текста и оборачивать тэгом code для корректного отображения. Удобно делать кнопкой </>
Это обязательно, см.п.3.8 Регламента.
Сюда же относится traceback, ввод и вывод в консоли и другая структурированная текстовая инфа.

[no-pasaran]

Модератор, большое спасибо!

[ksnk]

В многоугольнике векторная сумма всех векторов-сторон ==0. А вот какой получится - вероятно, проще полный перебор, начиная с первого вектора. Как вариант - вычислять угол наклона вектора и отсортировать их всех по возрастанию, тогда получится наиболее выпуклый из всех возможных.

Answer 1

[hint000]

Например: [(10, 0), (0, 10), (-10, 0), (0, -10)]

Учтите, что код, правильно работающий с целыми числами, будет давать сбои на вещественных числах из-за ошибок округления. Т.е. вы можете получать очень-очень маленькую длинну суммарного вектора (без округления был бы чистый ноль, но компьютер не работает с вещественными числами без округления), из-за этого условие vector_sum == zero_vector не выполнится.

Answer 2

[Wataru]

Из отрезков заданной длины можно составить многоугольник тогда и только тогда, когда максимальный строго меньше суммы всех остальных. Или, тоже самое: максимальный строго меньше половины суммы всех.

Код проверки будет примерно такой:

def can_construct_polygon(lengths):
  return len(lengths)>0 and max(lengths) < sum(lengths)/2

В списке lengths надо передать длины всех отрезков. Если у вас там вектора на плоскости заданы в vectors, то через map подсчитайте их длины сначала.

Edit:

Раз поворачивать вектора-отрезки нельзя, то действительно, составить многоугольник можно, если по-координатная сумма векторов дает (0, 0).

Все еще остается вопрос, а допускаются ли вырожденные мноугольники? Например, можно ли составить такой из веторов (1,0), (-1,0). Если допускаются, то проверять длины не надо. Если нет, то все еще надо, как я выше указал, сравнить максимальную длину с суммой всех длин.

Еще есть вопрос, а можно ли вектора переставлять. Если нельзя, то можно ли допускать самопересечение многоугольника? Надо ли самопересечениие проверять? Но я думаю, что в задаче это игнорируется и можно стороны переставлять. Тогда можно их отсортировать по углу и получить выпуклый многоугольник без самопересечений. Иначе задача становится весьма сложной геометрической задачкой, где надо проверять пересечение отрезков.

Ваш код вроде бы правильно проверяет на сумму векторов покомпонентно. Попробуйте добавить еще и проверку длин.

Comments

[no-pasaran]

вы неправильно поняли вопрос, речь идет о задании много угольника набором векторов, а не отрезков
вектор определяется направлением, а не только длинной и задается двумя данным: [1, 2] - вектор и точки 0-0 в точку 1-2.

[Wataru]

no-pasaran,

вы неправильно поняли вопрос

Это потому что вы условие задачи так и не сформулировали. Надо эти ветора подвигать, чтобы сложился многоугольник? Их можно вращать или нет? Можно их расставлять в любом порядке?

[Максим Припадчев]

no-pasaran, вектор [1,2] не обязан начинаться в [0,0]. назовем оси x и y. Это увеличение координаты x на 1 увеличение координаты y на 2. А начинаться в [0,0] они не обязаны.

[no-pasaran]

Набор векторов это массив из элементов задающих вектор. То есть это направление и длинна. Вектор задается двумя значениями - xy. Например: [(10, 0), (0, 10), (-10, 0), (0, -10)] - 4 vectors которые задают квадрат. Векторы в любом порядке. Много углов - больше чем треугольник или треугольник.

[no-pasaran]

Максим Припадчев, Wataru, я добавил изображение к первому вопросу. думаю это сделает понятнее. спасибо.

[Wataru]

no-pasaran, Я отредактировал свой ответ. Перечитайте его, пожалуйста.