Алгоритм AABB для контура точек пересечения AABB?
Я огляделся вокруг, но точно не нашел то, что искал. Сначала я думал, что это будет простая проблема. До тех пор, пока я не попытался реализовать ее и не понял, что было много случаев, и я не мог найти общее решение.
Скажем, у меня есть две AABB. Если их контуры пересекаются, я хочу получить все их точки пересечения. Максимальное количество баллов - 4, минимальное ненулевое количество баллов - 1.
Мои AABB состоят из min а также max точка, которая всегда автоматически сортируется так, чтобы min всегда имеет самые низкие значения ху и max всегда имеет самые высокие значения ху.
Изображение ниже показывает несколько AABB. Синие линии указывают их точки пересечения. Обратите внимание, что если сторона AABB перекрывает другую сторону, это похоже на бесконечное количество точек пересечения вдоль отрезков, которые перекрываются; в этих случаях я хочу игнорировать их и сказать: "Там нет точек пересечения".
Кто-нибудь получил идею для алгоритма? Я понимаю, что не разместил никакого кода, и я почти уверен, что он не одобрен, но я немного подумал об этой проблеме. Что касается того, почему я хочу сделать это... Я не знаю, мне просто интересно, возможно ли это сделать чисто.
О, да, у моих AABB есть такие методы, которые должны быть полезны:
Vector<2> getSize () const;
Point<2> getCenter () const;
//0=Quadrant-1, 1=Quadrant-2, 2=Quadrant-3, 3=Quadrant-4, else, error
Point<2> getCorner (int index) const;
//0=right, 1=up, 2=left, 3=down, else, error
LineSegment2D getSide (int index) const;
Я мог бы сделать некрасивый хак и просто сделать проверку линейного сегмента <-> линейного сегмента, но, я не знаю '.. Это вроде как', ну, некрасиво и не элегантно. Я почти уверен, что должна быть какая-то хитрость, которую я мог бы сделать с min а также max указывает сделать это быстро.
