General Polygon Clipper

Last updated

The General Polygon Clipper (GPC) is a software library providing for computing the results of clipping operations on sets of polygons. It generalises the computer graphics clipping problem of intersecting polygons with polygons. The first release of GPC was designed and implemented in 1997 by Alan Murta. As of August 2009 the final GPC release was version 2.32. The core GPC library is written in the C programming language but the library has also been ported to work with several other languages.

Contents

Availability

Since August 2020, GPC is no longer officially distributed by the author.

In December 2021 a copy of the GPC code (v2.32) was placed on GitHub under the MIT License by Paint.NET author Rick Brewster. [1]

Licensing

Developers may use GPC for any purpose without paid licensing restrictions.

Features of GPC

The following summarises the features and operations on polygons supported by GPC.

GPC can compute the following clip operations: difference, intersection, exclusive-or and union.

Polygons may comprise multiple disjoint contours. Contour vertices may be specified as clockwise or anticlockwise. Contours may be convex, concave or self-intersecting. Contours may be nested. In other words, polygons may have holes.

The clip operation output from GPC is a set of polygon contours or tristrips. Holes and external contours are differentiated in GPC's output. Coincident edges and degenerate regions are handled correctly.

Examples of GPC operations on sets of polygons

The following four images show examples of GPC computing operations between two polygon sets. The first polygon set comprises outlines of the United Kingdom and Ireland. The second polygon set comprises the four large inward-pointing arrows. In each example, the areas resulting from the GPC operation between the two sets of polygons are rendered in colour.

This example shows difference between the two sets:

Example of GPC Difference GPC Polygon Clipper difference.gif
Example of GPC Difference

This example shows intersection between the two sets:

Example of GPC Intersection GPC Polygon Clipper intersection.gif
Example of GPC Intersection

This example shows union between the two sets:

Example of GPC Union GPC Polygon Clipper union.gif
Example of GPC Union

This example shows exclusive-or between the two sets:

Example of GPC Exclusive-or GPC Polygon Clipper xor.gif
Example of GPC Exclusive-or

Ports and language bindings

