Question about the algorithm used in GEOS's buffer operation

[eagerbeaver04]

Hello! I am researching buffer algorithms for my thesis and would like to clarify which specific computational geometry methods are implemented in GEOS's BufferOp.

From the source code, I see that OffsetCurveBuilder and BufferSubgraph are involved, but I need a high-level description of the algorithm (e.g., Minkowski sum, offset curves with miters/bevels, etc.). Could you please:

• Confirm the core algorithm(s) used (e.g., based on winding numbers, offset curve approximation)?

• Recommend any papers or technical reports that describe GEOS's approach?

This would help me accurately reference the methodology in my work. Thank you for your time and for maintaining this critical library!

[dr-jts]

The buffer algorithm is a custom approach developed by me. It originally appeared in the JTS Topology Suite in 2001, and appeared to GEOS during the initial port of JTS in 2003.

The high level description is:

• A raw offset curve is generated for the input geometry, taking into account the various buffer parameters (buffer distance, quadrant segments (ii.e. join fillet quantization) join style, end cap style, etc.
• Some heuristics are used to reduce the number of self-intersections of the offset curve line (since a complex buffer can generate many self-intersections and cause slow performance)
• The raw offset curve is noded, preserving topological information about the left and right side of each noded line. This produces a fully-noded line arrangement of polygonal faces covering the generated buffer area.
• The topology faces are marked as inside or outside the buffer using the topological labelling on the edges.
• The interior faces are merged into one or more polygons which form the buffer.

Hope this helps. It would be nice if you provide a link to your thesis when it is published.

[eagerbeaver04]

Thank you so much for your detailed explanation! This is incredibly helpful for my thesis. I appreciate you taking the time to clarify the high-level approach and the steps involved in the buffer algorithm.

I will make sure to reference your work and the JTS/GEOS implementation in my thesis. Once it is published, I will gladly share a link with you.

Thank you again for your contribution to this field and for maintaining such a critical library!