Cтраница 2
Центровка по полумуфтам состоит в замерах по торцу - с целью определения пересечений осей валов ( роторов) и в замерах по окружности полумуфт - с целью определения смещения осей в четырех положениях валов последовательным поворотом их на 90 в пределах полной окружности. [16]
Важным аргументом при выборе способа математического описания для представления поверхности служит простота решения некоторых важных задач машинной графики, например определения пересечения двух поверхностей. Очевидно, что для этого больше всего подходят плоскости, однако при большом числе конечных участков поверхности, ограниченных замкнутыми кривыми, общий объем вычислений может оказаться значительным. Поверхности, построенные с помощью 5-сплайнов, обладают свойством выпуклой оболочки ( см. утверждение И. Число таких плоскостей может оказаться значительно меньше, чем необходимо при аппроксимации многогранниками, и, следовательно, задачи на пересечение и подобные им легче решать, оперируя этими плоскостями. Дополнительные затраты, связанные с определением точного пересечения, часто очень малы. В самом деле, большинство выпуклых оболочек вообще не пересекаются, и, следовательно, отсутствует необходимость проверять, не пересекаются ли соответствующие поверхности. При составлении карт местности, ориентированных на машинную картографию, очевидно, целесообразно использовать плоскости, поскольку требования к гладкости изображения не очень высоки. [17]
На рис. 181 6 множество точек, соответствующих событию А - - В, обозначено штриховкой в одном направлении, а событию А С - штриховкой в другом направлении. Из определения пересечения событий следует, что событию ( A - f - В) ( А Ц - С) соответствует множество точек, где есть штриховка и в одном, и в другом направлении. Это множество точек обведено жирной линией. Из сравнения рис. 181, а и 181 6 следует, что события Л ( ВС) и ( A - f - В) ( А С) эквивалентны. [18]
Определение пересечения двух многоугольников представляет существенный интерес для решения проблемы разделения видимых и невидимых элементов воспроизводимого объекта и является наиболее общей постановкой задачи разрезания. Задачу определения пересечения двух многоугольников можно решить при помощи многократного применения алгоритма 15.3. Рассмотрим многоугольники Eli и Eli, причем будем считать, что многоугольник П2 - выпуклый. [19]
С следует, по определению пересечения, что a. Рассмотрим второй случай: а. [20]
Геометрические алгоритмы ( Часть 6) - это методы решения задач с использованием точек и линий ( и других простых геометрических объектов), которые стали использоваться лишь недавно. Мы рассмотрим алгоритмы для отыскания образующей поверхности, определенной набором точек, определения пересечений геометрических объектов, решения задач отыскания ближайших точек и для выполнения многомерного поиска. Многие из этих методов прекрасно дополняют более элементарные методы сортировки и поиска. [21]
При воспроизведении изображения многоугольника, который может не быть выпуклым на участке окна наблюдения, представляющего собой правильный прямоугольник, можно либо рассмотреть разрезание каждой из сторон многоугольника окном ( с помощью алгоритма 15.2), либо разрезание всего многоугольника каждой из сторон окна. Для решения последней задачи предназначен алгоритм 15.3. Его можно также использовать в качестве базового алгоритма для определения пересечения двух произвольных многоугольников. [22]
N отрезков на плоскости достаточно Q ( N ogN) операций. Что произойдет, если потребовать, чтобы эти N отрезков были ребрами какого-нибудь многоугольника. В этом случае задача определения пересечения сводится к проверке простоты многоугольника, и было бы интересно исследовать вопрос о том, приводит ли это дополнительное условие к упрощениям алгоритма. По сей день для задачи о ПРОВЕРКЕ ПРОСТОТЫ МНОГОУГОЛЬНИКА не удается дать оценку сложности. К сожалению, эта оценка не повлияла на оценку сложности решения задачи о ПРОВЕРКЕ ПРОСТОТЫ МНОГОУГОЛЬНИКА, поскольку преобразование последней к задаче о ПЕРЕСЕЧЕНИИ РЕБЕР МНОГОУГОЛЬНИКА направлено в обратную сторону. Поэтому вопрос об оценке сложности задачи о ПРОВЕРКЕ ПРОСТОТЫ МНОГОУГОЛЬНИКА остается замечательной нерешенной проблемой вычислительной геометрии. [23]
В настоящей работе под обобщением объектов-графов понимают подграфы, общие для исследуемого множества объектов. Использование теоретике-множественной операции пересечения в этой работе основано на предположении, что все вершины каждого. Однако в некоторых случаях такое определение пересечения оказывается недостаточным, что можно показать на простом примере. [24]
Наблюдаемость некоторого объекта часто можно определить, рассматривая некоторое описывающее его тело, форма которого может быть весьма простой, - это может быть сфера или многогранник с гранями, параллельными координатным плоскостям. Это некоторое обобщение идеи, использованной для определения пересечения многоугольников в разд. [25]
Однако следует отметить, что, если т - малое число ( скажем, 3 или 4), как это часто бывает в прикладных задачах машинной графики, повышение эффективности процедуры может оказаться невозможным. Экономия, полученная за счет уменьшения числа осмотров одной вершины, может утрачиваться вследствие роста объема учетных операций. Поэтому проводимое в этом разделе обсуждение, относится к задаче определения пересечения двух многочленов лишь в случае, когда у обоих число вершин значительно. Существенное значение для машинной графики имеют алгоритмы, обеспечивающие эффективное определение попарных пересечений для большого числа многоугольников. Именно такая ситуация возникает при решении задачи разделения видимых и невидимых частей воспроизводимого объекта, а также при проверке рисунка схемы, особенно в случае высокой степени интеграции. Здесь также применимы принципы, положенные в основу эффективных алгоритмов определения пересечения многоугольников. [26]
В статье [17.2] обсуждаются теоретические аспекты подхода, основанного на использовании пространства объектов. В докладе [17.4] изложен алгоритм того же типа, что и алгоритм 17.1, однако оснащенный тщательно разработанной стратегией определения пересечений фрагмента изображения и грани. В результате обеспечен переход от квадратичной временной сложности к линейной. В докладе [17.6] рассматривается комбинация межкадровой однородности по наблюдаемости и однородности объекта по наблюдаемости. [27]
С помощью этих открытых овалов показывали, например, что такое пересечение и объединение множеств, как они связаны с дополнениями. Если, скажем, лектор объяснил это и хочет убедиться, что слушатели поняли данные определения, он изображает два пересекающихся овала и спрашивает: Если это - множество взрослых людей, а это - множество лиц женского пола, то что представляет собой общая часть. Однако в старой математике я ни разу не видел, чтобы для определения пересечения множества взрослых людей и множества лиц женского пола изображали диаграммы Венна и рассуждали о них. Но ныне диаграммы Венна часто используют именно для этого. [28]
Вычислим жтш, жтах, жтт, жтах и проверим, пересекаются ли проекции на ось ОХ. Если они пересекаются, то вычислим г / шш, 2 / ах, У ш, У ах и проверим, пересекаются ли проекции на ось OY. Если пересекаются проекции на оси ОХ и OY, то найдем координаты точки пересечения прямых, проверив ее принадлежность обоим отрезкам. Все пересечения устраняются за конечное число просмотров маршрута. При этом процедура определения пересечения переходов применяется ( п - 2) ( п - 3) / 2 раз. [29]
Основной причиной изучения задач о пересечениях явился тот простой факт, что два объекта не могут одновременно находиться в одном и том же месте. Программа, предназначенная для архитектурного проектирования, должна внимательно позаботиться о том, чтобы двери не оказались там, где их невозможно открыть, а коридоры не проходили через шахту лифта. В машинной графике один объект, подлежащий выводу, заслоняет другой, если их проекции на картинную плоскость пересекаются. Выкройки можно вырезать из одного куска материи только тогда, когда их удается разложить так, что они не накрывают одна другую. Важность разработки эффективных алгоритмов определения пересечений станет ясной, если учесть, что в промышленных приложениях происходит постоянный рост сложности задач: сложное графическое изображение может состоять из сотни тысяч векторов, архитектурная база данных зачастую содержит свыше миллиона элементов, а одна интегральная схема может содержать миллионы компонентов. В подобных случаях даже квадратичные алгоритмы неприемлемы. [30]