Прыжки по трафарету - Stencil jumping

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

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

Принцип

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

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

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

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

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

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

OA × AB
OB × BC
OC × CD
OD × DA

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

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