Jump to content

Трафаретные прыжки

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

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

Точка О лежит внутри элемента сетки ABCD.

Для простоты рассмотрим один элемент двумерной сетки, как показано на рисунке, и рассмотрим точку O внутри. Вершины элемента сетки обозначены A, B, C и D, а векторы AB, BC, CD, DA, OA, OB, OC и OD представлены. Перекрестное произведение OA и AB даст вектор, перпендикулярный плоскости, выходящей из экрана. Мы говорим, что величина векторного произведения положительна. Можно заметить, что перекрестные произведения OB и BC, OC и CD; и OD и DA все положительные.

Точка О лежит вне элемента сетки ABCD.

Это не тот случай, когда точка находится снаружи. Здесь мы видим, что не все перекрестные произведения положительны. Это основной критерий тестирования в алгоритме.

Как оно продвигается вперед?

[ редактировать ]

Для начала алгоритму нужен элемент сетки предположений. Элемент сетки можно найти по местоположению одной точки, скажем, A. Остальные точки можно найти автоматически, получив последующие точки. Требуемые векторные произведения затем находятся в порядке

  1. ОА × АБ
  2. OB × BC
  3. ОК × CD
  4. ОТ × ДА

Каждое из этих векторных произведений проверяется одно за другим (в указанном порядке), какое из них первым становится отрицательным. Если OA × AB сначала становится отрицательным, следующее предположение должно быть на шаг впереди по DA. Если сначала OB × BC отрицательна, пройдите по AB на один шаг, чтобы найти следующее предположение, и так далее.

Алгоритм сходится именно к тому элементу сетки, где все векторные произведения положительны.

См. также

[ редактировать ]
  • Руди А. Джонсон; Дэви М. Белк (1993). «МНОГОСЕТОЧНЫЙ ПОДХОД К РЕШАТЕЛЯМ ВСТРОЕННЫХ СЕТОК» (PDF (требуется плата) . Технические отчеты: ВВС США, лаборатория Райта, авиабаза Эглин . АИАА-1993-769 . Проверено 31 мая 2007 г.
  • Э.Г. Патерсон; Р.В. Уилсон; Ф. Стерн (май 1998 г.). CFDSHIP-IOWA и моделирование RANS с устойчивым потоком модели DTMB 5415 (PDF) . 1-й симпозиум по морскому применению CFD. п. 5. Архивировано из оригинала (PDF) 27 октября 2004 г. Проверено 31 мая 2007 г.
  • Прюитт, Натан С; Белк, Дэви М; Застенчивый, Вэй (2000). «Параллельное вычисление сеток смещения для аэродинамических задач с движущимися объектами». Прогресс аэрокосмических наук . 36 (2):117. Бибкод : 2000ПрАэС..36..117П . дои : 10.1016/S0376-0421(99)00013-5 .
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 73f9bf5891309436f784fc385b0cf55e__1620001080
URL1:https://arc.ask3.ru/arc/aa/73/5e/73f9bf5891309436f784fc385b0cf55e.html
Заголовок, (Title) документа по адресу, URL1:
Stencil jumping - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)