Polygon

 

Polygon logo|View all articles regarding Polygon|

Polygon is a Python package that handles polygonal shapes in 2D. It contains Python bindings for gpc, the excellent General Polygon Clipping Library by Alan Murta and some extensions written in C and pure Python. With Polygon you may handle complex polygonal shapes in Python in a very intuitive way. Polygons are simple Python objects, clipping operations are bound to standard operators like +, -, |, & and ^. TriStrips can be constructed from Polygons with a single statement. Functions to compute the area, center point, convex hull, point containment and much more are included.

Points can be organized in tuples or lists. NumPy arrays are also supported but Polygon can be compiled without support for it.

This package was already used to process shapes with more than one million points!

  • License: LGPL (not for gpc itself, see below!)
  • Status: Should be almost stable now, but there may be memory leaks. Malformed files and illegal contours may crash the library and your running Python interpreter! Use Polygon at your own risk or don’t use it at all!
  • gpc-Homepage: http://www.cs.man.ac.uk/~toby/alan/software/

gpc is included in Polygon, you don’t need to download it separately. I made two small changes to gpc:

  1. fixed warnings regarding a printf format string and
  2. made GPC_EPSILON adjustable, this may slow down the clipping a little bit.

The author of gpc (Alan Murta) is not responsible for this distribution! The wrapping and extension code is free software, but the core gpc library is free for non-commercial usage only. The author says:

GPC is free for non-commercial use only. We invite non-commercial users to make a voluntary donation towards the upkeep of GPC. If you wish to use GPC in support of a commercial product, you must obtain an official GPC Commercial Use Licence from The University of Manchester.

Please respect this statement and contact the author (see gpc homepage) if you wish to use this software in commercial projects!

Download, Documentation & Examples

Documentation and examples are included in the source distribution in the folder doc. The development of the packages is hosted at bitbucket.  There are two different projects, one for Python 2.x and one for Python 3.1 and newer.

I tried to keep both versions synchronized as long as possible. But now a lot of projects are moving to Python 3 and so will I. In the future Polygon2 will only receive bug fixes while new features are added to Polygon3.

Download Polygon2 for Python 2

Download Polygon3 for Python 3

Operations Example
Reduce Points Example
Tiling Example
Exploded Cookie
Star Cookie Example
Sierpinski Carpet Example (level 5)


