Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
С точки зрения усилий, затраченных на развитие графической аппаратуры, вызывает удивление то, что вопросу о сложности решения задачи удаления невидимых линий уделялось
328
Гл. 7. Пересечения
так мало внимания, поскольку именно здесь можно получить наибольший выигрыш. Конструирование черного ящика, снабженного'микропрограммой даже при использовании параллельных вычислений, не способно, как правило, дать эффект, сравнимый с тем, что дает использование новейших алгоритмических методов (причем разрыв растет при увеличении размеров задачи).
Во многих случаях, особенно для векторных дисплеев, компонентами сцены являются многоугольники. Если проекциями двух объектов являются многоугольники Р\ и Р2, a Pi ближе к зрителю, чем Р2, то необходимо изобразить Pi и РгП-Pi (понятно, что Р2[\Р\ — это пересечение Р2 и дополнения к Pi).
Таким образом, основная вычислительная задача при удалении невидимых линий состоит в формировании пересечения двух многоугольников. На практике нужно сделать нечто большее, ибо изображение будет складываться из множества разных многоугольников, каждый из которых необходимо вывести, и тем не менее можно ожидать, что в основе алгоритма останется определение попарных пересечений. Не обладая оптимальным алгоритмом пересечения многоугольников, нельзя рассчитывать на эффективную реализацию удаления невидимых линий. В данной главе будут получены точные оценки алгоритмов пересечения для выпуклых, звездных и произвольных многоугольников. Задача с многоугольниками является примером первого типа из числа рассматриваемых нами задач о пересечениях. Для сохранения желаемого уровня общности рассуждений будем указывать род геометрических объектов, которые могут быть многоугольниками, отрезками, полиэдрами и т. п., только тогда, когда это потребуется в конкретном приложении. Итак, имеется:
Задача типа С. 1') (ПОСТРОЕНИЕ ПЕРЕСЕЧЕНИЯ). Даны два геометрических объекта. Надо построить их пересечение.
7.1.2. Разпознавание образов
Одним из основных методов распознавания образов является классификация путем контролируемого обучения2). Даны N точек, каждая из которых идентифицируется по принадлежности к одному из m классов; нужно их предварительно обработать таким образом, чтобы любую новую точку (пробную точку) можно было корректно классифицировать. На рис. 7.2 показан двумерный пример, на котором оси соответ-
') С — аббревиатура слова «сечение». — Прим. перев.
2) Детали многих геометрических задач, возникающих при распознавании образов, можно найти в работах [Andrews (1972), Duda, Hart (1973), Meisel (1972)].
7.1. Примеры из приложений
329
ствуют весу и росту людей, принадлежащих к некой группе сверстников. Мужчины обозначены буквой «М», женщины — буквой «Ж». Буквой «Ч» обозначен человек, чьи вес и рост известны. Можно ли классифицировать Ч, основываясь только на значениях этих параметров? Каким решающим правилом надлежит воспользоваться?
Желательно получить, если это возможно, линейный классификатор, т. е. такую линейную функцию f, чтобы для определения класса, к которому относится Ч, было достаточно
V «Л!
Рис. 7.2. Задача классификации с двумя переменными.
одного вычисления (собственно вычисления линейной функции и сравнения):
if / (хч, уч) > Т then ЧеМ else ЧеД.
В последнем выражении через Т обозначено пороговое значение. В пространстве k измерений f(xu х2, xk)=T является гиперплоскостью; при двух измерениях это прямая. Линейный классификатор считается хорошим, если он разделяет классы друг от друга так, что все точки типа М лежат по одну его сторону, а все точки Ж — по другую.
Определение 7.1. Два множества называются линейно разделимыми тогда и только тогда, когда существует такая гиперплоскость Н, которая их разделяет.
Тем самым определение факта существования линейного классификатора является средством решения вопроса о разделимости обучающих выборок. Разделимость — это классическая задача комбинаторной геометрии. Основной критерий линейной разделимости дает следующая теорема:
Теорема 7.1 [Stoer, Witzgall (1970), теорема 3.3.9]. Два множества точек линейно разделимы тогда и только тогда, когда их выпуклые оболочки не пересекаются.
330
Гл. 7. Пересечения
Эта теорема проиллюстрирована для плоского случая на рис. 7.3. Поскольку известно, что выпуклой оболочкой конечного множества точек является выпуклый политоп, то линейная разделимость определяется проверкой пересечения двух выпуклых политопов. Последняя задача является примером задач следующего типа.
Разделимы Неразделимы
Рис. 7.3. Два множества разделимы тогда и только тогда, когда их выпуклые оболочки не пересекаются.
Задача типа С.2 (ПРОВЕРКА ПЕРЕСЕЧЕНИЯ). Даны два геометрических объекта. Пересекаются ли они?
Позднее будет показано, что проверка пересечения зачастую проще, чем соответствующая ей задача построения.
7.1.3. Трассировка и размещение
Поскольку микроминиатюризация в электронике достигла фантастических темпов, то количество компонент в чипах, проводников на платах и проводов в схемах выросло настолько, что подобное оборудование невозможно спроектировать без помощи ЭВМ. Число элементов в одной интегральной схеме вполне может превысить миллион, и каждый из них должен быть размещен конструктором с учетом множества физических и геометрических ограничений. Используемые при этом программы основаны на эвристиках и часто дают некорректные решения, например наложения компонент схемы или пересечения проводников (см. [Akers (1972); Hanan, Kurzberg (1972); Hanan (1975)]). Эвристические методы используются, поскольку некоторые из задач, связанных с размещением компонент, являются NP-полными [Garey, Johnson, Stockmeyer (1976)]. Следовательно, решения необходимо подвергать тщательной проверке, состоящей из попарных сравнений всех элементов чипа, что дорого и требует много времени. Это приводит к следующему теоретически важному классу задач.
