Wanted: Source for Vatti (or other) polygon clipper

Wanted: Source for Vatti (or other) polygon clipper

Post by Jens Alfk » Sat, 04 Dec 1993 05:47:24

I've recently discovered Bala R. Vatti's article "A Generic Solution To
Polygon Clipping" (CACM, July '92) which describes an algorithm for
intersecting (or unioning or differencing) any two arbitrary polygons, which
may self-intersect or have multiple contours. Cool stuff, and something I
really need for my current project.
  The article has a good description of the algorithm, but it's a pretty
complex beast and I'd much rather find some existing source code (C
preferable but I'll take anything) that I can use or at least consult for
  Does anyone have such code or know where I can find it?
  I'd also be interested in source code for other generic polygon clippers. I
do need to handle pairs of arbitrary polygons with multiple contours. If the
algorithm is good enough I'm willing to live without self-intersection...

Please reply by e-mail. If I get any good responses I'll summarize them here.

                                    This sound has no waves
--Jens Alfke                        This sound has no waves

            .apple.com              Through fog and other grey things
                                                  --Dog Faced Hermans


1. Implementation of general polygon clipper (Bala R. Vatti).


The past few months there has been a lot of questions on polygon clipping.
So you might find this interesting.

I have implemented the algorithm for general polygon clipping described
by Bala R. Vatti in Communications of the ACM July 1992 Vol. 35 No 7
pp 57-63. (I read a few weeks back of someone asking if anyone had
implemented "that bitching algorithm" :-)

The algorithm is based on a scanline technique and it handles all sorts
of polygons. They can be self-intersecting and contain holes, you can
define as many clip and subject polygons as you wish.

The output can be polygons or trapezoids (trapezoids are not implemented).

You can not only do clipping but union and difference (that's why I
did this).

It's FAST!

The problem is that the code was written in a hurry (less than a week).
Another thing is that the paper wasn't totally good, (lot's of errors
and left out parts), the pseudo-code wasn't the best either so...
Don't get me wrong the algorithm is great, it's quite simple and very
flexible (and fast).

The code isn't very good at the moment, it's good enough to be used in
my application but not good enough to be spread on the net.

BUT if there is enough interest I can make an effort of rewriting and
fixing and commenting the code so you can enjoy it.

Are you interested? Email me and we'll see.

Patrik Svensson

2. HP Deskjet 870CD vs EpsonCol Stylus 600 Vs AppleColorStylewriter6500?

3. Two pass polygon clipper source for download.

4. Show what key pressed on TForm

5. 2d polygon clipper -- source?

6. Animator

7. Best source of Weiler(80) polygon clipper?

8. Vatti algorithm - Polygon Clipping

9. Vatti polygon clipping algorithm

10. ANNOUNCE: General Polygon Clipper Library

11. ANNOUNCE: General Polygon Clipper library

12. looking for polygon clipper