[geos-devel] Writing a wrapper around LibGEOS

[Graham Toal]

On Mon, Jan 30, 2023 at 9:09 AM Regina Obe <lr at pcorp.us> wrote:

> Nyall,
>
> Thanks for the input.  I got to check out QGIS more closely with PostGIS
> curved geometries.  I admit to being a closeted Server/Database Admin
> person, not paying much attention to UIs beyond pgAdmin.  It's good to know
> there is so much interest in curves in the GIS community.
>

I'ld like to follow up on these comments from a month or two back.  I've
been looking into the use of curves in polygon operations a bit since then,
for my own purposes. Here's what I've learned.

Most packages use quadratic and cubic Beziers as their basic primitive, but
not higher orders.  More complex curves are usually approximated by
stitching together cubic curves into a path.

Quadratic curves can be easily converted into cubic curves if you don't
want to duplicate code by implementing both quadratic and cubic curves
everywhere.  Some operations that are mathematically exact when done with
quadratic curves cannot be done exactly with cubic curves.

Several operations on cubic curves cannot be done mathematically exactly,
*but* the approximations available are so close that they are acceptable in
almost all real-world circumstances.

Circles and arcs can be represented very accurately by Bezier
approximations.  Consequently so can ellipses.

Any single Bezier curve can be easily split into two adjoining Bezier
curves.

Flattening a curve to line segments (or even individual pixels on a raster
display) is trivial.  Reversing a flattened curve, even after
transformations and clipping, back to its Bezier representation, is
doable.  But most (not all) transformations can be done simply by
transforming the Bezier control points.  The main exception is offsetting,
where the exact mathematical solution is not tractable, but very good
approximations are available.

All the polygon and geometry operations that we do with line segments are
doable with curves.  Any that cannot be done optimally at a high level can
be approximated by flattening the curve to line segments and unflattening
the results back to Beziers.

Just about every operation that GEOS might need to implement in order to
add curves is well documented and implementations exist, although commonly
in Javascript rather than C or C++ - the packages paper.js and bezierjs are
two very good places to start.
http://paperjs.org/ and http://pomax.github.io/bezierjs/ (or WIP
https://pomax.github.io/BezierInfo-2/ ) I have bookmarks now for a *lot* of
other relevant pages.

The two packages above go hand-in-hand with SVG graphics but are not
synonymous with SVG.  Most (if not all - I haven't found a counterexample
yet) SVG implementations delay many of their operations until they get to
the bitmap rendering stage - a good polygon package ought to be able to do
everything that supports SVG but at the data structure level.

For the moment, for my own benefit, I've added loading and saving of SVG
files to the interface layer that I've built on top of LibGEOS.

What I am currently working on is a hack to add curves to GEOS - I will
flatten any curves from SVG paths on loading, work with the large
straight-line paths using GEOS, but reconstitute and write out Bezier
curves from the results as I save back to SVG files.  (I've got
proof-of-concept code for the re-constitution of Bezier curves from
flattened paths but have not yet built that back into SVG data
structures).  My hope is that if I can get a demonstration working of a
GEOS with curves by using this approximation, it might serve as a starting
point for adding curves (and the corresponding operations) to GEOS properly
within the data structure.

regards,

Graham
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/geos-devel/attachments/20230305/8bf9d4a0/attachment.htm>