Постановка (ясность). Пусть задан выпуклый многоугольник с вершинами $v_1,v_2,\dots ,v_n$ в порядке обхода (индексы по модулю $n$). Периметр обозначим $P$. Требуется найти точку на границе (то есть на некотором рёбре/отрезке) многоугольника, такая что при обходе по границе от этой точки в одном направлении длина пути равна половине периметра $P/2$.
Метод (алгоритм)
1. Вычислите длины рёбер ${\ell }_i=|v_i{v}_{i+1}|$ для $i=1,\dots ,n$ и периметр
$$P=\sum _{i=1}^n{\ell }_i,S=\frac{P}{2}.$$ 2. Постройте кумулятивную последовательность длин от $v_1$:
$$L_0=0,L_k=\sum _{i=1}^k{\ell }_i(k=1,\dots ,n).$$ 3. Найдите индекс $k$ такой, что $L_{k-1}\le S<L_k$. (Если $S=L_j$ для некоторого $j$, то искомая точка — вершина $v_{j+1}$.)
4. Тогда искомая точка лежит на рёбре $[v_k,v_{k+1}]$. Её расстояние от вершины $v_k$ $$d=S-L_{k-1},$$ и координаты точки получаются линейной интерполяцией:
$$p=v_k+\frac{d}{{\ell }_k}(v_{k+1}-v_k).$$
Доказательство корректности и единственности
- Непрерывность и монотонность. Если параметризовать обход границы длиной от $v_1$ в прямом направлении функцией $t\mapsto q(t)$, где $t\in [0,P)$ — текущая пройденная длина, то $q(t)$ — непрерывная функция, которая монотонно проходит по границе. Значит для любого значения длины $t\in [0,P)$ существует ровно одна точка на границе с этой пройденной длиной (за исключением совпадения в вершинах, где два параметра описывают одну точку).
- По определению $S\in [0,P)$. Так как $L_k$ — кумулятивные суммы, существует единственный индекс $k$ с $L_{k-1}\le S<L_k$. Это означает, что при обходе от $v_1$ точка с пройденной длиной $S$ попадает именно на ребро $[v_k,v_{k+1}]$. Дистанция от $v_k$ до этой точки равна $d=S-L_{k-1}$ и, раз движение по рёбру соответствует однородной скорости по длине, положение точки определяется линейной интерполяцией, указанной в шаге 4.
- Единственность. Поскольку функция длины до точки вдоль обхода строго возрастает (на рёбрах она линейна по параметру, на вершинах есть переход, но не убывание), уравнение «пройденная длина = $S$» имеет единственное решение на отрезке $[0,P)$. Следовательно, точка единственна.
Замечания
- Если нужно разделить периметр на две равные части независимо от выбранной начальной вершины, алгоритм даёт точку, от которой в выбранном направлении длина пути равна $P/2$. В другом направлении получится другая (комплементарная) точка, расположенная на расстоянии $P/2$ вдоль границы от первой.
- Сложность вычисления: $O(n)$ арифметических операций (вычисление длин и поиск нужного ребра).
Таким образом метод сводится к вычислению половины периметра и однократному поиску ребра, на котором лежит точка с соответствующей пройденной длиной; корректность обеспечивается непрерывностью и монотонностью функции пройденной длины вдоль границы.