Простой способ вычислить точку пересечения между двумя полигонами в C #

Question

У меня есть два многоугольника, определенных как список векторов, мне удалось написать подпрограммы для преобразования и пересечения этих двух многоугольников (см. Кадр 1).Используя пересечение линий, я могу выяснить, сталкиваются ли они, и написал рабочую функцию Collide ().

Это должно использоваться в игре с переменным шагом по времени, и поэтому (как показано ниже) в кадре 1 правый многоугольник не сталкивается, это нормально для кадра 2, так как многоугольники находятся прямо внутри каждогодругой, с правым многоугольником, сместившимся влево.

Мой вопрос: как лучше всего определить момент пересечения?В этом примере давайте предположим, что в кадре 1 правый многоугольник находится в точке X = 300, во втором кадре он переместился в -100 и теперь находится в 200, и это все, что я знаю к моменту появления второго кадра, это было в 300, теперь этона 200. То, что я хочу знать, это когда он действительно столкнулся, при каком значении X, здесь, вероятно, было около 250.

Я предпочтительно ищу C #Исходный код решения этой проблемы.Может быть, есть лучший способ подойти к этому для игр?

Answer 1

Если у вас есть возможность определить, перекрываются ли два полигона, одной из идей может быть использование модифицированного бинарного поиска для обнаружения места попадания двух полигонов.Начните с деления временного интервала пополам и посмотрите, пересекаются ли два многоугольника в средней точке.Если так, рекурсивно ищите первую половину диапазона;если нет, ищите вторую половину.Если вы укажете некоторый уровень допуска, при котором вам больше не нужны небольшие расстояния (например, на уровне пикселя), тогда время выполнения этого подхода будет O (log D / K), где D - расстояние между полигонами.и K - порог отсечки.Если вы знаете, какая точка в конечном итоге войдет во второй многоугольник, вы сможете очень быстро обнаружить столкновение таким образом.

Надеюсь, это поможет!

Answer 2

Я тоже не математик, но одним из возможных, хотя и грубым решением было бы запустить мини-симуляцию.

Давайте назовем движущийся многоугольник M и стационарный многоугольник S (хотя S не требуется на самом деле быть стационарным, подход должен работать одинаково независимо).Давайте также назовем два фрейма, которые у вас есть F1 для более раннего и F2 для более позднего, согласно вашей диаграмме.

Если вы должны были перевести многоугольник M обратно к своей позиции в F1 с очень небольшими приращениями до тех пор, пока они больше не пересекаются, тогда у вас будет место для M , в котором оно "просто'пересекается, то есть предыдущее местоположение, прежде чем они перестают пересекаться в этой симуляции.Пересечение в этом «просто» месте пересечения должно быть очень маленьким - достаточно маленьким, чтобы вы могли рассматривать его как точку.Давайте назовем этот многоугольник пересечения I .

Чтобы рассматривать I как точку, вы можете выбрать его вершину, ближайшую к центральной точке M in F1 : у этой вершины больше всего шансов оказаться за пределами S во время столкновения.(Существует множество других возможностей для интерпретации I как точки, с которой вы тоже можете поэкспериментировать, что может иметь лучшие результаты.)

Очевидно, что этот подход имеет некоторые недостатки:

• Симуляция будет медленнее для больших скоростей M , так как расстояние между его местоположениями в F1 и F2 будет больше, больше шагов симуляции будетнужно бежать.(Вы можете решить эту проблему, имея фиксированное число циклов моделирования независимо от скорости M , но это будет означать, что точность результата будет отличаться для более быстрых и медленных движущихся тел.)
• Размер «шага» в симуляции должен быть достаточно мал, чтобы получить требуемую точность, но меньшие размеры шага, очевидно, будут иметь большую стоимость вычислений.

Лично, без необходимой математической интуиции, япойдет сначала с этим простым подходом, а позже попытается найти математическое решение в качестве оптимизации.

Answer 3

Я бы использовал теорему о разделительной оси, как изложено здесь:

• Учебник Metanet
• Wikipedia

Тогда я бы развернул тест или использовал мультисэмплинг , если необходимо.

GMan здесь, в StackOverflow, написал пример реализации на gpwiki.org .

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

Answer 4

Для довольно общего решения и при условии ...

1. полигоны не пересекаются в момент времени = 0
2. хотя бы один многоугольник пересекает другой многоугольник в момент времени = t
3. и вы счастливы использовать библиотеку отсечения C # (например, Clipper )

затем используйте бинарный подход для получения времени пересечения по ...

double tInterval = t;
double tCurrent = 0;
int direction = +1;
while (tInterval > MinInterval)
{
  tInterval = tInterval/2;
  tCurrent += (tInterval * direction);
  MovePolygons(tCurrent);
  if (PolygonsIntersect) 
    direction = +1;
  else 
    direction = -1;         
}

Answer 5

Хорошо - вы можете видеть, что это всегда точка одного из многоугольников, которая сначала попадает в сторону другой (или другой точки - но в конце концов это почти одно и то же) - возможным решением будет вычисление расстояния точки от других линий в направлении движения. Но я думаю, что это закончится довольно медленно.

Полагаю, что в норме расстояния между кадрами настолько малы, что не важно знать, где именно они попали первыми - некоторые небольшие пересечения не будут видны, и, в конце концов, все равно отскочит или взорвется - не так ли? :)