A Polygon Library

A short note on reading this manual on the web vs on paper
Introduction

Polygon operations
Polygon operations on holes
Transformations
Advanced transformations: Offsetting
Lines and Points
Paths
Redefining ‘polygon’
Stack interface
Display
Interactions between polygon operations and display
Curves
Background

The Display, and file output
The Library Calls
Example programs
Some more detail
(Memos to self while creating documentation)

A short note on reading this manual on the web vs on paper

The best way to read this document is on the web, to take advantage of the various links to other relevant information.

For example, if you hover your mouse over an image, you'll see the actual code that was used to create that image. You can also click on the image to have a proper window pop up from which you can cut & paste the source code.

SIDEBAR: You should also be aware that this manual describes an ideal polygon library, for which an implementation is provided in the form of an interface layer on top of an existing polygon library. Any places where the implementation falls short of the ideal will be noted in a sidebar like this. Later releases may keep the same interface while using a different underlying implementation.

Introduction

A polygon library is a collection of procedures for manipulating polygons. In high-school, polygons meant regular polygons like these...

But in our context, polygons are arbitrary bounded areas like these... Or even these, which have holes in them...
(sometimes I'll shade the stuff to highlight the holes)

And occasionally polygons can be quite complex, containing holes that in turn contain more polygons...

We call a single contiguous area a sheet. Polygons are defined as the outer containing sheet and any nested polygons within any holes contained in that sheet.

Although they're not very common, there are two more forms of polygon you should know about - empty polygons, and infinite sheets. An empty polygon is effectively a point - it has an X and Y coordinate but zero area. An infinite polygon is the opposite of that - infinite area and no boundary (but it does still have an X,Y origin point, same as all polygons). I've mentioned holes - a stand-alone hole can't exist but a hole embedded in an infinite sheet is perfectly valid.

A bounded sheet. Also sometimes referred to as stuff.
A hole in an infinite sheet

Polygon operations

Polygon operations are basically Boolean operations performed on areas rather than bits. Union is the equivalent of OR, Intersection is the equivalent of AND and Symmetric Difference is the equivalent of EXOR. Complement is like NOT and turns stuff into a hole and vice-versa. All the other analogs of Boolean operations can be synthesized from these. Let's look at some examples:

Union

     A, B                                             A OR B

Intersection

             A, B                                               A AND B

Subtraction

                     A, B                             A-B (A AND (NOT B))

Reverse Subtraction

                    A, B                              B-A ((NOT A) AND B)

Symmetric Difference

           A, B                                       A EXOR B

Complement

A                                            NOT A

Polygon operations on holes

If a stand-alone hole (i.e. a hole in an infinite sheet) is subtracted from an overlapping bounded polygon, the result is identical to intersecting the complement of the hole with the bounded polygon. Similar logic can be applied to any operation with a hole (in an infinite sheet) rather than a bounded sheet.
A, B A-B (A AND NOT(B))
Intersection

Transformations

As a polygon is made from lines joining up points, it's possible to transform the individual points with the result of transforming the entire polygon. The library provides a mechanism to process polygon points with any arbitrary function. Some simple transformation functions are provided, such as Scale, Shear, Rotate, Reflect, and Reposition (aka Translate).

Any of these transformations could be applied using a 3X3 matrix and a general affine transform procedure - the interface is more complex, but using the matrix method does allow multiple transformations to be stacked and executed by a single compound transformation that is the result of multiplying all the individual transformation matrices together.

Scale

Shear

Rotate

Reflect

Reposition (also called Translate)

Advanced transformations: Offsetting

Although polygons can be easily scaled up or down with a simple transformation, there's a different kind of scaling transformation that is useful with polygons: it inflates the area of the polygon like a balloon - but deflates any holes. It'll be easier to understand if I give some examples. Making a polygon fatter used to be called Bloating and making it thinner was called Shrinking, but the more modern terminology is Insetting and Outsetting, or more generically Offsetting which can be positive or negative. (Also somewhat ambiguously called buffering; and a slightly different procedure that has a very similar result is the Minkowski Sum of a polygon with a circle.) [Aside: it may be possible that the use of the word 'buffer' in this context derives from the French 'Bouffer' which means to puff up or balloon in size.]

The user has a choice of how to build the offset corners - they can be square, beveled or rounded. These are really all the same thing - it's a question of how many segments to insert when creating the corner - 0 for square corners, 1 for beveled corners, and many for rounded corners. (In this particular implementation, rounded corners are approximated by eight straight line segments.)

Bloat (Outset, Positive Offset)

Original Bloat_(squared, beveled, rounded)

Shrink (Inset, Negative Offset)

Original Shrink_(squared, beveled, rounded)

One thing that can happen during an offsetting operation is that parts of the original polygon self-intersect or even turn inside-out. (overlap and underlap respectively)) When this happens, the caller has to specify how the damaged area is repaired in order to end up with a valid polygon. Here I use the default repair options:

Self-intersected Bloat

Touches as gap reduces

Inside-out area from Bloat

(Inside-out hole becomes stuff; stuff on stuff
remains stuff, so the hole disappears.)

The default behaviour of the polygon library is to do the ‘sensible expected thing’ if one exists - but the specific method of repair can be forced if need be. There will be more on what is a valid polygon and how to repair it later.

Lines and Points

Polygons can be used for all sorts of graphics; for instance a plain line could be represented by a rectangle with zero width - but it's a lot simpler if the polygon library has proper support for both lines and points. For example, you can shrink a rectangle until it becomes a line; and conversely you can bloat a line and generate a rectangle. Bloating a point turns it into a circle. But this brings up another concept that will be useful to understand... end caps and joins. This is basically the same as the creation of corners that we saw in the last example of bloating above:
Bloated line with default, squared,
and rounded end-caps and corners.

A point becomes a square when bloat_squared,
and a circle when bloat_rounded; a point
that is bloated with the default option remains a point.

Paths

Usually polygons are created from an array of points, but sometimes it is easier to create the polygon by starting from an origin point and creating a path by a series of incremental moves. There are two ways to convert paths into polygons:

Call a library procedure to convert a path into a polygon.
- Option 1: First extend the path by following it back to its starting point in the reverse direction. This will form a zero-width polygon (or a zero-width hole, like a scissor-cut in a sheet of paper)
- Option 2: Explicitly add a segment from the final point at the end of the line to the initial point at the start of the line. However if you do not force the start and end points of the line to be explicitly coincident, the library call will join them up for you anyway!
Bloat a line. Note that bloating a line then shrinking it by the same amount will also produce a zero-width polygon. In fact it's probably true to say that lines are zero-width polygons already, for most circumstances. And Points are zero-area polygons.

It is possible to perform operations between polygons and lines. Here we'll create an algorithm to add cross-hatching to a polygon, by making use of intersections between a polygon and a grid of lines:

Polygon Circumcircle Squared Gridlines Rotated Grid Hatching Result

First we start with our polygon, in this case a triangle. We use a library call to determine the minimum bounding circle that fits around our polygon, along with the center of that circle. Because circles are computationally expensive to deal with, we simplify our problem by expanding our clipping area into a simple square which is large enough to contain the circle.

We now generate a grid of parallel lines that fits in the enclosing square. We can rotate this grid to give us our preferred angle of cross-hatching, and be confident that the rotated grid does indeed cover our original polygon.

Finally we mask our original polygon with this rotated grid, by intersecting the two. Since this intersection loses the outline of the polygon, we add that back in too.

By choosing a gridline separation that matches the pixel width of the line being drawn (or, more practically, matches the width of the engraving tool being used in the CNC), you can actually generate a complete solid area-fill of the entire polygon for your selected output device.

SIDEBAR: I was originally unsuccessful in creating LibGEOS polygons containing both lines and areas, so for a time I simulated the effect of a combined polygon and line object by creating two separate objects on the object stack. (More info on the stack will be given in the later section detailing the programmer interface.) However I have subsequently managed to create these heterogenous collections of lines and polygons and points successfully, and am in the process now of updating all the examples to use the simpler code.