46 thoughts on “Polygon

  1. Hi, I wanted to know how does the Polygon library finds the centroid of an irregular polygon, what algorithm is being used for this task?

    Thanks for your help.

  2. Hi Jörg,

    Could it be that when Polygon_addContour() is called in Polygon_init(), any errors raised in Polygon__addContour() don’t bubble up? I’m not very familiar with this Python/C interface, but shouldn’t Polygon_init() return -1 in case of an error? I could be wrong though…

    Kind regards,

    Diederik

  3. Hello Jörg, the Windows installer for Python 3.3 (Polygon3-3.0.6.win32-py3.3_withNumPy) seems to be broken: after clicking on Next when it reads “ready to install” the application crashes.

    Any thoughts on what could be going on?

    • Sorry, I can not reproduce the error. On my system the installation works as expected. Can you give more information (Windows System, Python version etc.)?

      Jörg

  4. Hi! I can’t seem to import the packages properly.
    The error message was:
    Tracback :
    File “”, lin 1, in
    File “C\Python27\lib\site-packages\Polygon\__init__.py”, line 8, in
    __version__ = version
    NameError: name ‘version’ is not defined

    Please send a reply, I’m going the library for a Machine Problem in school.

    • Hi Louie,
      please send a correct and complete error message! Which version of Polygon do you use? How did you install it? What code was used to trigger the error? Jörg

  5. Hi Jörg,

    Is there an easy way to delete a contour from a polygon, other than creating a new polygon and copying over all contours that are _not_ to be deleted?

    Thanks,

    Diederik

  6. Hi Jörg,

    I’m sorry but I don’t quite understand from the documentation how I should input the fill color for when I save a svg:

    For example if I want the width and height to be 1000 and the rgb to be 128,128,230 how do I do it ?

    Ex of what I’ve been trying:

    writeSVG(“my.svg”,polyCircle,1000,1000,(128,128,230);

    • writeSVG() expects a sequence (list, tuple, …) of polygons and sequences of the attributes, even if you have just one polygon object. A list with one element can be written [e]. A tuple with one element is written (e,). A working example would be:

      import Polygon, Polygon.Shapes, Polygon.IO
      p = Polygon.Shapes.Star()
      Polygon.IO.writeSVG('out.svg', (p,), fill_color=((0, 255, 0),))

      Jörg

  7. Hi Jörg,

    Is it possible to set the GPC_EPSILON without recompiling the GPC library? I’ve found out that I need a bigger value, but haven’t found a way to specify it directly in the Python code itself.

    Thanks,

    Diederik

  8. Hi Jörg,

    The library looks great very intuitive, If I may ask is there a method to export the shapes to some form of bitmap image format (for ex jpg) ?

    Or would I have to use another library after I generate the images with yours ?

  9. vishal@vishal-Reserved:~/acads/python/Polygon2-2.0.6$ sudo python setup.py install
    NumPy extension not found – disabling support for it!
    running install
    running build
    running build_py
    running build_ext
    running install_lib
    running install_egg_info
    Removing /usr/local/lib/python2.7/dist-packages/Polygon2-2.0.6.egg-info
    Writing /usr/local/lib/python2.7/dist-packages/Polygon2-2.0.6.egg-info
    vishal@vishal-Reserved:~/acads/python/Polygon2-2.0.6$ python
    Python 2.7.3 (default, Apr 10 2013, 06:20:15)
    [GCC 4.6.3] on linux2
    Type “help”, “copyright”, “credits” or “license” for more information.
    >>> import Polygon, Polygon.IO
    Traceback (most recent call last):
    File “”, line 1, in
    File “Polygon/__init__.py”, line 5, in
    from cPolygon import *
    ImportError: No module named cPolygon

    Please help me with this

  10. I am trying to install the package but I am not able to install it. I can understand the reason. This is what appears:

    C:\Program Files (x86)\python\Polygon3-3.0.6>python setup.py install
    NumPy extension not found – disabling support for it!
    running install
    running build
    running build_py
    running build_ext
    building ‘Polygon.cPolygon’ extension
    Traceback (most recent call last):
    File “setup.py”, line 100, in
    setup(**args)
    File “C:\Program Files (x86)\python\lib\distutils\core.py”, line 148, in setup

    dist.run_commands()

    Vishal

  11. Hi Jörg,

    Suppose I have a single solid polygon with multiple holes. Now when I do a boolean on it, I might end up with a single polygon consisting of multiple solids, with each solid having multiple holes. Is there an easy way to tell which holes belongs to which solid? I can iterate over all contours in the polygon and find out which are the solids and which are the holes, but that’s about it….

    Of course I could look at all permutations and use the overlap() and covers() methods to find this out, but isn’t there an easier way?

    Regards,

    Diederik

    • Hi Diederik,

      Sorry, I don’t think there’s an easier way. The list of solids and holes is returned by gpc, which does the clipping operations. What I get is only a flat list without any information on the structure.

      Greetings from Berlin, Jörg

      • Thanks a lot for the quick reply, I will figure something out myself then.

        Diederik

        BTW, I visited Berlin last Friday…

  12. Hi Jörg,

    Thanks for the effort! However, I have a question and I am not sure if it is GPC related or in any case if there is something that can be done about it.

    My problem is when I want to add multiple polygons that leave a hole in the center. For example,

    import Polygon.Shapes as ps
    from math import pi

    polys = [ps.Polygon([[1,1], [4,1],[4,2],[1,2]], hole = True) for i in range(4)]
    polys[1].rotate(pi/2,1,1)
    polys[1].shift(1,0)
    polys[2].shift(0,2)
    polys[3].rotate(pi/2,1,1)
    polys[3].shift(3,0)
    pp = reduce(lambda x,y: x+y, polys)

    In principle these 4 rectangles should leave an empty square in the center. However, the result is a square with filled in center.

    I want to have polygons with multiple holes when I make an union.

    Thanks!
    Best regards,
    Jorge

    • Hi Jorge,

      I cannot reproduce any problems with this example. In my tests it gives a rectangular contour with a rectangular hole in the center. Please send me a complete script with some example output and information on your platform and versions of python and Polygon.

      Jörg

  13. Hi Jörg,

    I’m a little new to working with C libraries and I have a problem subclassing Polygon. Maybe you could help?

    I have my code:
    import Polygon as poly
    class Shape(poly.Polygon):
    def __init__(self, points):
    super().__init__(points)
    def __contains__(self, shape):
    return shape.overlaps(self)

    a = Shape(list of points)
    b = Shape(some more points)

    a in b
    Here I will run into trouble for using the wrong type of arguments.

    I changed the code to look like:
    _shape = poly.Polygon(shape[0])
    _self = poly.Polygon(self[0])
    return _shape.overlaps(_self)

    But it seems like a rather awkward solution. Any ideas?

  14. Hi Jörg,
    I wonder If you could help me please, since although I’ve already installed Polygon2, when importing the library I get the next message :

    Traceback (most recent call last):
    File “”, line 1, in
    File “Polygon/__init__.py”, line 5, in
    from Polygon.cPolygon import *
    ImportError: No module named cPolygon

    Hope you can help me please. I’d be really grateful to you.
    Cheers.
    Wronzio

    • Hi Wronzio,
      I know about two different sources for this error message:
      1. The package is not correctly installed.
      2. You are working in the base folder of the source of the package. This doesn’t work.

      Good luck, Joerg

  15. Hi Jörg,

    Thanks for the binding! I’ve run into a bug (a segfault, to be precise), however, and I’m wondering if there’s something specific to my installation that’s causing it. Here’s what I’m doing, and the corresponding segfault:


    from Polygon import Polygon, Utils
    a = array([[0.,0.], [0.,1.], [1.,1.], [1.,0.]]) # a simple square
    p = Polygon(a)
    Utils.pointList(p)
    Segmentation fault (core dumped)

    I’m running python-2.7.3, numpy-1.6.2, Polygon-2.0.4. Could you help?

    Thanks,

    Sourish

  16. Tried that first – just putting a print “hello” before the if statement.

    Doesn’t work. I wonder if it’s because I’m using Python 2.5…

    Thanks for your help,

    Simon

  17. Hi Jörg,

    Thanks very much for the tip. I was indeed working int the install library which was somewhat lazy of me. It works fine elsewhere!

    I now have another issue – can you help me? I am looking to extend the code to provide grow and shrink operations for the polygons. I have already figured out the algorithm when I was using gpc with MATLAB – but now I want to use it with Python.

    I would like to be able to overload the ‘+’ and ‘-’ operators for this, so the following:

    x=y+2

    will make x a polygon that’s the y polygon grown by 2.

    There appears to be strong type checking in the cPolygon.c and this causes an error when I try to implement the above. At first I suspected that the Py_TPFLAGS_CHECKTYPES might be set – but it isn’t.

    I can’t find where the type checking is enabled – and so can’t disable it.

    Any ideas?

    Simon

    • The + and or operators are both mapped with the table Polygon_NumberMethods to the function Polygon_opUnion (everything in the file cPolygon.c). This function checks if both operands are Polygon objects. To change the behaviour of the +-operator you nedd to change the mapping and/or the function.

      Joerg

  18. Hi Simon,
    I know about two different sources for this error message:
    1. The package is not correctly installed.
    2. You are working in the base folder of the source of the package. This doesn’t work.

    Good luck, Joerg

  19. Hi Jörg,
    Thanks for those great bindings.
    Any idea what the following is all about?

    Python 2.5.1 (r251:54863, Aug 12 2010, 11:27:22)
    [GCC 3.2.3 20030502 (Red Hat Linux 3.2.3-59)] on linux2
    Type “help”, “copyright”, “credits” or “license” for more information.
    >>> import Polygon
    Traceback (most recent call last):
    File “”, line 1, in
    File “Polygon/__init__.py”, line 6, in
    from cPolygon import *
    ImportError: No module named cPolygon

  20. Hi Jörg,
    Thanks for those great bindings.
    Could you please change “”.join(l) into b””.join(l) in py3k version of encodeBinary() ?

  21. Hi Diederik,

    thank you for the hint! I fixed this bug in the SVN now. You can wait for the next release or fix it yourself: in Io.py search for the string ','.join and replace the comma with a space. There should be only one occurrence near line 240.

    Jörg

  22. Hi Jörg,

    Thanks for providing the Python bindings for the polygon library, that’s really much appreciated! There’s however a small glitch I ran into while exporting svg files: these files cannot be viewed in all SVG capable programs, e.g. Inkscape or Firefox. This issue has been reported here: https://bugs.launchpad.net/inkscape/+bug/683066. I’m not sure if this export functionality has been created by you or by Alan Murta, but I figured that reporting it here wouldn’t hurt.

    Thanks once again.

    Diederik van Lierop

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">