The core GPC code is written in C, but the GPC user community has contributed a number of ports and bindings (or wrappers) for various other languages (ActionScript 3, Borland Delphi, C#, GNU Octave, Haxe, Haskell, Java, Lua, Pascal, Perl, Python, VB.Net). All of these ports and bindings are freely available.

Related Research Articles

<span class="mw-page-title-main">"Hello, World!" program</span> Traditional beginners computer program

A "Hello, World!" program is generally a computer program that ignores any input, and outputs or displays a message similar to "Hello, World!". A small piece of code in most general-purpose programming languages, this program is used to illustrate a language's basic syntax. "Hello, World!" programs are often the first a student learns to write in a given language, and they can also be used as a sanity check to ensure computer software intended to compile or run source code is correctly installed, and that its operator understands how to use it.

<span class="mw-page-title-main">Simple DirectMedia Layer</span> Free software multimedia library

Simple DirectMedia Layer (SDL) is a cross-platform software development library designed to provide a hardware abstraction layer for computer multimedia hardware components. Software developers can use it to write high-performance computer games and other multimedia applications that can run on many operating systems such as Android, iOS, Linux, macOS, and Windows.

OCaml is a general-purpose, high-level multi-paradigm programming language which extends the Caml dialect of ML with object-oriented features. OCaml was created in 1996 by Xavier Leroy, Jérôme Vouillon, Damien Doligez, Didier Rémy, Ascánder Suárez, and others.

In computing, the utility diff is a data comparison tool that computes and displays the differences between the contents of files. Unlike edit distance notions used for other purposes, diff is line-oriented rather than character-oriented, but it is like Levenshtein distance in that it tries to determine the smallest set of deletions and insertions to create one file from the other. The utility displays the changes in one of several standard formats, such that both humans or computers can parse the changes, and use them for patching.

Message Passing Interface (MPI) is a standardized and portable message-passing standard designed to function on parallel computing architectures. The MPI standard defines the syntax and semantics of library routines that are useful to a wide range of users writing portable message-passing programs in C, C++, and Fortran. There are several open-source MPI implementations, which fostered the development of a parallel software industry, and encouraged development of portable and scalable large-scale parallel applications.

<span class="mw-page-title-main">Bounding volume</span> Closed volume that completely contains the union of a set of objects

In computer graphics and computational geometry, a bounding volume for a set of objects is a closed volume that completely contains the union of the objects in the set. Bounding volumes are used to improve the efficiency of geometrical operations by using simple volumes to contain more complex objects. Normally, simpler volumes have simpler ways to test for overlap.

<span class="mw-page-title-main">Isosurface</span> Surface representing points of constant value within a volume

An isosurface is a three-dimensional analog of an isoline. It is a surface that represents points of a constant value within a volume of space; in other words, it is a level set of a continuous function whose domain is 3-space.

Clipping, in the context of computer graphics, is a method to selectively enable or disable rendering operations within a defined region of interest. Mathematically, clipping can be described using the terminology of constructive geometry. A rendering algorithm only draws pixels in the intersection between the clip region and the scene model. Lines and surfaces outside the view volume are removed.

<span class="mw-page-title-main">Clipper (electronics)</span>

In electronics, a clipper is a circuit designed to prevent a signal from exceeding a predetermined reference voltage level. A clipper does not distort the remaining part of the applied waveform. Clipping circuits are used to select, for purposes of transmission, that part of a signal waveform which lies above or below the predetermined reference voltage level.

<span class="mw-page-title-main">Boolean operations on polygons</span>

Boolean operations on polygons are a set of Boolean operations operating on one or more sets of polygons in computer graphics. These sets of operations are widely used in computer graphics, CAD, and in EDA.

JSDoc is a markup language used to annotate JavaScript source code files. Using comments containing JSDoc, programmers can add documentation describing the application programming interface of the code they're creating. This is then processed, by various tools, to produce documentation in accessible formats like HTML and Rich Text Format. The JSDoc specification is released under CC BY-SA 3.0, while its companion documentation generator and parser library is free software under the Apache License 2.0.

The Sutherland–Hodgman algorithm is an algorithm used for clipping polygons. It works by extending each line of the convex clip polygon in turn and selecting only vertices from the subject polygon that are on the visible side.

Protocol Buffers (Protobuf) is a free and open-source cross-platform data format used to serialize structured data. It is useful in developing programs that communicate with each other over a network or for storing data. The method involves an interface description language that describes the structure of some data and a program that generates source code from that description for generating or parsing a stream of bytes that represents the structured data.

PGF/Ti<i>k</i>Z Graphics languages

PGF/TikZ is a pair of languages for producing vector graphics from a geometric/algebraic description, with standard features including the drawing of points, lines, arrows, paths, circles, ellipses and polygons. PGF is a lower-level language, while TikZ is a set of higher-level macros that use PGF. The top-level PGF and TikZ commands are invoked as TeX macros, but in contrast with PSTricks, the PGF/TikZ graphics themselves are described in a language that resembles MetaPost. Till Tantau is the designer of the PGF and TikZ languages. He is also the main developer of the only known interpreter for PGF and TikZ, which is written in TeX. PGF is an acronym for "Portable Graphics Format". TikZ was introduced in version 0.95 of PGF, and it is a recursive acronym for "TikZ ist kein Zeichenprogramm".

SuperPascal is an imperative, concurrent computing programming language developed by Per Brinch Hansen. It was designed as a publication language: a thinking tool to enable the clear and concise expression of concepts in parallel programming. This is in contrast with implementation languages which are often complicated with machine details and historical conventions. It was created to address the need at the time for a parallel publication language. Arguably, few languages today are expressive and concise enough to be used as thinking tools.

The Vatti clipping algorithm is used in computer graphics. It allows clipping of any number of arbitrarily shaped subject polygons by any number of arbitrarily shaped clip polygons. Unlike the Sutherland–Hodgman and Weiler–Atherton polygon clipping algorithms, the Vatti algorithm does not restrict the types of polygons that can be used as subjects or clips. Even complex (self-intersecting) polygons, and polygons with holes can be processed. The algorithm is generally applicable only in 2D space.

The Greiner-Hormann algorithm is used in computer graphics for polygon clipping. It performs better than the Vatti clipping algorithm, but cannot handle degeneracies. It can process both self-intersecting and non-convex polygons. It can be trivially generalized to compute other Boolean operations on polygons, such as union and difference.

<span class="mw-page-title-main">TensorFlow</span> Machine learning software library

TensorFlow is a free and open-source software library for machine learning and artificial intelligence. It can be used across a range of tasks but has a particular focus on training and inference of deep neural networks.

<span class="mw-page-title-main">RaftLib</span>

RaftLib is a portable parallel processing system that aims to provide extreme performance while increasing programmer productivity. It enables a programmer to assemble a massively parallel program using simple iostream-like operators. RaftLib handles threading, memory allocation, memory placement, and auto-parallelization of compute kernels. It enables applications to be constructed from chains of compute kernels forming a task and pipeline parallel compute graph. Programs are authored in C++.

Vector overlay is an operation in a geographic information system (GIS) for integrating two or more vector spatial data sets. Terms such as polygon overlay, map overlay, and topological overlay are often used synonymously, although they are not identical in the range of operations they include. Overlay has been one of the core elements of spatial analysis in GIS since its early development. Some overlay operations, especially Intersect and Union, are implemented in all GIS software and are used in a wide variety of analytical applications, while others are less common.

References

  1. "GeneralPolygonClipper". GeneralPolygonClipper on GitHub. Retrieved 22 December 2021.