Linear Sweep of a 2D Polygon

Question

Suppose we have a 2D simple polygon (no self-intersection) on the $XY$ plane defined by $n$ vertices and a 2D vector $V=(A,B)$. Is there an algorithm to detect if a generic point $P=(x,y)$ on the plane belongs to the area that is covered by the polygon when it "slides" along the line segment from $A$ to $B$?

Answer 1

The generated region is the so-called "Minkovski sum" $P'= P \oplus V$ of the polygon and the vector (that can be considered as a degenerated polygon). $P'$ is known to be still a (convex) polygon.

Therefore, the algorithm you are looking for amounts to combine 2 classical algorithms :

• The algorithm giving the vertices of this Minkowski sum $P'$.

• The algorithm testing whether a point is inside or outside a convex polygon .

Answer 2

Edit: This answers a different question, for when the sliding vector is "infinitely large".

The area covered by the sliding polygon is an infinite strip which has two bounding lines. To find out which two vertices $(x_i,y_i)$ of the polygon are the ones sliding along the boundary, you can maximize/minimize the following function: $$ \alpha(x_i,y_i) := -B x_i + A y_i $$ where $(A,B)$ is the direction of the sliding. Geometrically, this formula comes from taking the scalar product of $(x_i,y_i)$ with the vector $(-B,A)$ perpendicular to $(A,B)$. Once you have the maximum index $i_{max}$ and minimum index $i_{min}$, a point $(x,y)$ lies in the region if and only if $$ \alpha(x_{i_{min}},y_{i_{min}}) \leq \alpha(x,y) \leq \alpha(x_{i_{max}},y_{i_{max}}). $$