Трафаретные прыжки
Переход по трафарету , иногда называемый обходом по трафарету , представляет собой алгоритм определения местоположения элемента сетки, охватывающего заданную точку, для любой структурированной сетки. Проще говоря, учитывая точку и структурированную сетку , этот алгоритм поможет найти элемент сетки, который будет окружать данную точку.
Этот алгоритм находит широкое применение в вычислительной гидродинамике (CFD) с точки зрения вырезания отверстий и интерполяции, когда две сетки лежат одна внутри другой. Другие варианты задачи могут быть примерно такими: задано место, на какой широте и долготе оно находится? Алгоритм грубой силы определит расстояние точки от каждой точки сетки и определит, какая из них наименьшая. Другой подход заключается в использовании алгоритма двоичного поиска , который даст результат, сравнимый по скорости с алгоритмом перехода по трафарету. Сочетание бинарного поиска и алгоритма перехода по трафарету даст оптимальный результат за минимально возможное время.
Принцип
[ редактировать ]
Для простоты рассмотрим один элемент двумерной сетки, как показано на рисунке, и рассмотрим точку O внутри. Вершины элемента сетки обозначены A, B, C и D, а векторы AB, BC, CD, DA, OA, OB, OC и OD представлены. Перекрестное произведение OA и AB даст вектор, перпендикулярный плоскости, выходящей из экрана. Мы говорим, что величина векторного произведения положительна. Можно заметить, что перекрестные произведения OB и BC, OC и CD; и OD и DA все положительные.

Это не тот случай, когда точка находится снаружи. Здесь мы видим, что не все перекрестные произведения положительны. Это основной критерий тестирования в алгоритме.
Как оно продвигается вперед?
[ редактировать ]Для начала алгоритму нужен элемент сетки предположений. Элемент сетки можно найти по местоположению одной точки, скажем, A. Остальные точки можно найти автоматически, получив последующие точки. Требуемые векторные произведения затем находятся в порядке
- ОА × АБ
- OB × BC
- ОК × CD
- ОТ × ДА
Каждое из этих векторных произведений проверяется одно за другим (в указанном порядке), какое из них первым становится отрицательным. Если OA × AB сначала становится отрицательным, следующее предположение должно быть на шаг впереди по DA. Если сначала OB × BC отрицательна, пройдите по AB на один шаг, чтобы найти следующее предположение, и так далее.
Алгоритм сходится именно к тому элементу сетки, где все векторные произведения положительны.
См. также
[ редактировать ]Ссылки
[ редактировать ]![]() | Эта статья включает список общих ссылок , но в ней отсутствуют достаточные соответствующие встроенные цитаты . ( Июль 2018 г. ) |
- Руди А. Джонсон; Дэви М. Белк (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 .