Journal of Mathematical Imaging and Vision Computer Vision and Pattern Recognition
The Maximum Cover with Rotating Field of View
Abstract
Abstract In this paper, we address the maximum cover problem of a rotating field of view (FOV) with a convex polygon $$\mathcal {P}$$ P with n vertices. The problem is defined as determining the optimal rotation angle $$\theta $$ θ of the FOV, characterised by a fixed centre and inner angle $$\phi $$ ϕ , such that the intersection between the FOV and $$\mathcal {P}$$ P has the maximum possible area. This problem is relevant for applications in visibility optimisation and uncertainty reduction in localisation tasks. We present a theoretical framework and a corresponding algorithm to approximate the value of the maximum, ensuring that the solution is close to the optimal within the specified precision. The intersection between the rotating FOV and $$\mathcal {P}$$ P forms a convex polygon whose number of vertices varies with the rotation angle $$\theta $$ θ . We analytically derive the area of the intersection when it takes its simplest form, a quadrilateral, as a two-variable function $$A(\theta ,\phi )$$ A ( θ , ϕ ) . The function $$A(\theta ,\phi )$$ A ( θ , ϕ ) , with the angle of rotation $$\theta $$ θ and the fixed inner angle $$\phi $$ ϕ , denoted as $$A_{\phi }(\theta )$$ A ϕ ( θ ) , is non-monotonic and has multiple local extreme points inside of a given domain which poses a challenge in identifying them and approximating the global maximum. We found an alternative way to express it by various compositions of a function $$A_{\theta }(\phi )$$ A θ ( ϕ ) (with a restricted inner angle $$\phi $$ ϕ and a fixed direction $$\theta $$ θ ). We show that $$A_{\theta }(\phi )$$ A θ ( ϕ ) has an analytical solution in the special case of a two-sector intersection and later provides a constrictive solution for the original problem. We develop an algorithm that approximates the direction of the field of view, with precision $$\varepsilon >1$$ ε > 1 , and complexity $$\mathcal {O}(n(\log {n}+(\log {\varepsilon })/\phi ))$$ O ( n ( log n + ( log ε ) / ϕ ) ) .