Кажется, вы ищете решение для линейной системы сравнений. Китайская теорема об остатках должна быть применима.Он не будет применять проверку ваших границ, но если он найдет решение, вы можете проверить границы самостоятельно.
РЕДАКТИРОВАТЬ: Забудьте CRT.
Предполагая size <= m1 и size <= m2,смоделируйте нижние (включительно) и высокие (исключительные) края областей памяти как линейные отношения:
addr1low = l1 + k1*m1
addr1high = addr1low + size = l1 + k1*m1 + size
addr2low = l2 + k2*m2
addr2high = addr2low + size = l2 + k2*m2 + size
Вы хотите знать, существует ли диапазон k1, k2 такой, что addr1low < addr2low < addr1high или addr1low < addr2high < addr1high,Обратите внимание на исключительные неравенства;таким образом мы избегаем точно перекрывающихся диапазонов.
Предположим, m1 = m2 = m.Обратите внимание:
addr1low < addr2low
l1 + k1*m < l2 + k2*m
(k1 - k2) * m < l2 - l1
k1 - k2 < (l2 - l1) / m
addr2low < addr1high
l2 + k2*m < l1 + k1*m + size
l2 - l1 < (k1 - k2) * m + size
(l2 - l1 - size) < (k1 - k2) * m
(l2 - l1 - size) / m < k1 - k2
Вышеуказанная прогрессия обратима.Предполагая, что k1, k2 может быть 0, -n2 <= k1 - k2 <= n1.Если в диапазоне от (l2 - l1 - size) / m до (l2 - l1) / m есть целое число, то система удерживается и происходит наложение.Это если ceil(max((l2 - l1 - size) / m, -n2)) <= floor(min((l2 - l1) / m, n1)).Другой случай (addr1low < addr2high < addr1high) происходит аналогично:
addr1low < addr2high
l1 + k1*m < l2 + k2*m + size
// ..
(l1 - l2 - size) / m < k2 - k1
addr2high < addr1high
addr2low + size < addr1low + size
addr2low < addr1low
// ..
k2 - k1 < (l1 - l2) / m
Теперь тест становится ceil(max((l1 - l2 - size) / m, -n1)) <= floor(min((l1 - l2) / m, n2)).
Теперь рассмотрим m1 <> m1, а без потери общности возьмем m1 < m2.
Обрабатывая переменные как непрерывные, решите пересечения:
addr1low < addr2low
l1 + k*m1 < l2 + k*m2
(l1 - l2) < k * (m2 - m1)
(l1 - l2) / (m2 - m1) < k
addr2low < addr1high
l2 + k*m2 < l1 + k*m1 + size
l2 - l1 - size < k * (m1 - m2)
(l2 - l1 - size) / (m1 - m2) > k // m1 - m2 < 0
Опять же, шаги обратимы, поэтому любое целое число k < min(n1, n2), удовлетворяющее границам, заставит систему удержаться.То есть, если ceil(max((l1 - l2) / (m2 - m1), 0)) <= floor(min((l2 - l1 - size) / (m1 - m2), n1, n2)).Другой случай:
addr1low < addr2high
l1 + k*m1 < l2 + k*m2 + size
l1 - l2 - size < k * (m2 - m1)
(l1 - l2 - size) / (m2 - m1) < k
addr2high < addr1high
addr2low + size < addr1low + size
addr2low < addr1low
l2 + k*m2 < l1 + k*m1
l2 - l1 < k * (m1 - m2)
(l2 - l1) / (m1 - m2) > k // m1 - m2 < 0
Здесь тест становится ceil(max((l1 - l2 - size) / (m2 - m1), 0)) <= floor(min((l2 - l1) / (m1 - m2), n1, n2)).
Окончательный псевдокод может выглядеть примерно так:
intersectos?(l1, n1, m1, l2, n2, m2, size) {
if (m1 == m2) {
return ceil(max((l2 - l1 - size) / m, -n2)) <= floor(min((l2 - l1) / m, n1)) ||
ceil(max((l1 - l2 - size) / m, -n1)) <= floor(min((l1 - l2) / m, n2));
}
if (m1 > m2) {
swap the arguments
}
return ceil(max((l1 - l2) / (m2 - m1), 0)) <= floor(min((l2 - l1 - size) / (m1 - m2), n1, n2)) ||
ceil(max((l1 - l2 - size) / (m2 - m1), 0)) <= floor(min((l2 - l1) / (m1 - m2), n1, n2));
}