1

Topic: Algorithm of cutting off of a polygon a rectangle

Good afternoon the algorithm of cutting off of the arbitrary polygon, a rectangle Interests, I used Sutherland's algorithm - Hodgmana, but the given algorithm has a lack of that that cannot break a polygon on some, and adds superfluous edges. Looking on the Internet, found family of algorithms which essence approximately in the following: Sequentially edges are processed and there are crosspoints with rectangle Pin - "an input" point in a rectangle, Pout - exit point and internal points, after handling of all points, there is handling Pin/Pout, begin with Pin we go on internal points to Pout all it we add in an output circuit, further from Pout goes according to a polygon direction (on hour/or against an arrow) on a cutting rectangle if we come in Pin from which came to Pout we short a circuit, then we pass to the following point Pin. And a principle algorithm not difficult and beautiful, but problems appeared on polygons with self-intersection as there is no the unambiguous direction of bypass.

2

Re: Algorithm of cutting off of a polygon a rectangle

Hello, SL, you wrote: SL> Good afternoon SL> the algorithm of cutting off of the arbitrary polygon, a rectangle Interests, I used Sutherland's algorithm - Hodgmana, but the given algorithm has a lack of that that cannot break a polygon on some, and adds superfluous edges. There is general-purpose enough (Even complex (self-intersecting) polygons, and polygons with holes can be processed) algorithm Vatti the link In particular, it is used in library Clipper the link