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