Functionality Todo List:

• [x] Add a function that checks whether entered points form a y-monotone polygon, return the paths if true
• [x] Add a function that takes number of points and arrange them into a y-monotone polygon
• [x] Make monotone generation generic for any axis or direction

Before Merging Todo List:

• [x] clean up code (extract large functions)
• [x] Add proper documentation to the functions
• [ ] Make sure all functionalities are covered by test cases

See https://github.com/svartalf/rust-claim/issues/9

This makes it impossible to use rgeometry together with nix, for example, which I want to do.

A possible workaround for users is to patch the (seemingly unmaintained) dependency like this:

[patch.crates-io]
claim = { git = "https://github.com/Turbo87/rust-claim.git", rev = "23892a3" }

CGAL has a kernel called Exact_predicates_inexact_constructions_kernel. This kernel uses f64 under the hood but switches to exact numbers when using f64 directly would give inaccurate results. This is slower than naively using f64 but guarantees correctness. RGeometry should do this by default and expose a separate type (maybe UnstableF64) for use when performance is more important than correctness.

Note, fixed-precision numbers from the fixed crate are still to be preferred.

This would force a dependency on num-rational.

get_visibility_polygon sometimes crashes with Point<f64> due to floating point error. With Point<f64>, return value from get_intersaction might be a little closer or further than original vertex when intersection result is Crossing, which results in invalid polygon_points and crash.

references

• DT: https://www.personal.psu.edu/cxc11/AERSP560/DELAUNEY/13_Two_algorithms_Delauney.pdf
• CDT: https://people.eecs.berkeley.edu/~jrs/papers/inccdtj.pdf

Introduction

Boolean operations on polygons are a set of Boolean operations (AND, OR, NOT, XOR, ...) operating on one or more sets of polygons in computer graphics. These sets of operations are widely used in computer graphics, CAD, and in EDA (in integrated circuit physical design and verification software).

Paper abstract:

In this paper a simple and efficient algorithm for computing Boolean operations on polygons is presented. The algorithm works with almost any kind of input polygons: concave polygons, polygons with holes, several contours and self-intersecting edges. Important topological information, as the holes of the result polygon, is computed.

Paper: https://www.sciencedirect.com/science/article/abs/pii/S0965997813000379?via%3Dihub Paper: https://www.inf.usi.ch/hormann/papers/Foster.2019.CSP.pdf Wikipedia: https://en.wikipedia.org/wiki/Boolean_operations_on_polygons

The algorithm from either paper is acceptable.

Testable properties

• For point P and polygons A and B,
  • If P is in A∪B then it must be in A or B.
  • If P is in A∩B then it must be in A and B.
  • If P is in A\B then it must be in A and not in B.
• The area of A∪B is:
  • Greater or equal to the area of A.
  • Greater or equal to the area of B.
  • Less than or equal to the area of A + the area of B.
• The area of A∩B is:
  • Less than or equal to the area of A.
  • Less than or equal to the area of B.
• The area of A\B is:
  • Less than or equal to the area of A.
• The output polygons may not be degenerate.
• The output polygons may touch but may not overlap.

Bounty

50 USDC for algorithm that satisfies the above properties.

Introduction

A constrained Delaunay triangulation is a generalization of the Delaunay triangulation that forces certain required segments into the triangulation as edges, unlike the Delaunay triangulation itself which is based purely on the position of a given set of vertices without regard to how they should be connected by edges. It can be computed efficiently and has applications in geographic information systems and in mesh generation.

Wikipedia: https://en.wikipedia.org/wiki/Constrained_Delaunay_triangulation Paper: https://dl.acm.org/doi/10.1080/13658810701492241

Testable properties

• The sum of the triangulated areas is equal to the area of the polygon.
• No two triangles overlap.
• All polygon vertices must appear at least once in triangulation.
• All of the triangles obey the Delaunay condition.

Bounty

50 USDC for algorithm that satisfies the above properties.

Introduction

From the referenced paper:

We describe a randomized algorithm for computing the trapezoidal decomposition of a simple polygon. Its expected running time is linear in the size of the polygon. By a well-known and simple linear time reduction, this implies a linear time algorithm for triangulating a simple polygon.

Paper: https://www.ics.uci.edu/~goodrich/pubs/dcg-tri.pdf

Testable properties

• The sum of the triangulated areas is equal to the area of the polygon.
• No two triangles overlap.
• All polygon vertices must appear at least once in triangulation.

Bounty

50 USDC for algorithm that satisfies the above properties.

Introduction

Polygon triangulation is the partition of a polygon P into a set of triangles, i.e., finding a set of triangles with pairwise non-intersecting interiors whose union is P.

A polygon can be decomposed into trapezoidal parts in O(n log* n) time. These trapezoidal parts can then be triangulated in linear time.

Wikipedia: https://en.wikipedia.org/wiki/Polygon_triangulation#Computational_complexity Paper: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.472.6973&rep=rep1&type=pdf

Testable properties

• The sum of the triangulated areas is equal to the area of the polygon.
• No two triangles overlap.
• All polygon vertices must appear at least once in triangulation.

Bounty

50 USDC for algorithm that satisfies the above properties.

Introduction

Polygon triangulation is the partition of a polygon P into a set of triangles, i.e., finding a set of triangles with pairwise non-intersecting interiors whose union is P.

Monotone polygons can be trivially triangulated and it is possible to decompose a polygon into monotone parts in O(n log n) time. Thus, one can triangulate a polygon by splitting it into monotone parts and then triangulating each part separately.

Wikipedia: https://en.wikipedia.org/wiki/Polygon_triangulation#Monotone_polygon_triangulation Paper: https://www.ibr.cs.tu-bs.de/courses/ws2021/ag/Papers/Ch5/Garey-etal_Triangulating_1978.pdf

Testable properties

• The sum of the triangulated areas is equal to the area of the polygon.
• No two triangles overlap.
• All polygon vertices must appear at least once in triangulation.

Bounty

50 USDC for algorithm that satisfies the above properties.