CODEWITHSUNDEEP
algorithmlanguage-agnosticgeometrypolygoncomputational-geometry
Gokhan Kurt
Gokhan Kurt

Reputation: 8277

Get the polygon created by moving a polygon

I don't know if the process has a specific name. I want to get the polygon which is created by translating a polygon. Is there an algorithm for this. For example: Example.

Convex hull works for convex polygons but I want a general solution. Also I would be happy to hear if there is a way to get the polygon created by rotating.

Upvotes: 2

Views: 139

Answers (2)

weasel - Peter Palfrader
weasel - Peter Palfrader

Reputation: 221

It appears you are looking for the Minkowski sum of your polygon and the line segment describing your movement.

The CGAL library package 2D Minkowski Sums can compute them for instance.

Upvotes: 4

Gene
Gene

Reputation: 46990

Given the explanation you gave in comments, the straightforward approach is this:

Let v be a vector describing the linear movement
For each edge (p,q) in the polygon 
  construct quadrilateral (p, q, q+v, p+v)
Compute the union of all the quadrilaterals plus the original polygon

Computing polygon unions is a well-studied problem with efficient algorithms.

Upvotes: 2

Related Questions