You can combine the hatching process with a rotation for more traditional cross-hatching, and even use two different hatching angles to create more patterns. The polygon library contains a Hatch procedure which creates the hatch pattern for a polygon and pushes it on the stack, above the original polygon. If you want the outline to be attached to the polygon you can do so by calling the Combine() procedure, but the library leaves that step to you to perform explicitly because in some other circumstance you may prefer to use the hatch pattern on its own without the polygon's outline.

In the hatching example above, we intersected a line with a polygon to produce a clipped line, like this:

Line intersected by a polygon - A AND B. (Rectangle A, Line B, Result A AND B)

These operations may be more obvious if you think of the line as a zero-width polygon. If we do the same two operations again but with a non-zero width polygon (we'll make it a little thicker) you should be able to see the parallel.
Thickened line intersected by a polygon - A AND B. (Rectangle A, Line B, Result A AND B)

However a subtraction operation allows us to take a polygon and use that same line to split it into multiple parts - B-A. (Rectangle A, Line B, Result B AND NOT A)

Polygon split by intersecting with a line.

SIDEBAR: Not sure if this works with a plain line yet.

Again we'll use a very thin polygon rather than a line so we can see what's happening better.
Polygon split by intersecting with a slightly bloated line.

There's also a degenerate case where the line doesn't cut the polygon from edge to edge - in that case it creates a cut in the polygon as if it were paper cut by scissors:

Polygon and line. Cut Polygon. Polygon cut by bloated line.

Again, using a slightly bloated line to cut with makes it more visible. As you can see, the generated cut is not a simple line - it is a polygon edge that goes inwards and then back outwards covering the exact same path as the inward cut.

SIDEBAR: This is another problematic operation under LibGEOS. The polygon appears to be automatically healed when there are two touching edges. Though that could be accidental on my part and caused by the automatic repair code I execute after every binary operation...

Redefining ‘polygon’

Now that you are familiar with all 3 types of object that the polygon library can manipulate, I can admit that the objects which the library passes around as ‘polygons’ are actually collections of all three simpler types as now described. Also the limitation that polygons have one single encompassing boundary at the top level is not the case in the objects that the library handles - a single ‘Polygon’ variable may contain more than one disjoint and non-intersecting top-level polygon. But rather than refer to ‘polygon sets’ or ‘a polygon collection’ I'll continue to use the simple expression ‘polygon’ to describe one of these collections of 0-, 1-, and 2-D geometric objects.

Stack interface

Although it is orthogonal to the operations provided by the polygon library, the way that polygon operations are invoked in the library (the API) is quite distinctive and influences the user's perception of the polygon library. The ‘obvious’ and perhaps more traditional interface is a simple functional one - a call something like A = Union(B, C). This works quite well for many styles of applications where the code is crafted by hand - geography processing for example. But in other domains, such as CAD or VLSI layout, the polygon operations are frequently generated by programs acting on other data. From experience in this area I've found that a stack-based API is often simpler to use; for example: Push(A); Push(B); Union(); C = Pop().

This library implements both styles! The underlying base procedures are in the functional style, and a stack-based interface is supplied as a layer on top of that. The stack is visible to the user and as a convenience, the display procedure when called can either display a fixed number of items at the top of the stack - or all items on the stack, at the user's discretion.

Display

Different output devices can be selected before any polygons are drawn. Currently I support vector output on the PiTrex (a Vectrex driven by a Raspberry Pi, which has to be refreshed (i.e. the graphics re-drawn) continuously at 50Hz), and on any device supported by OpenGL/Glu/Glut, which is most raster displays. Support is planned for storage tube displays (slower to draw, but no real-time refresh being necessary) and various output file formats, including SVG.

Interactions between polygon operations and display

Normally, good programming practise would keep device-dependent display totally independent from the data structure side of the polygon library. However because of an implementation restriction to do with approximating curves by using straight-line segments, that has not been possible with this package. In order to support the refresh rate of some dynamic vector graphic displays, it is sometimes necessary to create curves using fewer line segments than would be used on storage tube displays or raster displays. This should be done by parameterising the resolution of curves and setting that parameter at the same point in your application as you select the output device. A better understanding of the issues may be had by reading the next section on curves.

Curves

The current implementation of this interface is built on a polygon library called LibGEOS, designed primarily for use by the geography community. In fact our library was created specifically to make the GEOS system more approachable by the CAD and general computer science communities, repackaging its calls in an interface that would be more familiar to those communities. Unfortunately LibGEOS lacks some features that a full general-purpose polygon library would prefer to have. Amongst those is internal support for curved lines and polygons. I attempt to mitigate this shortcoming by supplying a procedure to treat a set of points (either a line path or a polygon boundary) as a Bézier curve, with the curve being constrained to be coincident with the line or boundary at the points of inflection. Note that these are not ‘control points’ in the sense of Bézier curves, if you are familiar with that concept. (They're ‘knots’.) The user never needs to create Bézier control points and never sees the ones that the polygon library creates for them internally.
Line superimposed by curve which touches at all the points of inflexion on the line.
Polygon superimposed by curve which touches at all the points of inflection on the polygon boundary.

Unfortunately the process of taking a line or polygon and treating it as the basis of a curve, and then approximating that curve by decomposing it into many short straight line segments, is a one-way operation. Once converted, the line or polygon cannot be simplified back into the original set of points.

As mentioned earlier, the granularity of the decomposition of a curve into straight-line segments can affect the output display - it is recommended to use a much coarser approximation to a curve if your output device is a refreshed vector display, which cannot handle drawing large numbers of vectors at an acceptable refresh rate. The granularity of curve approximation can be increased for final output to a device such as a VLSI mask maker (projection lithograph system) or a CNC engraving tool.

Curves with varying approximations:
Polygon 64 steps 256 steps 1024 steps

SIDEBAR: The intent of the granularity parameter was to define the number of straight-line segments used to implement each curve segment. It turned out in practise that the parameter actually controlled how close to the defined points the curve would come. To get a really good fit, I had to use a very fine granularity. What I may eventually do is generate using a fine granularity and then reduce the curve to simpler segments as a post-processing step.

Background

I first learned about polygon operations in 1978 from my CS2 tutor, Irene Buchanan, at Edinburgh University. Irene and her collaborator, Eric Barton, had produced one of the earliest polygon libraries, which they documented in an Edinburgh Computer Science Department internal report, “The Polygon Package”. Later when I was working at Acorn Computers in the UK, in the VLSI tools group, as Acorn were developing the ARM chip, my manager Lee Smith (also originally from Edinburgh University) wrote another polygon library for Acorn that was specifically targetted towards VLSI layouts. It was from him that I appreciated the value of a stack-based interface in that applications domain.

In later years, indeed after retirement, I picked up the hobby of woodworking using CNC equipment. Although many off-the-shelf tools exist for the design of objects and their implementation using CNC devices, none of them appealed to me as a programmer so I attempted to write my own. Although partially successful, these attempts would hit areas of difficulty that to me appeared to be easily solved if only I had access to a good polygon library, so at that point I started looking for an open source polygon library that I could incorporate into my home-made CNC CAD tools...

This turned out to be easier said than done, and it was a few years until I came across a suitable solution. There were two problems: the first was that I program mostly in C nowadays, and frankly don't have the patience or interest to learn C⁺⁺ to the level that would be needed to write in it extensively. There were very few polygon libraries available written in plain C. The second was that those few packages written in C did not support polygon offsetting, which is a necessary and crucial function for many CAD processes. For example, to convert a PCB layout that was designed for PCB creation using a photo-resist into one that was suitable for creation using engraving (using a layout style called ‘isolation routing’), it is necessary to bloat the metal tracks, subtract the original track from the bloated version, and remove the metal from the remaining pattern using the CNC engraving tool.

With these two constraints, there appeared to be nothing available that would offer the functionality I wanted in a pure C package. Or so I thought, until I discovered a feature of LibGEOS that I had overlooked in my original research. LibGEOS is written in C⁺⁺, but - unlike many other C⁺⁺ packages which are accessible from C only through complex interfacing methods (writing in C but compiling with a C⁺⁺ compiler, or performing nasty name-mangling tricks at link time, or writing cross-calling interface procedures that can't access all the C⁺⁺ procedures) - this package came with a plain C interface already built. It was accessible through a Unix header file and accompanying library that could be accessed from standard C with no C⁺⁺ involvement at all other than building the initial library with the supplied make files, and for most target systems LibGEOS could in fact be installed with a simple 1-line command using the system's package manager.

So... that's where I am with this project today - a working polygon library with the functionality I expect, accessible from C, and with an interface layered over it that is familiar and comfortable. There is not a 100% fit between my concept of an ideal polygon library and what it supplied by LibGEOS, but it is closer than any alternative I've found so far.

The Display, and file output

I touched on the display model in the introduction. Now we'll go into it in some more depth, and cover the output of polygons in various formats such as SVG.

Talk about the real-time constraints of refresh vector graphics devices like the PiTrex, and approximations to curves..

Talk about BBC Micro VLSI editor and how Charles terminal used actual layers but Beeb didn't have enough RAM to do anything similar, so a selected set of overlaps (ie transistors) was explicitly drawn by using polygon operations to detect the overlaps and explicitly draw those areas in a different graphical style (which on the Beeb with so few colours meant dithering.)

Note that overlapping two transparent polygons that have colours assigned in the userdata generates an overlap whose colour is a blending function of the colours of the original polygons. (This generalises to any number of overlaps)

The Library Calls

The Applications Programming Interface (or API) - what we used to just call the header file - is the primary specification of how to access the Polygon Library from a programming language; in this case, C. Below is an annotated version of the header file, "polygon-package.h", with extra explanations and links to example code. More examples can be seen above by mousing over and clicking on the examples of polygon operations in the Introduction chapter above.
PLEASE NOTE: for the short term during which the interface is somewhat in flux, and before I've created the better documented version of the header file, I'm just inserting the actual header file below with some HTML trickery. Unfortunately the HTML hack that I'm using doesn't appear to handle < and > in a <pre>...</pre> section, so the C code is marginally corrupted. Bear with me for the moment. I'll be fixed in a few days. (Famous last words).

Example Programs

PCB

PCB Isolation routing

Simple overlay

Some more detail

There is some background detail that's not critical to using the Polygon Library, but which is the sort of thing that an interested programmer would like to be aware of.

Units

The Polygon library works in dimensionless units using the C type 'double' which is a large floating point type. There are only two places where dimensions are treated as integers - the first is when they are printed out by one of the library procedures - it uses WKT format but deliberately asks it to write values out as integers. (Which I think are rounded but I would need to check to be sure). The second is when the viewport dimensions are passed to the PiTrex graphics package, which is an all-integer system. This is not a problem unless the user has been working with very small units, in which case there may be some scaling issues and rounding problems when displaying on the PiTrex.

However, in my own code and the examples here, I find it useful to impose an absolute measure of size. I define units as microns and write conversion procedures to allow sizes to be specified in more familiar units, for example cm(3) which is converted into 30000 base micron units. I picked the micron as my smallest unit as it was sufficiently accurate for all the CNC machining that I do. Someone working in the VLSI field might prefer to use nanometers nowadays!

      static inline double mm(double microns) { return round(microns*1000.0); }    // convert a unit specified in millimeters into microns
      static inline double cm(double microns) { return round(microns*10000.0); }   // convert a unit specified in centimeters into microns
      static inline double  m(double microns) { return round(microns*1000000.0); } // convert a unit specified in meters into microns
      static inline double in(double microns) { return round(microns*25400.0); }   // convert a unit specified in inches into microns
      static inline double ft(double microns) { return in(microns*12.0); }         // convert a unit specified in feet into microns

This works quite well but you do have to be careful to wrap all dimensioned units with the appropriate conversion function, and it's easy to forget one when you first start coding in this style, though it becomes second nature soon enough.

C⁺⁺11 has some support for dimensioned units, but if you want that in C you'll need to do some tricky macro pre-processing... I wrote this paper on the subject back in 2012, but never did get around to writing code to implement it.

Nested Polygon Hierarchy

In the Introduction I explained how polygons could be nested inside the holes in other polygons, and that the outer-level polygon and its nested children could all be treated as a single unit. In some polygon libraries this hierarchy is explicit, but in ours the hierarchy is implicit and only becomes visible when you 'Uncombine()' a single object into its component parts - the top-level polygon and its immediate children. This interface was chosen because the LibGEOS library that this package is currently implemented on top of, does not have a concept of nested polygons. However it does have a concept of a collection of polygons in a single object, so it is this data structure that we use to implement nested polygons, and we make the hierarchy visible by looking at the results of the Uncombine() operation.

Note that because the polygon objects in our system are potentially collections of non-overlapping polygons rather than a single top-level polygon, the Uncombine() operation has a mechanism to indicate that this was the case in its result code: if an Uncombined polygon was a single polygon containing nested polygons, the integer result is positive; if it was a collection of non-overlapping polygons the result is negative.

To extract the full tree-structure from a heavily-nested polygon, you need to Uncombine() all its children until the result of the Uncombine() call is 1 for all children.

Note that we haven't defined what to do with a combined object containing lines and points yet.

Low-level representation of polygon boundaries

If you are familiar with other polygon libraries you may know that the most common internal data structure used to represent polygons heavily makes use of the chirality of the rings that store the perimeter of a polygon - if it is stored as a clockwise ring of points then it is one type of object and if it is an anti-clockwise ring then it is the other type - the types being stuff and holes... but the choice of which is which is quite arbitrary - in one library Clockwise loops may be holes and in another, holes are anti-clockwise. So a deliberate decision was made to not make the direction of a loop visible in this library, but instead explicity define outlines as outer (containing stuff) or inner (a hole in a larger containing sheet). The only time that the user will need to access a ring of points in a specific orientation is when exporting from this system to some other system where the chirality matters. That is why there is a library procedure to allow the user to define the handedness of stuff and holes when calling the procedures to walk the polygon data structure and export coordinates.

The curve algorithm hacks

Some words on the trick of reversing the direction of curve generation, and averaging the two curves to get a symmetric result; and why it doesn't immediately work for polygon loops (but might be fixable with some coding effort).

Varargs hack!

The ability to move a whole group of objects when pushing them on the stack rather than Transform-ing each one.

  PlaceAt( coord,
    Poly1,
    Poly2,
    PolyN
  );

Push() is just PlaceAt() with a 0,0 parameter... May expand Push() to take multiple parameters too.
Document the varargs macro hack and point out that the limited number of parameters is not really a problem because it is just a programmer's syntactic convenience - if you were doing something to more than 64 objects you wouldn't be doing it inline in the source code like that.

Limits to the shrink operation

Rather annoyingly, the underlying LibGEOS library inset operation exhibits this behaviour: when shrinking (insetting) a polygon, opposite faces that are closer than the inset distance just disappear. It would be really useful if instead there was an option which caused them to degenerate into a single line or zero-width polygon instead - so that repeated shrinking of a polygon would eventually reduce it to its straight-skeleton. There appears to be no support in LibGEOS for determining a medial axis (centerline). I made some notes while trying to find a solution to the 'curve hack' mentioned earlier.

Similar to question at https://community.esri.com/t5/geoprocessing-questions/how-to-calculate-intermediate-polygon-between-two/td-p/273042
also known as centerline: https://mapserver.org/_images/centerline-greatlakes.png
This python code might do it but I need C: https://github.com/fitodic/centerline (https://centerline.readthedocs.io/en/latest/)
The spine of a straight skeleton could work too.
The PostGIS package has ST_ApproximateMedialAxis: https://postgis.net/docs/ST_ApproximateMedialAxis.html
Would like a 'thin' polygon offsetting variant that stops just before it is inset out of existence. Like https://gis.stackexchange.com/questions/33887/finding-centrelines-from-polygons-in-qgis
A sort of inverse-Minkowski using the inscribed circle call might be possible too... constructing a line from all the centers of every possible inscribed circle...
turns out this exists (elsewhere) and is called the "MAT algorithm" ( https://www.mdpi.com/2220-9964/9/5/304 Fig 4. )

Fortunately, after all that research and contemplation, I finally had a 'Doh!' insight - for this specific problem, when I realised that a simple arithmetic average of the two curves was all that I needed! But there are many other circumstances where such a cheap solution is not the answer, and I will be asking the LibGEOS people if perhaps they can add such a facility some day (or maybe it can be retrofitted in user-written code...)

Fortunately for several of my own requirements (area-filling on a raster display, or cutting out an area with a CNC), repeated shrinking can be made to work as long as the width of the shrink is less than half of the width of a pixel or the CNC tool. Otherwise gaps can remain close to the straight skeleton of the polygon. Reading between the lines at some of the discussions on the subject, the problem appears to be that finding the centerline requires an intensely iterative solution which appears to be anathema to programmers who prefer a one-step analytical solution to all problems. Though that shouldn't be a worry to people who are happy enough to calculate Voronoi or Delauney diagrams in a similar manner.

A bunch of other things from the TO DO section below that should be written up in more detail but don't have a more appropriate place to go.

Documentation TO DO list: Implementation details and restrictions

As you can see this manual is very much in the process of being written; I'm taking a break at this point to do some proof-reading and also update the software to more closely approximate to the manual! Below are my notes of areas still to tackle in both the software and this manual. In the meantime I'll announce this project to a few friends and get some feedback on the work in progress so far.

Curves
CCW vs CW rings (internal detail) https://gis.stackexchange.com/questions/119150/order-of-polygon-vertices-in-general-gis-clockwise-or-counterclockwise
extend definition of polygon to be sheet+lines+points (rename lines to paths?)
Perhaps extend the use of the paper+scissors metaphor, especially to explain half-edges.
limitation of LibGEOS polygons: holes but no nested polygons
Why nested polygons are useful. But is this something better left to application level? (No, it isn't. It's just a limitation of LibGEOS)
LibGEOS lack of properly nested polygons. Actually implemented as a collection of 1-level polygons (boundary + holes). Can extract hierarchy using polygon operations.
limitations of using the polygon library's internal representation of polygons as a user-level data structure (trying to avoid data redundancy)
Polygon library is deliberately limited - it is too tempting to let it develop into something like SVG or Inkscape! Provides underlying mechanisms that let you build systems like that on top of it.
No stand-alone holes
No infinite sheets
No arbitrary user-tagged data associated with a polygon?
Shrinking: when step exceeds width, would like a line. Instead it disappears. Makes fill procedure difficult.
Difficulty of intersections of curves - mathematically impossible to do just from control points - needs flattening. But see Bézier Intersection (older page) Ditto wrt transforms.
Re-constitution of control-point-created curve from segments (like Neil Raine's curve-fitting for font extraction, or potrace/autotrace)
See https://github.com/silasfiore/svg_cnc re both the above
transform graphics: https://www.google.com/search?q=2d+geometric+transformation+matrix+rotate+scale+shear+project
types of transform. including affine transforms: https://www.google.com/search?q=affine+transforms
Joins - LibGEOS version and options - get them primarily from bloating corners. bloated lines are a subcase.
Notes on similarity to SVG - except svgs perform ops at draw time on the actual pixels after all transformations have been applied - not the underlying polygons
See https://kevin-arias.github.io/Rasterizer/ for matrix transforms and other info (from https://github.com/Kevin-Arias/Rasterizer)
Add HPGL and postscript to potential output formats. gnuplot?
curve support could be possible - https://inkscape.org/news/2018/11/11/graphics-math-library-2geoms-first-release-availab/
Use of double rather than int or long long int. Short note on rounding and precision.
Planes/Layers - more of an application data structure
Using the stack to display outline and hatch pattern as two separate objects because Union(lines,sheets) seems not to work...
trying to use LibGEOS polygons as master copy of data rather than keeping an application master copy
Arcs - circle segments - (Note: CGAL handles polygons with circular arcs)
Ellipses - sheared circles
Béziers - everything else. Bézier intersection is a hard problem https://www.google.com/search?q=mathematical+calculate+curve+intersection+bezier+transform. Intersecion of a Bézier curve and a straight line: https://www.particleincell.com/2013/cubic-line-intersection/
Create new terminology: fixed points as opposed to control points, for Béziers. Fixed points being the endpoints of line segments through which the curve must pass.
Even straight lines could be implemented using Béziers. Two coincident fixed points form a sharp corner.
https://www.google.com/search?q=applying+transform+to+bezier+curve+control+points
https://pages.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/Bezier/bezier-construct.html CAN transform control points! “Affine invariance”
NOT is also known as Complement()
Infinite sheet is a subset of NEF Polyhedron - https://doc.cgal.org/latest/Nef_2/index.html#Chapter_2D_Boolean_Operations_on_Nef_Polygons
https://mcmains.me.berkeley.edu/pubs/DAC05OffsetPolygon.pdf
don't forget I rationalised the endcap/corner names and dropped mitred in favour of beveled. Update code to match docs.
(also the actual endcaps aren't consistent for squared/beveled(mitred) options)
Bloating a point only works with the squared and rounded options for now.
~~Either clicking on or mousing over the images should show the code that generated them. Tooltips?~~ Or use the html from my folded code project?
Dotted and dashed line styles. Colours. Fills. Actual vs simulated Transparency?.
Vectrex data-structure output
~~I forgot about reflections in the transformations (although a scale transformation of -1 in one axis has the same effect).~~ And the shear parameters may need a little explanation.
See also https://git.osgeo.org/gitea/postgis/postgis/src/branch/master/liblwgeom
and https://github.com/shapely/shapely/blob/main/src/geos.c
Need a GetCenter(Poly, &cx, &cy) call - returns center of bounding box. (All true origins are 0,0). Also useful, center of bounding circle. How about center of gravity (a.k.a centroid)?
Combine - can take ... parameters Or just have stack-based interface and do “for (i=0;i<3;i++) Combine();”? Stack-based version destroys its inputs. Functional version does not.
Uncombine - uncombine takes TOS and separates into top-level poly and next level only (ie contents of top-level holes). returns int to say how many pieces. (>=1) Contents of top-level holes may also contain nested polygons.
placeat can take ... list of polygons and pushes them all on stack, applying transformation to each one
Flatten() - equivalent to fully recursive uncombine
make no-encap and bevelled the default bloat command (call it 'truncated'? 'abrupt'? 'minimal'?) - squared and rounded being the optional versions? I really don't want encap and join parameters, but I also don't want 3X3 procedure variations either. 'truncated' nomenclature partially solves inconsistency of bloating a point that remains a point.
Check that I got sin/cos right everywhere it is used and not cos/sin (ie accidentally rotated)
~~Find out what is the preferred stack order for subtract, and if I need to change it, do it everywhere! (I.e Push(A); Push(B); Subtract() - is that A-B or B-A?)~~
Redo hatching examples in light of working Combine() call...
probably better curve fitting: https://www.jointjs.com/blog/how-to-create-nice-looking-curves-in-svg-with-fixed-tangents. Also Smooth Bézier Spline Through Prescribed Points. Since writing this page I've seen a few different ways of fitting curves to points - my own hack implemented in this package is one of the poortest choices. (I think my solution may have been an unwitting reinvention of Catmull-Rom splines! By the way, we did quite a lot of experimentation on fitting curves to points at the MIT 'Scratch' site)
If I flatten curves with straight line segments in order to do polygon operations on curves using an underlying package that only works with straight lines, I will need code that takes the results of those operations and 'unflattens' the resulting polygons back into Bézier curves. I do have a crude prototype of exactly this, in unflatten.c which does work, but the overhead is quite high and with the current code I feel that this mechanism isn't practical within reasonable CPU times.

Graham Toal <gtoal@gtoal.com>

A Polygon Library

Table of Contents

A short note on reading this manual on the web vs on paper