Рассчитать перекрытие между двумя прямоугольниками на сетке x/y?

Мне нужно вычислить перекрытие (количество или да/нет), которое создают два прямоугольника на специальной сетке x/y. Сетка 500x500, но стороны и углы соединяются (непрерывны). Таким образом, следующая точка после 499 снова становится 0.

В предыдущем вопросе я спросил, как рассчитать расстояние между двумя точками в этой сетке. Это оказалось евклидовым расстоянием:

sqrt(min(|x1 - x2|, gridwidth - |x1 - x2|)^2 + min(|y1 - y2|, gridheight - |y1-y2|)^2)

Каков математический способ расчета, если два прямоугольника (определяемые точкой (x, y), шириной и высотой) пересекаются в этой сетке?

Прямоугольник-1 ([x=0,y=0], w=20, h=20) и прямоугольник-2 ([x=495,y=0], w=10, h=10) должны перекрываться. Перекрывающийся прямоугольник (не обязательно, но) должен быть ([x=0,y=0], w=5, h=10)


coordinates grid overlap math euclidean-distance
person Ropstah    schedule 24.01.2010    source источник
comment
Я могу сказать вам, как это сделать в 3D-пространстве... это будет работать и в 2D, но я не знаю, приемлемо ли это для вас. В основном идея состоит в том, чтобы посмотреть на 2 плоскости, на которых находятся прямоугольники. Найдите пересечение этих плоскостей и посмотрите, пересекается ли линия, которая пересекает эти плоскости, с обоими прямоугольниками... Хотите услышать математику?   -  person Cipi    schedule 24.01.2010
comment
Меня очень интересует математика. Я понимаю, о чем вы говорите, и я могу вычесть математику, но я не могу ее произвести... Будет ли 2D-подход менее требовательным к мощности процессора?   -  person Ropstah    schedule 24.01.2010
comment
Мощность процессора?! Вы можете рассчитать это на процессоре Casio Watch. xD Это действительно простая математика... Позвольте мне проверить то, что я имею в виду. Вы создаете его на C-подобном объектно-ориентированном языке?   -  person Cipi    schedule 24.01.2010
comment
Меня немного смущает, когда вы говорите «Прямоугольник-1» ([x=0,y=0], w=20, h=20) и «Прямоугольник-2» ([x=495,y=0], w=10, h=10) должны иметь перекрытие. Если один находится в начале координат, а другой — далеко на 495° по оси x, они не будут перекрываться.   -  person Chris Upchurch    schedule 24.01.2010
comment
На самом деле на все это есть ответ здесь: stackoverflow.com/questions/115426/   -  person Cipi    schedule 24.01.2010
comment
@Chris: пожалуйста, прочитайте первые 3 строки моего вопроса.   -  person Ropstah    schedule 24.01.2010
comment
@Cipi: я ищу очень эффективную функцию, которая выполняет этот расчет почти непрерывно. Разве это не другой способ ответа на широкий вопрос (вращение и т. Д.). И учитываются ли мои требования, где сетка должна быть непрерывной?   -  person Ropstah    schedule 24.01.2010

Ответы (1)


arrow_upward
3
arrow_downward

Сначала вычислите диапазон x и y для каждого прямоугольника (поскольку у вас есть геометрия тора, сделайте это по модулю сетки).

Итак, учитывая ваш Rectangle-1, вычислите:

x1 = x = 0, x2 = x + w = 20
y1 = y = 0, y2 = y + h = 20

То же самое для прямоугольника-2:

x3 = 495, x4 = 505 mod 500 = 5
y3 = 0,   y4 = 10

Создайте области x и y для каждого прямоугольника:

Reactangle-1: x-regions: (0, 20)
              y-regions: (0, 20)

Rectangle-2:  x-regions: (495, 500), (0, 5)
              y-regions: (0, 10)

Если какие-либо (обе) области x и y между двумя прямоугольниками имеют ненулевое пересечение, то ваши прямоугольники перекрываются. Здесь (0, 20) x-область прямоугольника-1 и (0, 5) x-область прямоугольника-2 имеют ненулевое пересечение, как и (0, 20) и (0, 10) y -регионы.

person 3lectrologos    schedule 24.01.2010