Алгоритм для обнаружения пересечения двух прямоугольников?
NullPointerException s - исключения, возникающие при попытке использовать ссылку, которая указывает на отсутствие местоположения в памяти (null), как если бы она ссылалась на объект. Вызов метода по нулевой ссылке или попытка получить доступ к полю нулевой ссылки вызовет функцию NullPointerException. Они наиболее распространены, но другие способы перечислены на странице NullPointerException javadoc.
Вероятно, самый быстрый пример кода, который я мог бы придумать для иллюстрации NullPointerException, be:
public class Example {
public static void main(String[] args) {
Object obj = null;
obj.hashCode();
}
}
В первой строке внутри main я явно устанавливаю ссылку Object obj равной null. Это означает, что у меня есть ссылка, но она не указывает на какой-либо объект. После этого я пытаюсь обработать ссылку так, как если бы она указывала на объект, вызывая метод на нем. Это приводит к NullPointerException, потому что нет кода для выполнения в местоположении, на которое указывает ссылка.
(Это техничность, но я думаю, что она упоминает: ссылка, которая указывает на null, равна 't то же, что и указатель C, указывающий на недопустимую ячейку памяти. Нулевой указатель буквально не указывает на в любом месте , который отличается от указаний на местоположение, которое оказывается недопустимым.)
8 ответов
Стандартный метод состоял бы в том, чтобы сделать отделяющийся тест оси (сделайте поиск Google на этом).
Короче говоря:
- Два объекта не пересекаются, если можно найти строку, которая разделяет два объекта. например, объекты / все точки объекта находятся на различных сторонах строки.
забавная вещь, что достаточно просто проверить все края этих двух прямоугольников. Если прямоугольники не наложатся, то один из краев будет отделяющейся осью.
В 2D можно сделать это, не используя наклоны. Край просто определяется как различие между двумя вершинами, например,
edge = v(n) - v(n-1)
можно получить перпендикуляр к этому путем вращения его на 90В °. В 2D это легко как:
rotated.x = -unrotated.y
rotated.y = unrotated.x
, Таким образом, никакая тригонометрия или наклоны не включены. Нормализация вектора к единичной длине не требуется также.
, Если Вы хотите протестировать, если точка находится на одной или другой стороне строки, можно просто использовать скалярное произведение. знак скажет Вам, какая сторона Вы идете:
// rotated: your rotated edge
// v(n-1) any point from the edge.
// testpoint: the point you want to find out which side it's on.
side = sign (rotated.x * (testpoint.x - v(n-1).x) +
rotated.y * (testpoint.y - v(n-1).y);
Теперь тест все точки прямоугольника против краев прямоугольника B и наоборот. При нахождении отделяющегося края, объекты не пересекаются (обеспечение всех других точек в B имеют с другой стороны край, протестированный на - см. рисунок ниже). Если Вы не находите края разделения или прямоугольники пересекаются или один прямоугольник, содержится в другом.
тест работает с любыми выпуклыми полигонами btw..
Поправка: Для идентификации отделяющегося края недостаточно протестировать все точки одного прямоугольника против каждого края другого. Край кандидата E (ниже) был бы как таковой быть идентифицированным как отделяющийся край, как все точки в A находятся в той же полуплоскости E. Однако это не отделяющийся край, потому что вершины Vb1 и Vb2 B находятся также в той полуплоскости. Это только был бы отделяющийся край, если бы это не имело место http://www.iassess.com/collision.png
При использовании Java все реализации интерфейса Shape имеют , пересекается метод, которые берут прямоугольник.
Одно решение состоит в том, чтобы использовать что-то позвонившее Никакой Пригодный Полигон. Этот полигон вычисляется от этих двух полигонов (концептуально путем скольжения один вокруг другого), и он определяет область, для которой полигоны накладываются, учитывая их относительное смещение. После того как у Вас есть этот NFP затем, просто необходимо сделать тест включения с точкой, данной относительным смещением этих двух полигонов. Этот тест включения быстр и легок, но действительно необходимо создать NFP сначала.
Имеют поиск Никакого Пригодного Полигона в сети и видят, можно ли найти алгоритм для выпуклых полигонов (это становится НАМНОГО более сложным, если у Вас есть вогнутые полигоны). Если Вы не можете найти, что что-либо затем посылает мне по электронной почте в howard точке точки J, может com
точки GmailВ основном посмотрите на следующее изображение:
, Если эти два поля сталкиваются, строки A и B наложатся.
Примечание, которое это должно будет быть сделано и на X и на оси Y и обеих потребностях перекрыть, чтобы прямоугольники столкнулись.
существует хорошая статья в gamasutra.com , который отвечает на вопрос (изображение от статьи). Я сделал подобный алгоритм 5 лет назад, и я должен найти, что мой фрагмент кода отправляет его здесь позже
Поправка : Разделение Теоремы Оси указывает, что две выпуклых формы не делают перекрытие, если отделяющаяся ось существует (т.е. тот, где проекции как показано не делают перекрытие). Так "Отделяющаяся ось существует" => "Никакое перекрытие". Это не bi-импликация, таким образом, Вы не можете завершить обратное.
Проверьте, чтобы видеть, пересекает ли какая-либо из строк от одного прямоугольника какую-либо из строк от другого. Наивное пересечение линейного сегмента легко кодировать.
при необходимости в большей скорости существуют усовершенствованные алгоритмы для пересечения линейного сегмента (строка развертки). См. http://en.wikipedia.org/wiki/Line_segment_intersection
Вы могли найти пересечение каждой стороны углового прямоугольника с каждой стороной выровненной осью. Сделайте это путем нахождения уравнения бесконечной строки, на которой каждая сторона находится (т.е. v1 + t (v2-v1) и v '1 + t' (v '2-v '1) в основном), находя точку, в которой строки встречаются путем решения для t, когда те два уравнения равны (если они параллельны, можно протестировать на тот), и затем тестирование, находится ли та точка на линейном сегменте между этими двумя вершинами, т.е. является им верный те 0 < = t < = 1 и 0 < = t' < = 1.
Однако это не покрывает случай, когда один прямоугольник полностью покрывает другой. То, что можно покрыть путем тестирования, лежат ли все четыре точки любого прямоугольника в другом прямоугольнике.
Это - то, что я сделал бы, для 3D версия этой проблемы:
Моделируют эти 2 прямоугольника как плоскости, описанные уравнением P1 и P2, затем пишут P1=P2 и получают из этого строку перекрестного уравнения, которое не будет существовать, если плоскости будут параллельны (никакое пересечение) или будут в той же плоскости, в этом случае Вы получаете 0=0. В этом случае необходимо будет использовать 2D прямоугольный перекрестный алгоритм.
Затем я видел бы, проходит ли та строка, которая находится в плоскости обоих прямоугольников, через оба прямоугольника. Если это делает, то у Вас есть пересечение 2 прямоугольников, иначе Вы не делаете (или не были должны, я, возможно, пропустил угловой случай в голове).
, Чтобы найти, проходит ли строка через прямоугольник в той же плоскости, я нашел бы 2 точки пересечения строки и стороны прямоугольника (моделирующий их уравнения строки использования), и затем удостоверился бы, что точки пересечений с в диапазоне.
, Который является математическими описаниями, к сожалению, у меня нет кода, чтобы сделать вышеупомянутое.
Ну, метод грубой силы должен обойти края горизонтального прямоугольника и проверить каждую точку вдоль края, чтобы видеть, падает ли это на или в другом прямоугольнике.
математический ответ должен сформировать уравнения, описывающие каждый край обоих прямоугольников. Теперь можно просто найти, пересекает ли какая-либо из этих четырех строк от прямоугольника A какую-либо из строк прямоугольника B, который должен быть простым (быстрым) решателем линейного уравнения.
-Adam