CODEWITHSUNDEEP
mathpolygonsubtraction
George
George

Reputation: 31

how to subtract circle from an arbitrary polygon

Given an arbitary polygon with vertices stored in either clockwise/counterclockwise fashion (depicted as a black rectangle in the diagram), I need to be able to subtract an arbitrary number of circles (in red on the diagram) from that polygon. Removing a circle could possibly split the polygon into two seperate polygons (as depicted by the second line in the diagram).

I'm not sure where to start.

Example http://www.freeimagehosting.net/uploads/89a0276d9d.jpg

Upvotes: 3

Views: 884

Answers (2)

Angus Johnson
Angus Johnson

Reputation: 4643

Here's a freeware polygon clipping library (written in Delphi and C++) that does what you're asking: http://sourceforge.net/projects/polyclipping/

Upvotes: 0

Dan Piponi
Dan Piponi

Reputation: 8116

Warning: getting code to do this absolutely right is tricky. (Conceptually it's fine, but you can quickly get bogged down in numerical errors and edge cases.) You're basically asking for a 2D version of Constructive Solid Geometry. You might want to see if you can use an existing library written by an expert in computational geometry. There are some libraries here that will probably do what you want, but you'll have to choose a representation that suits you best and convert what you have into that representation.

Upvotes: 2

Related Questions