2D polyline/shape library for offsetting, combining, etc.

Hello! Ive created this test vector:

"Vector, nodes 4, closed=1"
"    Node 0 : X=155.575   Y=113.665   B=0"
"    Node 1 : X=161.29   Y=113.665   B=1"
"    Node 2 : X=161.29   Y=114.935   B=0"
"    Node 3 : X=155.575   Y=114.935   B=1"
"Vector, nodes 4, closed=1"
"    Node 0 : X=161.29   Y=113.665   B=0"
"    Node 1 : X=167.64   Y=113.665   B=1"
"    Node 2 : X=167.64   Y=114.935   B=0"
"    Node 3 : X=161.29   Y=114.935   B=1"

Basically it is 2 horisontal lines: second one starts at same point, where first ends (X=161.290 Y=114.300)

I use this C function:

cavc_pline_boolean(scene[countur_in_scene_num], countur2, cavc_booleanOp_And, combine_options, &pos_list, &neg_list);

Could you please take a look on it?

https://user-images.githubusercontent.com/19372111/122493643-a4f24500-d01a-11eb-97f8-f2e26873c0cd.mp4

This polyline cannot be offset outside

{"vertexes":[[0,0,2.9239855509708432],[422.7001801508977,-2181.678349165927,0.21373279590439873],[1217.850643134374,-1733.2038795014323,4.472986753391631],[961.0754444813574,-155.87051634718955,0.22947158823257166]],"isClosed":true}

More benchmarks should be added for the core polyline functions:

• Polyline path length
• Polyline parallel offset
• Polyline winding number These benchmarks can be added to cavalier_contours/benches/benches.rs.

More polylines (capturing different characteristics, e.g. polyline with lots of lines, polyline with lots of arcs, polyline when offset that has many self intersects, polyline when offset that has very little self intersects, etc.) should be added and available for the benchmarks as well. These can be added to cavalier_contours/benches/test_polylines.rs.

As things grow it may make sense to create another crate in the workspace that has all the characteristic polylines we want to add for testing so it may be accessed from the other crates (test_suite, etc.).

{"vertexes":[[0,0,0],[0,-882.3073569599583,0.19403531582953024],[30.99567883971031,-942.6919889602286,0.1940353158226031],[0,-1003.0766209573267,0],[0,-1880,0],[4,-1880,0],[4,-1003.2606547873729,-0.19502429444774674],[34.00003211540752,-945.3840053746535,-0.19502429171847763],[64,-1003.2606547872638,0],[64,-1880,0],[68,-1880,0],[68,-1003.0766209572321,0.1940353134888888],[37.00432115854346,-942.6919889585697,0.194035313489369],[68,-882.3073569597691,0],[68,0,0],[64,0,0],[64,-882.1233231297883,-0.19502431066879408],[33.999968577962136,-939.9999731353018,-0.19502429444816094],[4,-882.1233231296792,0],[4,0,0]],"isClosed":true}

If it can be improved better, it doesn't matter if it can't be improved

Feel free to close immediately, I didn't search if the bug was already submitted.

I just played with the web version of CavalierContours and found a failing test:

(80.0, 90.0, 0.374794619217547),
(231.5, -278.0, 0.0),
(230.0, 0.0, 1.0),
(320.0, 0.0, -0.5),
(280.0, 0.0, 0.5),
(390.0, 210.0, 0.0),
(280.0, 120.0, 0.5)], 3.0) =>
                    [PlineProperties::new(11, 0.0, 1563.689560505266, 66.99239238371496, -273.0909692941639, 401.41586988912127, 205.22199935960901)]

with mode Offset , Offset 3, Offset count 50, Handle Self Intersects activated.

Thanks for offering this project!

The functions in circle_circle_intersect.rs, line_circle_intersect.rs, line_line_intersect.rs, under cavalier_contours/core/math and cavalier_contours/polyline/pline_seg_intersect.rs need code examples added to their documentation. E.g. circle_circle_intr just has /// Finds the intersects between two circles.

