Построение выпуклой оболочки в режиме реального времени / Doc / Примечание

Примечания

1) Из программы было удалено центрическое распределение, в результате чего были удалены соответствующая кнопка из панели инструментов и соответствующий пункт меню.

2) Добавилось диалоговое окно с настройками распределения в кольце, описанное ниже.

3) Добавлена новая кнопка «Приостановить/возобновить генерацию» и соответствующий пункт меню, позволяющие приостановить или возобновить автоматическую генерацию точек.

Кнопка и пункт меню становятся активными только в случае выбора одного из видов генерации.

В случае, если, например, была выбрана генерация с использованием распределения в кольце, а затем нажата кнопка, приостанавливающая генерацию, то повторный выбор генерация с использованием распределения в кольце приведет к завершению генерации вообще. Чтобы начать автоматическую генерацию снова, надо выбрать соответствующий пункт меню (или нажать соответствующую кнопку панели инструментов).

Распределение в кольце

В программе предусмотрена возможность задания в автоматическом режиме множества точек, для которых строится выпуклая оболочка. Генерация точек возможна с использованием одного из распределений: равномерное распределение в прямоугольнике и распределение в кольце.

Для использования автоматической генерации с использованием распределения в кольце необходимо выбрать соответствующий пункт меню или нажать на соответствующую кнопку в панели инструментов, после чего на экране появится диалоговое окно (см. рис. 1) для задания параметров распределения.

Рис. 1

Обозначения:

Минимальный внешний радиус кольца – параметр 1.

Максимальный внешний радиус кольца – параметр 2.

Ширина кольца (в % от внешнего радиуса кольца) – параметр 3.

Приращение внешнего радиуса – параметр 4.

Количество точек - параметр 5.

Ограничения на вводимые значения:

Значение параметра 1 лежит в интервале [20, 170].

Значение параметра 2 лежит в интервале [20, 170].

Значение параметра 3 лежит в интервале [0, 100].

Значение параметра 4 лежит в интервале [2, 10].

Значение параметра 5 лежит в интервале [1, 200].

Единицы измерения значений параметра:

1) 1, 2 и 4 – пиксели;

2) 3 – проценты;

3) 5 – безразмерная величина.

Параметр 1 позволяет задать минимальный внешний радиус кольца (см. рисунок 2).

Рис.2

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

В случае, если минимальный радиус сразу же (в диалоговом окне на рис. 1) задан равным максимальному, то увеличение радиуса кольца не происходит и точки ставятся в кольцо, ограниченное максимальным внешним радиусом (он же минимальный) и внутренним, который можно вычислить следующим образом: минимальный внешний радиус минус ширина кольца. Ширина кольца задается в процентах от текущего внешнего радиуса.

Р ис.3

x – значение параметра 3,

R – текущий внешний радиус кольца,

R – приращение внешнего радиуса, задаваемое параметром 4.

Таким образом (см. рис.3), изменение внешнего радиуса на приращение (R) влечет изменение ширины кольца на R*x/100.

Если задать толщину кольца равной 0%, то распределение в кольце «превращается» в распределение по окружности (точки ставятся на окружность радиуса R, где R – значение внешнего радиуса кольца). Если задать толщину кольца, равной 100%, то распределение в кольце «превращается» в распределение в круге. Точки распределяются по всему кругу.

Ширина кольца в совокупности с внешним радиусом определяет ту область, в которой будут генерироваться точки.

В случае, если значение текущего радиуса достигло значения максимального, но не все точки, количество которых задано параметром 5, были сгенерированы, то дальнейший рост внешнего радиуса прекратится, а оставшиеся точки будут ставиться в кольцо, ограниченное максимальным внешним радиусом и внутренним радиусом, который определяется как внешний радиус за вычетом ширины кольца.

Если же значение текущего радиуса не достигло значения максимального, и все точки, количество которых задано параметром 5, были сгенерированы, то генерация прекращается, и дальнейший рост внешнего радиуса не происходит.

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

Ограничение, накладываемое реализацией алгоритма на задание множества исходных данных:

При постановке точек на одной прямой, а также очень близко друг к другу (в радиусе двух пикселей) возникает проблема правильного (однозначного) определения ситуации. Существует неоднозначность в принятии решения, какие точки в этом случае считать опорными. Чтобы избежать этого, реализовано следующее: при вставке очередного элемента в выпуклую оболочку проверяется, не лежит ли точка на одной прямой с точками выпуклой оболочки и не лежит ли в радиусе двух пикселей другая точка. Если точка лежит на прямой или вблизи другой точки, то точка просто игнорируется, иначе вставляется в оболочку, либо отмечается, как внутренняя. Если игнорирование происходит в режиме автоматической генерации, то происходит генерация новой точки, которая также проверяется на соблюдение описанных условий. Такая генерация происходит максимум пять раз. Если точка удовлетворяет условиям, то она ставится и цикл проверки прекращается. Если же после цикла ни одна из пяти точек не удовлетворила условиям, она не ставится вообще. В режиме ручной постановки точек не происходит дополнительной генерации и, если точка не удовлетворяет условиям, то она просто не ставится.