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

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

Этот алгоритм находит широкое применение в вычислительной гидродинамике (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 на один шаг, чтобы найти следующее предположение, и так далее.

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

См. также

Пятиточечный трафарет

Ссылки

Руди А. Джонсон; Дэви М. Белк (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 .

Внешние ссылки

программное обеспечение пегас