САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
КАФЕДРА МАТЕМАТИЧЕСКОЙ ТЕОРИИ МОДЕЛИРОВАНИЯ
СИСТЕМ УПРАВЛЕНИЯ
Колосов Игорь Андреевич
Выпускная квалификационная работа специалиста
ТЕСТИРОВАНИЕ ЭФФЕКТИВНОСТИ АЛГОРИТМОВ ПОСТРОЕНИЯ
ВЫПУКЛОЙ ОБОЛОЧКИ
Направление СМ.116.2006
Прикладная математика и информатика
Научный руководитель
кандидат физ.-мат. наук,
доцент
Тамасян Г. Ш.
Санкт-Петербург
2016
2
Оглавление
Стр.
1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
2. Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
3. Вспомагательные сведения . . . . . . . . . . . . . . . . . . . . . . . . .
6
4. Решение задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.1 Алгоритм проверки условий крайности . . . . . . . . . . . . . . . . 10
4.2 Программная реализация . . . . . . . . . . . . . . . . . . . . . . . . 13
5. Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3
1. Введение
Во многих задачах вычислительной геометрии и на некоторых этапах реализации алгоритмов недифференцируемой оптимизации возникает задача по
выявлению крайних точек выпуклой оболочки конечного числа точек. Например, кодифференциал функции 𝑓 суммы от кодифференцируемых функций 𝑓𝑘
представляет собой сумму (по Минковскому) кодифференциалов 𝑑𝑓𝑘 , т.е. сумму
выпуклых многогранников. Естественно, что количество элементов в кодифференциале 𝑑𝑓 функции 𝑓 возрастает экспоненциально. В таком случае для эффективной работы численных алгоритмов негладкого анализа необходимо производить «чистку», т.е. отбросить не информативные точки и оставить только
крайние.
Из известных методов решающих рассматриваемую задачу является алгоритм QuickHull [3] — построение выпуклой оболочки для заданного набора
точек. Однако, его применение сопряжено со многими ограничениями. Разработчики пакета MatLab обращают внимание на то, что данная процедура дает
гарантированный результат для набора точек из пространства размерностей не
более 6-9.
В работе рассматривается программная реализация по выявлению крайних
точек у множества, которое получается в результате сложения многогранника
и отрезка. Теоретической базой данного алгоритма являются результаты работы [1]. Предполагается, что многогранник задан крайними точками, а также известны грани и их нормали. В частности, данную информацию о многограннике
можно получить в результате применения алгоритма QuickHull.
4
2. Постановка задачи
Напомним определения выпуклой оболочки и крайней точки.
Определение 1. Выпуклой оболочкой conv 𝐴 множества 𝐴 называется наименьшее выпуклое множество, содержащее 𝐴.
Определение 2. Точка 𝑝 выпуклого множества 𝑆 ⊂ R𝑛 называется крайней,
если не существует пары точек 𝑎, 𝑏 ∈ 𝑆 таких, что 𝑝 лежит в относительной
внутренности отрезка conv{𝑎,𝑏}.
Рассмотрим множество 𝐴, состоящее из трех точек на плоскости.
{︃(︃ )︃ (︃ )︃ (︃ )︃}︃
0
−2
−2
𝐴=
,
,
.
3
6
1
На рисунке 2.1 треугольник со своей внутренностью соответствует множеству conv 𝐴, а вершины являются крайними точками.
𝑦
6
3
1
-2
-1
0
𝑥
Рисунок 2.1 — Выпуклая оболочка и крайние точки множества 𝐴
Изобразим (см. рис. 2.2) сумму многогранника conv 𝐴 и отрезка 𝑇 , с вершинами в точках (0, 0)𝑇 и (4, 0)𝑇 .
Видно, что точка (0,3)𝑇 не является крайней для нового многоугольника
(рис. 2.2, б)). Она не является существенной для задания результата суммы. Точку (0,3)𝑇 следует идентифицировать и удалить.
5
-2
-1
𝑦
𝑦
6
6
3
3
1
1
0
4
𝑥
-2
-1
0
2
4
𝑥
а) треугольник conv 𝐴 и отрезок 𝑇
б) conv 𝐴 + 𝑇
Рисунок 2.2 — Сумма многогранника и отрезка
Ставится задача проверки крайности точек, которые получаются в результате суммы произвольныx многогранника и отрезка в конечномерном пространстве.
6
3. Вспомагательные сведения
Напомним одно из определений выпуклого конуса.
Определение 3. Пусть подмножество 𝐶 является частью пространства R𝑛 . Множество
𝐾(𝐶) = {𝜆𝑥 | 𝜆 > 0, 𝑥 ∈ 𝐶}.
называется конической оболочкой подмножества 𝐶.
Если множество 𝐶 — выпуклое, то 𝐾(𝐶) является выпуклым конусом.
Заметим, что 𝐾(𝐶) не обязательно содержит начало координат. Тогда замыкание 𝐾(𝐶) задается следующим образом:
cone 𝐶 := 𝐾(𝐶) = 0𝑛
⋃︁
𝐾(𝐶).
Полученный оператор cone совпадает по определению с одноименным оператором из [2]. Определим несколько необходимых нам множеств.
Пусть задано множество точек 𝐴 = {𝑎0 , 𝑎1 , . . . , 𝑎𝑚 }, где все 𝑎𝑖 ∈ R𝑛 являются крайними для многогранника conv 𝐴. Не умаляя общности предположим,
что размерность аффинной оболочки множества conv 𝐴 равняется 𝑛, а также все
точки 𝑎𝑖 отличны друг от друга.
Зададим следующие вспомогательные множества. Вычтем 𝑎𝑖 из остальных
точек 𝐴 и зададим матрицу с размерностью 𝑛 × 𝑚
𝐴(𝑎𝑖 ) := (𝑎0 − 𝑎𝑖 , 𝑎1 − 𝑎𝑖 , . . . , 𝑎𝑖−1 − 𝑎𝑖 , 𝑎𝑖+1 − 𝑎𝑖 , . . . , 𝑎𝑚 − 𝑎𝑖 ).
Заметим, что в матрице 𝐴(𝑎𝑖 ) отсутствует нулевой столбец. В силу определения
множества 𝐴, нулевой столбец в 𝐴(𝑎𝑖 ) может быть получен только как разность
𝑎𝑖 − 𝑎𝑖 .
Обозначим выпуклый многогранный конус, натянутый на множество
{conv 𝐴 − 𝑎𝑖 } ∖ 0𝑛 , следующим образом
𝐾(𝑎𝑖 ) := 𝐾(conv
⋃︁
𝑗∈1:𝑚
где 𝐴(𝑎𝑖 )𝑗 — 𝑗-й столбец матрицы 𝐴(𝑎𝑖 ).
𝐴(𝑎𝑖 )𝑗 ),
7
Для иллюстрации описанных множеств рассмотрим пример:
{︃(︃ )︃ (︃ )︃ (︃ )︃}︃
0
−2
−2
𝐴=
,
,
,
3
6
1
𝑎1
{︃(︃ )︃ (︃ )︃}︃
−2
−2
𝐴(𝑎0 ) =
,
.
3
−2
𝑦
𝑎1 − 𝑎0
6
(3.1)
𝑦
3
𝐾(𝑎0 )
𝑎0
-2
𝑎2
-2
1
0
𝑎2 − 𝑎0
0
𝑥
-2
𝑥
б) 𝐾(𝑎0 )
а) conv 𝐴
Рисунок 3.1 — Изображения выпуклой оболочки множества 𝐴 и конуса 𝐾(𝑎0 )
Формализуем поставленную задачу. Рассмотрим сложение многогранника
conv 𝐴 c отрезком conv{𝑏0 , 𝑏1 }, 𝑏0 , 𝑏1 ∈ R𝑛 , 𝑏0 ̸= 𝑏1 :
conv 𝐴 + conv{𝑏0 , 𝑏1 } =
= conv{𝑎0 + 𝑏0 , 𝑎1 + 𝑏0 , . . . , 𝑎𝑚 + 𝑏0 , 𝑎0 + 𝑏1 , 𝑎1 + 𝑏1 , . . . , 𝑎𝑚 + 𝑏1 }.
(3.2)
Выражение (3.2) можно представить, как сумму точки и множества
conv 𝐴 + conv{𝑏0 , 𝑏1 } = 𝑏0 + conv 𝐴𝑣 ,
(3.3)
где 𝐴𝑣 = {𝑎0 , 𝑎1 , . . . , 𝑎𝑚 , 𝑎0 + 𝑣, 𝑎1 + 𝑣, . . . , 𝑎𝑚 + 𝑣}, 𝑣 = 𝑏1 − 𝑏0 .
Свяжем описанные множества с приведенными примерами. Для рис. 2.2
имеем 𝑏0 = (0, 0)𝑇 , 𝑏1 = (4, 0)𝑇 , множество 𝐴 из (3.1). Тогда выпуклая оболочка
conv 𝐴𝑣 изображена на рис. 2.2 б). Рассмотрим другое (3.3) представление суммы
многогранника и отрезка. Множество conv 𝐴𝑣 можно получить смещая conv 𝐴
на вектор 𝑣, при этом ≪запоминая≫ весь след смещения. В новых обозначениях
8
получим рис. 3.2.
𝑦
𝑎1
𝑎1 + 𝑣
6
𝑎0
1
𝑎2
-2
-1
0
𝑎0 + 𝑣
𝑎2 + 𝑣
2
𝑣
4
𝑥
Рисунок 3.2 — Множество 𝐴𝑣 и вектор смещения 𝑣
Выявим крайние точки множества conv 𝐴𝑣 . Справедлива следующая лемма [ANG].
Лемма 1. Для каждой точки 𝑎𝑖 из множества 𝐴 справедливо:
1. Если 𝑣 ̸∈ 𝐾(𝑎𝑖 ), то 𝑎𝑖 + 𝑣 является крайней для conv 𝐴𝑣 .
В противном случае 𝑎𝑖 + 𝑣 не является крайней для conv 𝐴𝑣 .
2. Если −𝑣 ̸∈ 𝐾(𝑎𝑖 ), то 𝑎𝑖 является крайней для conv 𝐴𝑣 .
В противном случае 𝑎𝑖 не является крайней для conv 𝐴𝑣 .
Замечание 1. Лемма (1) задает необходимое и достаточное условие крайности
точки для суммы многогранника и отрезка.
Проверим графически условия леммы для точек 𝑎0 и 𝑎0 + 𝑣 из рис. 3.2.
Изобразим конус 𝐾(𝑎0 ) и векторы 𝑣, −𝑣 (см. рис. 3.3).
9
𝑎1 − 𝑎0
𝑦
3
𝐾(𝑎0 )
−𝑣
𝑣
-2
𝑎2 − 𝑎0
0
𝑥
-2
Рисунок 3.3 — Проверка условий леммы
На рис. 3.3 видно, что 𝑣 ̸∈ 𝐾(𝑎0 ). Получаем, что точка 𝑎0 +𝑣 является крайней. Теперь рассмотрим второй пункт леммы. Вектор −𝑣 принадлежит конусу
𝐾(𝑎0 ). Тогда 𝑎0 не является крайней.
10
4. Решение задачи
4.1
Алгоритм проверки условий крайности
Пусть все нормали к граням множества conv 𝐴 направлены наружу относительно к conv 𝐴. Многогранник conv 𝐴 имеет грани 𝐹𝑘 , с нормалями 𝑛𝑘 ,
𝑘 ∈ 1 : 𝑚𝐹 (𝐴) . Грани 𝐹𝑘 задаются своими крайними точками, т.е.
𝐹𝑘 = conv{𝑎𝑘1 , . . . , 𝑎𝑘𝑚(𝐹𝑘 ) },
где все 𝑎𝑘𝑖 ∈ 𝐴, 𝑚𝐹 (𝐴) — количество крайних точек грани 𝐹𝑘 .
Зададим множество индексов активных граней, в которых участвует точка
𝑎𝑖 ∈ 𝐴, 𝑖 ∈ 1 : 𝑚:
𝐹 (𝑎𝑖 ) = {𝑘 ∈ 1 : 𝑚𝐹 (𝐴) | 𝑎𝑖 ∈ 𝐹𝑘 }.
Запишем принципиальный алгоритм, который проверяет условия леммы 1
для точек 𝑎𝑖 и 𝑎𝑖 + 𝑣, 𝑖 ∈ 0 : 𝑚.
Алгоритм
Для всех 𝑖 ∈ 0 : 𝑚 выполнить:
1. Выберем точку 𝑎𝑖 ∈ 𝐴. Найдем множество активных граней 𝐹 (𝑎𝑖 ).
2. Вычислим для всех 𝑘 ∈ 𝐹 (𝑎𝑖 ) скалярное произведение
𝑠𝑘 := ⟨𝑛𝑘 , 𝑣⟩.
Если хотя бы для одного индекса 𝑘 ∈ 𝐹 (𝑎𝑖 ) число 𝑠𝑘 > 0, то 𝑣 ̸∈ 𝐾(𝑎𝑖 ).
Переходим к шагу 3.
В противном случае переходим к шагу 4.
3. Точка 𝑎𝑖 + 𝑣 является крайней для conv 𝐴𝑣 . Переходим к шагу 5.
4. Точка 𝑎𝑖 + 𝑣 не является крайней для conv 𝐴𝑣 .
5. Для всех 𝑘 ∈ 𝐹 (𝑎𝑖 ) имеем
𝑠𝑘 := ⟨𝑛𝑘 , −𝑣⟩ = −𝑠𝑘 .
11
Если хотя бы для одного индекса 𝑘 ∈ 𝐹 (𝑎𝑖 ) выполняется 𝑠𝑘 > 0, то
−𝑣 ̸∈ 𝐾(𝑎𝑖 ). Переходим к шагу 6.
В противном случае переходим к шагу 7.
6. Точка 𝑎𝑖 является крайней для conv 𝐴𝑣 . Переходим к шагу 8.
7. Точка 𝑎𝑖 не является крайней для conv 𝐴𝑣 .
8. Конец рассмотрения индекса 𝑖.
Проиллюстрируем работу алгоритма на примере (3.1).
Пример работы алгоритма. Пусть
{︃
}︃
{︃(︃ )︃ (︃ )︃ (︃ )︃}︃
(︃ )︃
0
−2
−2
4
𝐴=
𝑎𝑖 =
,
,
, 𝑣=
,
3
6
1
0
𝑖=0:2
{︃(︃ )︃ (︃ )︃ (︃ )︃ (︃ )︃ (︃ )︃ (︃ )︃}︃
0
−2
−2
4
2
2
𝐴𝑣 =
,
,
,
,
,
.
3
6
1
3
6
1
⋃︁
Треугольник conv 𝐴 имеет стороны 𝐹𝑘 , с нормалями 𝑛𝑘 , 𝑘 ∈ 1 : 3:
𝐹1 = conv{𝑎0 , 𝑎1 }
𝐹2 = conv{𝑎1 , 𝑎2 },
𝐹3 = conv{𝑎2 , 𝑎0 },
(︃ )︃
3
𝑛1 =
2
(︃
(︃
𝑛2 =
−1
0
)︃
,
𝑛3 =
𝑦
𝑎1
6
𝑛1
𝑛2
𝑎0
𝑛3
𝑎2
-2
1
0
𝑥
Рисунок 4.1 — Нормали к граням conv 𝐴
Случай 𝑖 = 0:
1. Имеем 𝐹 (𝑎0 ) = {1, 3}.
1
−1
)︃
.
12
2.
𝑠1 = ⟨𝑛1 , 𝑣⟩ = 12,
𝑠3 = ⟨𝑛3 , 𝑣⟩ = 4.
Отсюда 𝑣 ̸∈ 𝐾(𝑎0 ).
3. Точка 𝑎0 + 𝑣 является крайней для conv 𝐴𝑣 .
5.
𝑠1 = ⟨𝑛1 , −𝑣⟩ = −12,
𝑠3 = ⟨𝑛3 , −𝑣⟩ = −4.
7.
8.
Случай
1.
2.
Отсюда −𝑣 ∈ 𝐾(𝑎0 ).
Точка 𝑎0 не является крайней для conv 𝐴𝑣 .
Конец рассмотрения индекса 𝑖 = 0.
𝑖 = 1:
Имеем 𝐹 (𝑎1 ) = {1, 2}.
𝑠1 = ⟨𝑛1 , 𝑣⟩ = 12,
𝑠2 = ⟨𝑛2 , 𝑣⟩ = −4.
Отсюда 𝑣 ̸∈ 𝐾(𝑎1 ).
3. Точка 𝑎1 + 𝑣 является крайней для conv 𝐴𝑣 .
5.
𝑠1 = ⟨𝑛1 , −𝑣⟩ = −12,
𝑠2 = ⟨𝑛2 , −𝑣⟩ = 4.
6.
8.
Случай
1.
Отсюда −𝑣 ̸∈ 𝐾(𝑎1 ).
Точка 𝑎1 является крайней для conv 𝐴𝑣 .
Конец рассмотрения индекса 𝑖 = 1.
𝑖 = 2:
Имеем 𝐹 (𝑎2 ) = {3, 2}.
13
2.
𝑠3 = ⟨𝑛3 , 𝑣⟩ = 4,
𝑠2 = ⟨𝑛2 , 𝑣⟩ = −4.
Отсюда 𝑣 ̸∈ 𝐾(𝑎0 ).
3. Точка 𝑎2 + 𝑣 является крайней для conv 𝐴𝑣 .
5.
𝑠3 = ⟨𝑛3 , −𝑣⟩ = −4,
𝑠2 = ⟨𝑛2 , −𝑣⟩ = 4.
Отсюда −𝑣 ̸∈ 𝐾(𝑎0 ).
6. Точка 𝑎2 является крайней для conv 𝐴𝑣 .
8. Конец рассмотрения индекса 𝑖 = 2.
По окончанию алгоритма идентифицируем точку 𝑎0 , как не являющейся крайней
для многоугольника conv 𝐴𝑣 . Удалим ее из 𝐴𝑣 и получим
{︃(︃ )︃ (︃ )︃ (︃ )︃ (︃ )︃ (︃ )︃}︃
−2
−2
4
2
2
conv 𝐴𝑣 = conv
,
,
,
,
.
6
1
3
6
1
4.2
Программная реализация
Опишем общую схему программной реализации.
1. Генерируется или задается множество точек 𝑀 в пространстве R𝑛 .
2. Вычисляется выпуклая оболочка множества 𝑀 . Набор полученных
крайних точек записывается в множество 𝐴. Сохраняется информация
о гранях 𝐹𝑘 многогранника conv 𝐴 и соответствующих нормалях 𝑛𝑘 ,
𝑘 ∈ 1 : 𝑚𝐹 (𝐴) .
3. Вводится вектор смещения 𝑣 ∈ R𝑛 . Строится массив allPoints, коотрый
⋃︀
соответствует множеству 𝐴𝑣 = {𝐴 {𝐴 + 𝑣}}.
4. Для всех точек из 𝐴𝑣 проверяется лемма 1. Выводится затраченное время на этот пункт. Крайние точки записывается в массиве resultPoints.
14
5. Вычисляется выпуклая оболочка множества 𝐴𝑣 . Полученные крайние
точки сравниваются с resultPoints. Если есть несовпадения, выводится
информация о конкретных нестыковках.
Алгоритм проверки леммы реализован на языке программирования
JavaScript с использованием библиотек quickhull3d [5] версии >= 2.0.0 для построения выпуклой оболочки в трёхмерном пространстве и t3-boilerplate версии
>= 0.2.7 для отображения модели. Для случая четырёхмерного, пяти-мерного и
шести-мерного пространств для построения выпуклой оболочки использовалась
библиотека Qhull [3] реализованная на языке программирования C.
В случае трёхмерного пространства для удобства задания первоначального
набора данных можно задать как параметры авто-генерации точек пространства
(по умолчанию), либо загрузить в корневую директорию проекта файл points.js
с набором точек в формате JSON. Пример содержания файла points.js:
var DIMENSIONS = 3;
var points = [ [0, 0, 0], [1, 0, 0], [0, 1, 0], [0, 0, 1] ];
Реализация алгоритма проверки леммы в трёх-мерном прострастве с построением 3D модели находится в файле libs/scripts.js, в папке libs находятся так
же вспомогательные библиотеки такие как JQuery версии 1.12.3 [6] и THREE [7].
Для запуска следует открыть файл index.html в любом современном браузере например Chrome или FireFox. Важно, чтобы браузер поддерживал современные
инструменты вроде canvas. Для получения подробной информации о ходе выполнения проверки следует запустить панель отладки браузера (Chrome, FireFox:
Ctrl + Shift + i). Настройки параметров авто-генерации и другие настройки находятся в теле файла index.html. При загрузке файла index.html происходит построение выпуклой оболочки с помощью библиотеки quickhull3d и отображение результата на сцене с помощью библиотек t3-boilerplate и THREE, а так
же отображается набор нормалей для граней выпуклой оболочки. Пользователю предлагается задать смещение 𝑣, относительно осей координат 𝑥, 𝑦, 𝑧, точек
отобранных для построения выпуклой оболочки алгоритмом Quickhull. После
указания смещения следует нажать кнопку “Построить”. В результате отобразится исходная выпуклая оболочка с заданным смещением. Далее для запуска
алгоритма построения результирующей выпуклой оболочки с помощью леммы,
с включением исходных точек и точек смещения (множество 𝐴𝑣 ) следует нажать
кнопку “Проверить”.
15
Описание алгортма.
На первоначальном этапе исходные точки (𝑀 ) записываются в массив points
глобального контекста
// исходный набор точек
var points = [];
По исходному набору точек просходит построение выпуклой оболочки conv 𝐴 с
помошью библиотеки quickhull3d (см. рис. (4.2))
faces = qh(points);
Массив faces (𝐹𝑘 ) представляет из себя массив граней выпуклой оболочки с
нормалями (𝑛𝑘 ) к ним. Далее выполняется построение 3D модели по заданным
точкам и граням выпуклой обочки с нормалями. В процессе построения заполняются массивы normals - массив нормалей, pointNormals (нобор нормалей для
каждой из точек граней) и массив qhPointsLinks — ссылки на точки выпуклой
оболочки в исходном массиве points.
Рисунок 4.2 — Выпуклая оболочка множества 𝐴
На этапе построения смещения относительно осей координат, заполняются
массивы newPoints - точки для построения выпулой оболчки смещения и массив
allPoints (𝐴𝑣 ) - точки включающие в себя исходный набор и точки смещения.
var i;
newPoints = points.slice();
16
allPoints = points.slice();
var x = parseInt(document.querySelector("♯coefficientX").value);
var y = parseInt(document.querySelector("♯coefficientY").value);
var z = parseInt(document.querySelector("♯coefficientZ").value);
if (isNaN(x)) {
x = 0;
}
if (isNaN(y)) {
y = 0;
}
if (isNaN(z)) {
z = 0;
}
for (i = 0; i < qhPointLinks.length; i += 1) {
var point = [
parseFloat(points[qhPointLinks[i]][0]) + x,
parseFloat(points[qhPointLinks[i]][1]) + y,
parseFloat(points[qhPointLinks[i]][2]) + z
];
newPoints[qhPointLinks[i]] = point;
allPoints.push(point);
}
Далее происходит построение смещённой выпуклой оболочки по точкам
массива newPoints аналогично первому этапу (см. рис. (4.3)), при этом нормали
и набор pointNormals заполняется заново, сами нормали остаются неизменными
как и ссылки на точки выпуклой оболочки в этих массивах.
На завершающем этапе проверки используется лемма 1 для отбора точек
выпуклой оболчки и происходит проверка этих точек посредством сравнения
каждой точки с точкой отобранной по алгоритму Quickhull для набора точек
allPoints. По условиям леммы для каждой точки граней pointNormals проверям
скалярное произведение вектора (𝑣) построенного из точка А исходной выпуклой оболочки в точку A’ смещённой выпуклой оболочки.
var result;
var i;
17
Рисунок 4.3 — Выпуклые оболочки множеств 𝐴 и 𝐴 + 𝑣
var a, b;
//Строим вектор AA’ (v) где A’ (ai + v) точка смещения
a = [newPoints[index][0] - points[index][0], newPoints[index][1] points[index][1], newPoints[index][2] - points[index][2]];
//Проверяем условия леммы
for (i = 0; i < item.length; i += 1) {
//Вычисляем скалярное произведения вектора AA’ (v) и нормалей к
граням которые содержат точку A
result = (a[0]*item[i].x) +
(a[1]*item[i].y) +
(a[2]*item[i].z);
//Если скалярное произведение < 0 то прерываем цикл
if (result < 0) {
break;
}
}
//Если скалярное произведение < 0 добавляем точку в результирующий
массив
if (result < 0) {
18
resultPoints.push(points[index]);
} else {
excludedPoints.push(points[index]);
}
Аналогично производится проверка ветора A’A (-v) в результате мы
получаем набор точек resultPoints - крайние точки множества conv 𝐴𝑣 и набор
excludedPoints - точки не удовлетворяющие условиям отбора. На рис. 4.4
некрайние точки показаны синими кружками. Далее по точкам allPoints (𝐴𝑣 )
происходит построение выпуклой оболочки. Сравниваются крайние точки
последней с resultPoints.
Рисунок 4.4 — Идентифицированные точки леммой и conv 𝐴𝑣
console.log(’Построение выпуклой оболочки смещения’);
var resultFaces = qh(resultPoints);
buildHull(this, resultPoints, resultFaces)
console.log(’Количество точек’, qhPointLinks.length, resultPoints.length);
resultFaces = qh(allPoints);
buildHull(this, allPoints, resultFaces)
console.log(’Проверка количества точек’, qhPointLinks.length);
for (var i = 0; i < resultPoints.length; i++) {
19
var noMatch = true;
for (var j = 0; j < qhPointLinks.length; j++) {
if (allPoints[qhPointLinks[j]][0] === resultPoints[i][0] &&
allPoints[qhPointLinks[j]][1] === resultPoints[i][1] &&
allPoints[qhPointLinks[j]][2] === resultPoints[i][2]
){
console.log(’match: ’ + i, resultPoints[i]);
noMatch = false;
break;
}
}
if (noMatch) {
console.log(’ERROR: ’ + i, resultPoints[i]);
}
}
if (excludedPoints.length > 0) {
for (var i = 0; i < excludedPoints.length; i += 1) {
console.log(’Excluded: ’ + i, excludedPoints[i]);
}
}
Для проверки работы алгоритма в 4х 5ти и 6ти мерном пространствах, будет использован сервис [4], который представляет собой API для доступа к пакету qhull.org. Сервис принимает на вход два не обязательных параметра. Первый
принимает значение вида D1 - D6 (http://freestel.ru/api/qhull/D4), которое определяет размерность пространства. Второй аргумент указывает количество точек,
если используется сценарий автоматической генерации точек на стороне сервиса через утилиту rbox (http://freestel.ru/api/qhull/D4/100) из пакета qhull. Сервис
отдаёт набор граней и нормалей к ним, используя результат работы утилиты
qconvex из пакета qhull. Все остальные пункты проверки леммы аналогичны
пунктам для 3-х мерного пространства.
20
5. Заключение
В работе разработан программный пакет на языке JavaScript для численной
проверки необходимого и достаточного условия крайности точек суммы двух
многогранников. Крайние точки сравнивались с результатами нахождения выпуклой оболочки этой суммы. Численные эксперименты подтверждают теоретические результаты. В трехмерном случае удалось наглядно изобразить каждый
этап программной реализации.
21
Список литературы
[1] Ангелов Т. А. Нахождение крайних точек суммы двух политопов. Семинар
«CNSA & NDO». Избранные доклады. 05 мая 2016.
[2] Рокафеллар Р. Выпуклый анализ // М.: Мир, 1973. 472 с.
[3] Barber C. B., Dobkin D. P., Huhdanpaa H. T. The Quickhull algorithm for
convex hulls // ACM Trans. on Mathematical Software. 1996. 22. 469–483
(http://www.qhull.org).
Электронные ресурсы:
[4] http://freestel.ru/api/qhull
[5] https://github.com/maurizzzio/quickhull3d
[6] http://jquery.com
[7] http://treejs.org
Отзывы:
Авторизуйтесь, чтобы оставить отзыв