Add more documentation about their parameters, and add a basic code example similar to what is done for the functions in the cavalier_contours/polyline/pline_seg.rs module.

• Finish adding functions to handle open polylines and self intersecting polylines with dual offset slicing.
• Finalize option structure for passing in epsilon values and any other parameters.

In case of segments not intersecting but close enough (in pos_equal_eps box) there will be incorrect behavior. If bound boxes isn't overlap but segments intrsects. For examle: 2 perpendicular segments * | | * ------- with distance between less than pos_equal_eps but greter than T::epsilon() In that case should be intersection but it won't

It is possible for arc overlap intersection to not be detected but other intersections are, this causes problems in boolean operation between polylines.

Original issue with test cases here: https://github.com/jbuckmccready/CavalierContours/issues/48

How should epsilon/tolerance values be specified? There can be multiple epsilon values within an algorithm each of which may use different values (e.g. epsilon used or determining if two points overlap may be different than the epsilon used for fuzzy comparing in a distance check).

Currently in C++ they are just hard coded constants but it would be good to have them as part of the API with easy to use sensible defaults.

Currently I think all epsilon values should be explicitly passed to functions and have them be bundled inside of an options struct. The options struct then implements the Default trait with sensible default values, from the consuming side then specific epsilon values (or other option fields) could be changed from the default.

The main intersect functions line_line_intr, line_circle_intr, circle_circle_intr, and pline_seg_intr all use a fuzzy epsilon value for float comparisons. These functions should be reviewed for improvement in quality (reducing error) and consistency (they should agree in as many cases as possible when given the same epsilon value).

Background:

The epsilon value is used to prevent pathological problems (e.g., when two lines are almost parallel they should just be treated as parallel due to limited precision of floats), and also makes results fuzzy/sticky (e.g., if the end of a line segment very nearly touches a circle it should be treated as an intersect).

This is required for geometric consistency in intersect detection within algorithms. E.g., if we parallel offset a line by x and then by -x and find intersects with the original input we expect the result to be overlapping (even the line may not be exactly the same due to error propagation through floating point arithmetic in the offset operation).

Some recent commits that attempt to patch some issues relating to intersect consistency and errors: https://github.com/jbuckmccready/cavalier_contours/commit/e6a598ff5e0ef7ef418754b17c39cb96ba0c1b85 https://github.com/jbuckmccready/cavalier_contours/commit/1a40c08a2a23f18969e9b77c2976e244fea473d1 https://github.com/jbuckmccready/cavalier_contours/commit/f712458c6aa9fb13d6f7b01a13e159c0680f856a

I posted this question at the C++ issue tracker-- I'm not sure whether this or that place is the right place to post. Anyway feel free to close the one that is not relevant.

The question is this: Is there any plan to support variable offsets? Something like NetTopologySuite VariableBuffer. Currently only uniform offset can be done throughout all the vertexes on the polylines.

Currently all overlapping results are kept (purposefully) by the polyline offset function. There could be an option to toggle this behavior to discard them rather than keep them.

Currently it's assumed all bulge values are between -1 and 1 (this ensures the chord is always the line between the vertexes). If an arc is greater than a half circle it must be split into two segments.

The different polyline operations need to be reviewed for what the consequences would be to support larger bulge values. Original issue reporting bug: https://github.com/jbuckmccready/cavalier_contours/issues/13.

Currently segments are always joined with an arc when needed (to maintain constant offset distance from original input).

It's common in graphics libraries to offer other join types, e.g. see Microsoft documentation on the Shape.StrokeLineJoin Property here: https://docs.microsoft.com/en-us/dotnet/api/system.windows.shapes.shape.strokelinejoin?view=net-5.0

It may be possible add a miter and/or bevel join option to the parallel offset algorithm, need to investigate if it conflicts with the way offset slice pruning is performed.