[Feature Request] Optimize MinkowskiSum for Convex Polygons with $O(N+M)$ Linear Algorithm

[FishOrBear]

Type of Request

• Performance Optimization
• Bug Fix
• New Feature

Description

Hi Angus,

First of all, thank you for the incredible work on Clipper2! It has been an amazing tool for geometric computing.

While reviewing the implementation of MinkowskiSum in clipper.minkowski.cpp, I noticed that the current implementation detail::Minkowski uses a generalized approach: it generates $O(N \times M)$ quadrilaterals by shifting paths and then resolves them using detail::Union.

While this generalized approach is extremely robust and handles concave/open paths beautifully, it introduces unnecessary overhead when both input paths are strictly convex polygons.

For two convex polygons with $N$ and $M$ vertices, their Minkowski Sum is also a convex polygon with at most $N+M$ vertices, which can be computed in $O(N+M)$ linear time using a standard two-pointer edge-advance algorithm (ordered by edge angles/cross products), without generating intermediate quads or executing the heavy Clipper64::Execute(ClipType::Union) scanline logic.

Proposed Optimization

We can add a fast-path detection at the entry of MinkowskiSum. If both polygons are verified to be convex (which can be checked in $O(N)$ or assumed via user documentation/flags), we can bypass the quad-generation and Union steps entirely, routing the execution to a linear-time merger.

Something similar to the classic approach:

1. Find the bottom-left vertex for both polygons as the starting point.
2. Use a two-pointer loop to compare the cross product of the next edges of both polygons.
3. Advance the pointer with the smaller angle and push the combined vertices into the result path.

Expected Benefits

• Time Complexity: Dropping from $O(N \times M) + \text{Union Cost}$ down to a pure $O(N + M)$ line loop.
• Memory Footprint: Eliminates the allocation of $N \times M$ quad paths in memory.