Поскольку столкновения с кругом всегда сводятся к сравнению с радиусом (в вашем случае через проекцию), наличие ближайшего сегмента линии (края многоугольника) и вектора нормали — это единственные строительные блоки, которые вам нужны. Вектор нормали легко вычисляется из точек сегмента прямой (что-то вроде единицы (y2-y1, x1-x2)... отрицательной обратной величины наклона). Выяснение того, какое ребро ближе всего, является строительным блоком, который остается. Вороной район дает нам последний кирпичик.
Вы понимаете коллизии между выровненными по осям ограничивающими рамками. Я предполагаю, что вы также понимаете столкновения между двумя кругами. Я предполагаю, что вы не понимаете вороных регионов. Итак, с чего начать? Диаграммы Вороного. Я настоятельно рекомендую вам найти схематическое объяснение. Эта ссылка довольно хороша. Однако, в зависимости от того, насколько вы заблудились, возможно, небольшой дополнительный фон (хотя серьезно, никакое объяснение не может сравниться с визуальным):
Диаграмма Вороного — одна из самых распространенных структур данных вычислительной геометрии. В любой книге по вычислительной геометрии будет обсуждаться диаграмма Вороного. Он отвечает на простой вопрос: где находится ближайшее почтовое отделение? Учитывая набор точек на плоскости (почтовые отделения), диаграмма Вороного разделяет плоскость на разные области, каждая из которых содержит одну из точек. Если вы находитесь в конкретном регионе, вы знаете, какой пункт (почта) к вам ближе всего. Если бы вы были кругом, это было бы неплохо для обнаружения столкновений по простой причине: ближайшая точка является наиболее важной для проверки на столкновение.
Обратите внимание, что если вы хотите математически вывести диаграмму Вороного, вы просто рассматриваете все пары точек и вычисляете все пересекающиеся линии. Затем вы пересекаете все биссектрисы и отбрасываете отрезки, которые не важны, потому что какая-то другая точка находится ближе к интересующей вас точке (что происходит при каждом пересечении). Однако это приводит к ужасно неэффективному алгоритму. Эффективная реализация включает в себя еще одну повсеместную вещь в вычислительной геометрии: алгоритм линейной прогонки. Его детали можно найти в другом месте; важно то, что он обеспечивает метод рассмотрения только важных моментов на любом этапе алгоритма.
Области Вороного в вашем уроке немного сложнее. Вместо точек у нас есть отрезки. К счастью, алгоритм линейной развертки прекрасно с этим справляется. В основном вам нужно беспокоиться о начале или конце сегментов линии. Концептуально мало что изменится, если у вас есть базовый алгоритм. Опять же, это исключительно полезно для обнаружения столкновений с кругом: учитывая область Вороного, вы знаете, на каком отрезке линии проверять столкновения.
Это даже помогает? Обратная связь приветствуется. Я буду рад прояснить что-нибудь. Объяснение диаграмм Вороного без наглядности, наверное, плохая идея.
person
ccoakley
schedule
27.05.2011
