Математическая техника для проверки пересечения
Представьте, что есть очень очень большая комната в форме полого куба. В неподвижных отдельных точках комнаты висят волшебные шары. Ни у одного магического шара нет другого точно над ним. Если мы возьмем воображаемую горизонтальную плоскость бесконечной области и пройдем через куб, как мы можем быть уверены, что плоскость не прорезает ни один из магических шаров?
Высота магического шара определяется как функция его положения (x и y). Распределение происходит таким образом, что некоторые шары находятся на одной высоте, а другие - на разной высоте. Пусть функция будет z = axy + bx + cy
где a, b, c - положительные целочисленные константы. Позиции (значения оси x и оси y), а также высота (z) являются дискретными значениями (для простоты мы можем считать их положительными целыми числами).
Если бы функция распределения шаров была z=10xy+8x+4y, то невозможно иметь значение a z 15 или 21. Таким образом, плоскость при z=15 или z=21 не будет разрезать ни один из шариков! Фактически, в этом случае любая плоскость с высотой (z = любое нечетное число) не будет прорезать шары. Заметно, что есть несколько плоскостей с высотой в виде четных чисел, которые не прорезают шары.
Мы не хотим находить высоты всех магических шаров и сравнивать их с высотой горизонтальной плоскости, поскольку это было бы подобно пробованию всех возможных комбинаций и заняло бы очень много времени даже на компьютере.
Наша цель - найти быстрый метод, с помощью которого мы можем определить, может ли данное значение z (высота) быть получено любой парой (x,y) (позиций). Если заданный z не может быть получен, то плоскость на этой высоте не прорезает шары! Вопрос также похож на нахождение того, присутствует ли данное число в последовательности, произведенной функцией двух переменных.
Было бы очень полезно, если бы U мог дать мне какие-либо предложения по решению этой проблемы. Благодарю вас. (Я уже пробовал эволюционные вычисления, такие как GA,PSO,DE,SA и т. Д. Метод должен быть детерминированным).
1 ответ
Похоже, у вас в комнате много шаров. Высота помещения от z=A до z=B. Что вас интересует, так это то, находятся ли они на высоте z. Чтобы сделать это без необходимости итерации по всем шарам, вам нужно начать с предположения, что диапазон от A до B пуст, и итерировать по шарам, отмечая части этого диапазона как полные до тех пор, пока он не заполнится полностью или не будет шаров., В первом случае ни один самолет не удовлетворит, но вы не прошли через все шары, чтобы узнать это. В последнем случае у вас есть диапазоны z, в которых нет шариков, и вы можете использовать их, чтобы легко проверить более одной плоскости, однако с начальной стоимостью итерации по всем шарикам.