Мне нужно оценить коэффициент перекрытия двух прямоугольников произвольного размера и ориентации.Приблизительная площадь перекрытия вращающихся прямоугольников
Я знаю, как выполнить точные вычисления, используя алгоритм Сазерленда-Ходжмана, который можно оптимизировать для этого случая.
В любом случае, поскольку мне нужно использовать эту функцию, интенсивная и совершенная точность не требуется (скажем, 10% -ная ошибка может быть допущена), мне было интересно, не может ли она быть оценена быстрее, желательно без разветвления.
Если это помогает, можно предположить, такое же соотношение сторон для обоих прямоугольников, а отношение площадей не превышает 4.
Update:
Для прямоугольников поворотов,, формула
(мин (W0, W1 + DX) - макс (-w0, DX-W1)) (мин (Н0, DY + H1) - макс (Н0, DY-H1)).
или ноль, если какой-либо из двух факторов отрицательный, где
DX,DY- разница между центральными координатами,WиHобозначают соответствующие половинные размеры.Возможно, стоит посмотреть на кривую общей площади для заданного размещения центров и заданных размеров, когда вы меняете относительный угол поворота.
Просто спекуляция, как насчет выборки? То есть, если преобразование A отображает выровненную ось, 0 центрированный прямоугольник на один из ваших прямоугольников, а B сопоставляется с другим, а затем для коллекции выборочных точек p из выровненной второй оси прямоугольника вы подсчитываете количество раз inv (A) (B (p)) находится в первом выровненном по оси прямоугольнике; отношение количества обращений к числу выборок было бы приближением к отношению площади пересечения к площади второго прямоугольника, выровненного по оси. – dmuir
@ dmuir: это совершенно верно. Теперь цель состоит в том, чтобы уменьшить вычислительную стоимость, так что количество разрешенных выборок будет очень ограниченным (например, менее десяти я думаю). –
, если ваш язык позволяет это сделать, вы можете делать много вычислений выборки параллельно. – dmuir