Mincowski Sum of Convex Polygons

Code

/// Returns the Minkowski sum of two convex polygons `p` and `q`.
/// Both `p` and `q` must be oriented in CCW and should not contain two equal points.
/// The returned polygon is also oriented in CCW.
fn minkowski_convex(p: &[P], q: &[P]) -> Vec<P> {
	fn line_iterator(poly: &[P]) -> impl Iterator<Item = [P; 2]> + '_ {
		let mut it = poly.iter().copied().cycle().peekable();
		iter::from_fn(move || {
			let u = it.next().unwrap();
			let v = *it.peek().unwrap();
			Some([u, v])
		})
	}

	let pi = (0..p.len()).min_by_key(|&i| p[i]).unwrap();
	let qi = (0..q.len()).min_by_key(|&i| q[i]).unwrap();
	let mut pl = line_iterator(p).skip(pi).enumerate().peekable();
	let mut ql = line_iterator(q).skip(qi).enumerate().peekable();

	let mut ret = vec![];
	while let (Some(&(pc, pp)), Some(&(qc, qq))) = (pl.peek(), ql.peek()) {
		if pc >= p.len() && qc >= q.len() {
			break;
		}
		ret.push(add(pp[0], qq[0]));
		let pcq = cross(sub(pp[1], pp[0]), sub(qq[1], qq[0]));
		if pcq >= 0 {
			pl.next();
		}
		if pcq <= 0 {
			ql.next();
		}
	}
	ret
}

Last modified on 231225.