Распределить точки вдоль многоуголь на одинаковом расстоянии

[ivanovich]

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

Подчеркну, что здесь важно эвклидово расстояние. Существующие многочисленные решения считают расстояние вдоль сторон многоугольника, как на картинках. Но тогда эвклидово расстояние между некоторыми точками получается отличным от других. А нужно, чтобы оно было везде одним и тем же.



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

[dgwuqtj]

Можно для каждого расстояния попробовать расставить точки, начиная с какой-то фиксированной. Если $M$ достаточно большое, то с уменьшением расстояния будет уменьшаться и часть границы, покрытая точками, так что можно искать ответ двоичным поиском.

[ivanovich]

А на сколько уменьшать расстояние? На какой-то процент от текущего или на фиксированную величину?

[wrest]

ivanovich
Решение представляет из себя два параметра -- расположение какой-то точки и длину.
Значит, попробовать фиксирокать точку и каким-то методом (последовательных приближений) искать длину.
Надо ещё держать в уме, что решение может быть не единственным. На сторонах правильного N-угольника можно расположить M=N точек например в вершинах или на серединах сторон.
В случае треугольника расстояние (для трех точек) может меняться от длины стороны до её половины.

Может ещё поможет такое соображение. По сути, в задаче надо в данный N-угольник вписать равносторонний M-угольник.

[dgwuqtj]

ivanovich в сообщении #1662609 писал(а):

А на сколько уменьшать расстояние? На какой-то процент от текущего или на фиксированную величину?

Пробуем расстояние $d$. Если оно слишком большое, пробуем $d / 2$. Если $d / 2$ слишком маленькое, пробуем $3 d / 4$... Двоичный поиск же. Вообще там зависимость гладкая, так что можно и чем-то вроде метода хорд.

[sergey zhukov]

ivanovich
Проще, наверное, не расставлять $M$ точек как-нибудь, а потом их двигать, чтобы обеспечить равномерное распределение, а несколько раз перерисовать равномерное распределение точек, пока оно не сойдется к $M$ точкам и не замкнется в конце. От каждой текущей точки рисуем окружность фиксированного радиуса, ищем пересечение со сторонами прямоугольника и т.д.

[wrest]

dgwuqtj в сообщении #1662615 писал(а):

Вообще там зависимость гладкая,

Вы уверены? Расстояние между точками гладко зависит от координаты второй точки вдоль многоугольника, но не наоборот. Координата вдоль многоугольника зависит от расстояния между точками не гладко, т.к. это неоднозначная функция (одному и тому же расстоянию от точки A могут соответствовать больше одной "следующей" точки B).

-- 24.11.2024, 01:39 --

sergey zhukov в сообщении #1662617 писал(а):

От каждой текущей точки рисуем окружность фиксированного радиуса, ищем пересечение со сторонами прямоугольника и т.д.

Типа того. Но вот сдаётся мне, что например разместить 5 точек по равностороннему треугольнику можно единственным способом (с точностью до симметрий). Все пять попадут или в вершины или в середины сторон (все середины сторон + 2 вершины). И расстояние между ними будет половина стороны. Так, например, поместив первую точку произвольно (т.е. не в вершину и не в середину стороны), вообще нельзя будет найти нужную конфигурацию.


На стороне желтого треугольника со стороной единица выбрали "стартовую" точку D.
Провели окружности с центром в D: красная, фиолетовая, зеленая - радиусами $0,4;0,5;0,6$ соответственно.

[dgwuqtj]

wrest в сообщении #1662618 писал(а):

Вы уверены?

Я был неправ, она даже разрывная... Хочется дополнительное условие, например, что все углы тупые.

[ivanovich]

Остановлюсь на алгоритме с окружностями и последовательном приближении длины отрезков, соединяющих точки.

Выбираем начальную точку P1 и число необходимых точек N.
Вычисляем периметр многоугольника L.
Определяем начальное расстояние между точками: l1 = L/N.
Размещаем точки:
- от текущей проводим окружность радиуса l1 и ищем ее пересечение со сторонами многоугольника;
- если их несколько, то проходя вдоль сторон, выбираем первое (ближайщее) место пересечения;
- это будет позиция следующей точки.
В конце концов мы придем к конечной точкe PM.
Определяем расстояние d1=|PM-P1|.
- если оно больше эпсилон, вводим кооректирующий фактор c1 = d1/N;
- учитываем знак, если мы проскочили начальную точку, ставим минус, иначе плюс;
Корректируем расстояние между точками l2 = l1 + c1.
Повторяем.

Вопрос, сойдется ли такой алгоритм к решению?

[dgwuqtj]

ivanovich в сообщении #1662653 писал(а):

Вопрос, сойдется ли такой алгоритм к решению?

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

[wrest]

ivanovich в сообщении #1662653 писал(а):

Вопрос, сойдется ли такой алгоритм к решению?

Кажется, что иногда да, а иногда нет. Ваши враги - острые углы (ну и углы большие развёрнутых). Надо проверять...

[sergey zhukov]

ivanovich в сообщении #1662653 писал(а):

Вопрос, сойдется ли такой алгоритм к решению?

Неужели не интересно это проверить на практике?

[ivanovich]

sergey zhukov в сообщении #1662682 писал(а):

Неужели не интересно это проверить на практике?

Конечно интересно и собираюсь это сделать)

-- 24.11.2024, 17:41 --

dgwuqtj в сообщении #1662654 писал(а):

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

Не упомянул, что начальная точка всегда находится в вершине многоугольника.