Параллельное программирование

Особенности применения косинуса как функции меры угла - часть 2


Аналогично, из второй строки находим {p2, p1}, что определяет ту же вершину. Третья строка определяет возможное множество образующих {p3, p2}, что не подтверждается проверкой. Четвертая строка также не определяет правильный выбор образующих {p4, p1}.

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

На рис. 6.7 Qнижн={p1, p2, p3, p4, p5}.

"Критические" случаи

Рис. 6.7.  "Критические" случаи

Таблица косинусов углов имеет вид

Таблица 6.3.

ГраньНормальN1 N2N3 N4 N5
p1 N1 1 0-1-v2/2v2/2
p2 N2 0 10v2/2v2/2
p3 N3 -1 01v2/2-v2/2
p4 N4 -v2/2 v2/2v2/210
p5 N5 v2/2 v2/2-v2/201

Легко видеть, что анализ любой строки не позволит обнаружить вершину многогранника R.

Действительно, по первой строке формируется предполагаемое множество образующих {p1, p4}. Однако пересечение этих прямых не дает искомую вершину. И так — по всем строкам. Если бы было установлено, что ось y не входит в состав поверхности R, то соответствующий косинус можно бы было игнорировать, что привело бы к правильному выбору множества образующих {p1, p2}.

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

n, то на первом этапе поиска исключим из рассмотрения координатные плоскости. Это приведет к исключению из табл. 6.3

двух последних строк и столбцов. Легко видеть, что поиск вершины осуществляется успешно.

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




Начало  Назад  Вперед



Книжный магазин