jbuckmccready / cavalier_contours

2D polyline/shape library for offsetting, combining, etc.
Apache License 2.0
144 stars 12 forks source link

Review intersect functions to minimize error and maximize consistency #21

Open jbuckmccready opened 2 years ago

jbuckmccready commented 2 years ago

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

jbuckmccready commented 2 years ago

These issues have actually manifested in reported issue https://github.com/jbuckmccready/cavalier_contours/issues/23 - commits and improvements are ongoing.