CODEWITHSUNDEEP
geometrycomputational-geometry
Josh C.
Josh C.

Reputation: 4363

Subtract Rectangle from Polygon

I'm looking for an algorithm that will subtract a rectangle from a simple, concave polygon and return a remainder of polygons. If the rectangle encloses the polygon, the remainder is null. In most cases, it looks like at least one edge will be shared between the rectangle and the polygon.

I've been digging around the internet, but I've not found a good lead.

Can someone point me in the right direction?

Upvotes: 3

Views: 1645

Answers (1)

leftangle
leftangle

Reputation: 128

That's easy: Find the intersections between the rectangle and the edges of the simple polygon and cut the segments there. This does not require a spatial search structure as the 4 edges of the polygon are a constant factor, so that runs in linear time.

Then compute a constrained Delaunay triangulation of all segments and use seed points to grow the regions. Combine the regions appropriately (the triangles inside the simple polygon minus the ones inside the rectangle minus triangles outside. The triangles that remain are your result and the border edges are the edges of the resulting polygon.

Edit: I'm sorry if the answer was too short. The figure below shows the idea.
a) The two input polygons
b) The CDT after insertion of the (cutted) segments
c) The grown regions
d) The green region minus the red region
e) The border edges of the region of d.

enter image description here

Upvotes: 6

Related Questions