Comprehensive feature wishlist / brain dump.

[lemmih]

Algorithms:

• [ ] Pick random point in triangulated polygon. O(n).
• [ ] Build a mass-balanced triangle tree such that a random polygon point can be sampled in O(log n).
• [ ] kernel :: SimplePolygon p r -> Maybe (ConvexPolygon p r) in O(n). See: http://www.dtic.mil/get-tr-doc/pdf?AD=ADA056887
• [x] convexPolygon :: Polygon t p r -> ConvexPolygon p r in O(n). Implemented in #84
• [x] diameter :: ConvexPolygon p r -> r in O(n). Implemented in #83
• [x] diameter :: [Point 2 r :+ p] -> r in O(n log n). Implemented in #86
• [x] Convex.extremes in O(log n) rather than O(log^2 n). Implemented in #69
• [x] Single-source shortest path in O(n) with triangulation. Implemented in #64
• [ ] Single-source shortest path in O(n) with triangulation from an interior point.
• [x] O(log n) time inConvex. Implemented in #76
• [ ] approxDiameter :: [Point 2 r :+ p] -> r in O(n) using principal-axis.
• [x] Planar point location in O(log n).
• [ ] O(n log n + k) line segment intersections. See: https://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=87F4974EC77559D6486C8D9DBDF96A35?doi=10.1.1.460.7188&rep=rep1&type=pdf See: https://sci-hub.do/10.1016/S0747-7171(08)80064-8
• [ ] Bichromatic Closest Pair approximation in O(n). See: https://www.cs.umd.edu/~samir/grant/cp.pdf
• [ ] Straight skeletons. See: http://www.cs.ust.hk/~scheng/pub/motorpub.pdf See: http://www.cs.umanitoba.ca/~cccg2010/electronicProceedings/paper15.pdf See: https://www.sthu.org/research/publications/files/HuHe11.pdf
• [ ] #204 Greiner–Hormann O(nm): http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.703.8012&rep=rep1&type=pdf Improved algorithm: https://sci-hub.do/10.1016/j.cagx.2019.100007 C++ implementation: https://www.inf.usi.ch/hormann/polyclip/ O((n+k) log n): https://sci-hub.do/10.1016/j.advengsoft.2013.04.004 Public Domain C++ implementation: http://www4.ujaen.es/~fmartin/bool_op.html Simplex algorithm: https://hal.inria.fr/inria-00517670/document
• [ ] Shortest path in O(n log n). See An Optimal Algorithm for Euclidean Shortest Paths in the Plane.
• [ ] Visibility polygon in O(n) without triangulation (SimplePolygon only).
• [ ] Visibility polygon in O(n^2) using ray-casting.
• [x] Visibility polygon in O(n log n) using a sweepline algorithm (any polygon). Implemented in #62
• [ ] Visibility polygon from edge in O(n) with SSSP tree (SimplePolygon only).
• [ ] Visibility polygon from edge in O(n) with triangulation (new research from Frank Staals).
• [ ] Visibility polygon from chord in O(n) with triangulation.
• [ ] Visibility polygon from point in O(n) with SSSP tree (SimplePolygon only).
• [ ] Visibility polygon from point in O(k) with triangulation where k is the number of intersected triangles.
• [x] Output sensitive triangulation dual in O(k).
• [ ] Visibility window tree in O(n).
• [ ] ConvexPolygon intersection test in O(log n + log m). See: https://arxiv.org/pdf/1312.1001.pdf
• [ ] Optimal Convex Decomposition in O(nr^2).
• [ ] Approximate Convex Decomposition in O(nr). Approximate Convex Decomposition of Polygons
• [ ] Approximate Convex Decomposition in O(n) with the Hertel/Mehlhorn algorithm. https://core.ac.uk/download/pdf/82318242.pdf http://www.dma.fi.upm.es/recursos/aplicaciones/geometria_computacional_y_grafos/web/piezas_convexas https://doc.cgal.org/latest/Minkowski_sum_2/classCGAL_1_1Hertel__Mehlhorn__convex__decomposition__2.html
• [ ] Connect polygon holes by vector (with steiner points).
• [ ] Connect polygon holes with triangulation (without steiner points).
• [ ] Connect polygon holes by shortest cuts (without steiner points).
• [ ] Constrained Delaunay Triangulation in O(n log n). Constrained Delaunay Triangulations https://hal.inria.fr/inria-00073390/document https://people.eecs.berkeley.edu/~jrs/papers/inccdtj.pdf
• [ ] Randomised Linear Triangulation in O(n). See: https://www.ics.uci.edu/~goodrich/pubs/dcg-tri.pdf
• [ ] Randomised Near-Linear Triangulation in O(n log* n). See: http://www.cs.unc.edu/~dm/CODE/GEM/chapter.html
• [x] Polygonization: Generate monotone simple polygons in O(n log n).
• [ ] Polygonization: Connect random points with a graham scan in O(n log n). Yields star-skeleton polygons?
• [ ] Polygonization: Grow polygons by attaching a new shape on a random edge and checking for self-intersections.
• [ ] Polygonization: Create holes by shrinking according to the straight skeleton.
• [ ] Polygonization: 2-Opt Moves, Steady Growth 2, Space Partitioning. See: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.47.6026&rep=rep1&type=pdf See: http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=2C714D59DF41A9C315CE238B437A0F38?doi=10.1.1.18.5963&rep=rep1&type=pdf
• Polygon morphing:
  • [ ] Linear interpolation.
  • [ ] Angular interpolation.
  • [ ] Edge+angle interpolation. An intrinsic solution to the vertex path problem (1993)
  • [ ] Least-work linear interpolation. A physically based approach to 2-D shape blending (1992)
  • [ ] Star-Skeleton. Shape Blending Using the Star-Skeleton Representation (1995)
  • [ ] As-rigid-as-possible. As-rigid-as-possible shape interpolation (2000)
  • [ ] Guaranteed intersection-free. Guaranteed Intersection-Free Polygon Morphing (2001)

Infrastructure:

• [x] Arbitrary instance for SimplePolygon and MultiPolygon. Implemented in #51
• [x] Implement shrink by cutting away reflex vertices. Implemented in #64
• [x] Arbitrary instance for ConvexPolygon. Generate true random convex polygons. Implemented in #73 https://cglab.ca/~sander/misc/ConvexGeneration/convex.html
• [x] API coverage badge in README. Implemented in #59
• [ ] 100% Haddock coverage of API. Currently at ~~69%~~ ~~71%~~ ~~77%~~ ~~80%~~ 83%. Progress list: https://github.com/noinia/hgeometry/blob/docs/docs/haddock.txt
• [ ] Graphical unit tests that can be easily verified by both humans and machines.

Test properties:

• [x] read . show == id for Point. Implemented in #64
• [x] read . show == id for Vector.
• [ ] read . show == id for RealNumber. Add QC tests.
• [x] read . show == id for SimplePolygon and MultiPolygon. Implemented in #51
• [ ] area p == area (connectHoles p)
• [ ] connectHoles p doesn't add any self-intersections. Check with BentleyOttmann in O(n log n).
• [x] area p == sum (map area (triangulate p)) Implemented in #51
• [ ] area p <= area (convexHull p)
• [x] extremes == extremesLinear. Implemented in #69

Library:

• [ ] Don't use CircularSeq in Algorithms.Geometry.Tangents.Tangents.
• [ ] Implement Data.Ext as a zero cost type family.
• [x] Inforced CCW vertex order in all polygons. Implemented in #52
• [x] O(1) vertex indexing in SimplePolygon. Implemented in #53
• [ ] O(1) vertex indexing in MultiPolygon.
• [x] Safe constructor for SimplePolygon. Implemented in #74
• [x] Consistent Big-O notation. Implemented in #82
• [ ] Bezier curve intersection. See bezier clipping and De Casteljau's algorithm. Copy code (BSD3) from cubicbezier. Finding exact intersections is hard. This is how they do it in CGAL: http://acg.cs.tau.ac.il/copy_of_projects/in-house-projects/arrangements-of-bezier-curves/p253-hanniel.pdf This way may be easier: https://cs.nyu.edu/exact/doc/subdiv1.pdf Geez, bezier intersection is hard: https://arxiv.org/pdf/2009.00811.pdf Bezier intersection is way too difficult. Much easier to linearise the curves and use normal line-segment intersection.
• [ ] Bezier boolean operations: union, intersection, difference, exclusion.
• [ ] Read/Write support for mesh file-formats. See meshio. Hm, maybe we only need support for WKT.

Branding:

• [x] hgeometry organization.
• [x] website on hgeometry.github.io and hgeometry.org/.com.
• [ ] Benchmark against CGAL.

Incredible overview of Computation Geometry: Visibility Algorithms In The Plane

Another good overview: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.48.2190&rep=rep1&type=pdf

Overview of intersection algorithms: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.63.2041&rep=rep1&type=pdf

Handbook of Discrete and Computational Geometry: http://www.csun.edu/~ctoth/Handbook/HDCG3.html

PhD about numerical errors: https://tel.archives-ouvertes.fr/tel-03116750/document

[noinia]

That seems like a pretty nice TODO list :).

With respect to the 'isCounterClockwiseOrder':

• I wonder if we should just 'normalize' the orientation of the vertices. i.e. keep as an invariant that the vertices are always in, say CCW, order.

edit: Hmm, if we want to enforce that using s.t. like a smart constructor that actually seems to force Eq r and Fractional r constraints on us. That does not seem very nice.

Somewhat related to this. I've actually been wondering if I should have used an Array/Vector to store the vertices instead of an (Circular) Sequence. That would allow us O(1) time indexing (instead of the O(log n) we currently have). We do "lose" persistence. But my impression is that most of the time we use polygons in a read-only setting anyway. Any opinions on this?

With respect to approximate convex subdivion:

• There is a very easy 4 approximation algorithm: for every reflex vertex v, let u be one of its incident vertices, and let T be the triangle incient to v that intersects the line through u and v. Now pick both diagonals bounding T to split the polygon (and do this for every reflex vertex). This gives a set of 2r splitting dagionals in total, Since any convex subdivision has size at least r/2 (i.e. at best we can connect two reflex vertices) this is a 4 approximation.

I'll try to implement/add something like that this weekend :).

• For the visibility polygon algorithm: Indeed O(n) time in simple polygons is nice (but if I recall the algorithm to do that is somewhat finnicky). There is also a fairly simple O(n log n) time sweepline algorithm that even works in polygons with holes (rotate a half-line around the query point ; maintain the edges intersected by the line in a BST) that would be nice to implement/add :)

[noinia]

For prosterity let me also add here: I've been working on implementing an O(n log n) time algorithm to compute the convex hull of a set of points in R^3. This would also give O(n log n) time algorithms for e.g. Voronoi diagram and Delaunay Triangulation. The implementation in hgeometry-devel seems to work, but it doesn't really like degenerate inputs (i.e. 4 coplanar points).

To better deal with degeneracies I've (partially) implemented 'Simulation of Simplicity': a generic way of dealing with degeneracies. I haven't fully integrated that with the rest of the library yet. (Essentially, this mechanism would replace some of the basic primitives that we are currently using, e.g. to check if 3 points make a CCW or CW turn, to compute intersections etc). When I have some free time again I hope to continue that work.

[lemmih]

With respect to the 'isCounterClockwiseOrder':

* I wonder if we should just 'normalize' the orientation of the vertices. i.e. keep as an invariant that the vertices are always in, say CCW, order.

edit: Hmm, if we want to enforce that using s.t. like a smart constructor that actually seems to force Eq r and Fractional r constraints on us. That does not seem very nice.

We could simplify the constraint to Eq r and Num r. Would that be acceptable? I'm having a hard time thinking of polygons with points that aren't numbers and do not have equality tests. Maintaining a CCW invariant on all polygons would be a big win from my point of view.

[lemmih]

Somewhat related to this. I've actually been wondering if I should have used an Array/Vector to store the vertices instead of an (Circular) Sequence. That would allow us O(1) time indexing (instead of the O(log n) we currently have). We do "lose" persistence. But my impression is that most of the time we use polygons in a read-only setting anyway. Any opinions on this?

Completely in favor of this. I can draft a PR so we can see if there are unexpected consequences.

[noinia]

We could simplify the constraint to Eq r and Num r. Would that be acceptable? I'm having a hard time thinking of polygons with points that aren't numbers and do not have equality tests. Maintaining a CCW invariant on all polygons would be a big win from my point of view.

Ah well spotted that we can simplify the constraint to (Num r, Eq r) instead. I think I can indeed live with those constraints, and I think having a CCW invariant would indeed be worth that.

To support O(1) indexing in polygons with holes we also need to store slightly more information about holes (some cumulative number of vertices on all holes 'up to hole h'). Therefore, I think we should refactor things to make SimplePolygon/Polygon an opaque type, and have smart constructors that guarantee those constraints (and some pattern synonyms to get some sort of backward compatibility).

[lemmih]

To support O(1) indexing in polygons with holes we also need to store slightly more information about holes (some cumulative number of vertices on all holes 'up to hole h'). Therefore, I think we should refactor things to make SimplePolygon/Polygon an opaque type, and have smart constructors that guarantee those constraints (and some pattern synonyms to get some sort of backward compatibility).

Do we need O(1) indexing of all vertices? I would have thought that O(1) indexing of the boundary vertices and for any given hole would be sufficient for all purposes.

[lemmih]

There is also a fairly simple O(n log n) time sweepline algorithm that even works in polygons with holes (rotate a half-line around the query point ; maintain the edges intersected by the line in a BST) that would be nice to implement/add :)

Tetsuo Asano's algorithm, right? I've looked and looked and I cannot find a copy of his 1983 article. Is his algorithm described in detail somewhere online?

[noinia]

To support O(1) indexing in polygons with holes we also need to store slightly more information about holes (some cumulative number of vertices on all holes 'up to hole h'). Therefore, I think we should refactor things to make SimplePolygon/Polygon an opaque type, and have smart constructors that guarantee those constraints (and some pattern synonyms to get some sort of backward compatibility).

Do we need O(1) indexing of all vertices? I would have thought that O(1) indexing of the boundary vertices and for any given hole would be sufficient for all purposes.

Well, in the current sitatuation if you have a polygon with many, say \Omega(n) holes, and you ask for "give me information about vertex i" which is some vertex of a hole (but you don't really know which one) that would take O(n) time. With slightly more information we can make that O(1). That seems like a useful thing to have. Especially if we are currently fiddling with the definition of Polygon anyway.

[noinia]

There is also a fairly simple O(n log n) time sweepline algorithm that even works in polygons with holes (rotate a half-line around the query point ; maintain the edges intersected by the line in a BST) that would be nice to implement/add :)

Tetsuo Asano's algorithm, right? I've looked and looked and I cannot find a copy of his 1983 article. Is his algorithm described in detail somewhere online?

Yes. It's a very basic sweepline algorithm, so it appears in basic textbooks about computational geometry, e.g. Computational Geometry: Theory and Applications, but probably not in other printed articles.

[noinia]

There is also a fairly simple O(n log n) time sweepline algorithm that even works in polygons with holes (rotate a half-line around the query point ; maintain the edges intersected by the line in a BST) that would be nice to implement/add :)

Tetsuo Asano's algorithm, right? I've looked and looked and I cannot find a copy of his 1983 article. Is his algorithm described in detail somewhere online?

Yes. It's a very basic sweepline algorithm, so it appears in basic textbooks about computational geometry, e.g. Computational Geometry: Theory and Applications, but probably not in other printed articles.

Rather than describing the algorithm I just ended up implementing a large part of it just now. See #62

[noinia]

I've opened up a separate issue (#71) to discuss things related to visual unit tests and debugging.

In terms of features I think there are also some low hanging fruits like:

• [ ] add a concrete implementation of a segment tree storing 2D line segments (currently there is some generic SegmentTree module supporting monoidal annotations. Should be fairly easy to get that into something actually workable)
• [x] planar point location. Either using the segment tree or by a persistent sweep. I think I even partially implemented the planar sweep in some file in the repo already.
• [x] O(log n) time pointInConvexPolygon

[noinia]

By the way; for visibilityPolygon from edge: me and some collegues are working on a very simple O(n) time algorithm in triangulated polygons. One of our students implemented it in C++, and it seems it is alsmost as fast as visibility-polygon from a point. We should hopefully be able to make that writeup public soon. We can then also implement it in HGeometry :)

[lemmih]

Exciting. HGeometry might get a cutting edge algorithm before CGAL.

[lemmih]

In terms of features I think there are also some low hanging fruits like:

* [ ]  add a concrete implementation of a segment tree storing 2D line segments (currently there is some generic SegmentTree module supporting monoidal annotations. Should be fairly easy to get that into something actually workable)

* [ ]  planar point location. Either using the segment tree or by a persistent sweep. I think I even partially implemented the planar sweep in some file in the repo already.

I don't understand what these two mean. Do you have links to papers or articles that explain the algorithms/problems?

[noinia]

In terms of features I think there are also some low hanging fruits like:

* [ ]  add a concrete implementation of a segment tree storing 2D line segments (currently there is some generic SegmentTree module supporting monoidal annotations. Should be fairly easy to get that into something actually workable)

* [ ]  planar point location. Either using the segment tree or by a persistent sweep. I think I even partially implemented the planar sweep in some file in the repo already.

I don't understand what these two mean. Do you have links to papers or articles that explain the algorithms/problems?

For the first one; segment trees solve the following problem: given a set of disjoint segments in the plane, store them in a data structure such that given a vertical query segment Q, we can quickly report the segments intersected by Q. See for example slide 27-and onwards of these slides. Segment trees use O(n log n) space, and support such queries in O(log^2 n + k) time. (or even O(log n) using some additional tricks)

For the second one: The problem is given a planar subdivison, store it such that given an arbitrary query point q \in R^2, we can find the face containing q. This problem is equivalent to vertical ray shooting: i.e. given q find the first edge vertically above q. (our planar Subdivision data structure then allows us to "retrieve" the face from that edge/line segment in constant time.)

To solve vertical ray shooting there are two options:

a) store the edges (= line segments) in a segment tree. (The segment-tree can report this edge in O(log n) time.) b) plane sweep with a partially-persistent BST: sweep a vertical line over the plane, while maintaining the edges that are currently intersected by the vertical line (in the order in which the segments intersect the sweep line). To answer a query: find (using a binary search) the version of the BST (a Data.Set) that corresponds to the "time" at which the sweep line was at x-coordinate q_x, now do another binary search to find the segment directly above q. It seems I already partially implemented this in https://github.com/noinia/hgeometry/blob/master/hgeometry/src/Algorithms/Geometry/PointLocation/PersistentSweep.hs

More low-hanging fruit would be Voronoi diagrams; since we already have the delaunay triangulation, we can convert it into a Voronoi diagram in linear time. I also already partially implemented that in https://github.com/noinia/hgeometry/blob/master/hgeometry/src/Algorithms/Geometry/VoronoiDiagram/DualDT.hs Too many interesting things to think about/try that I sometimes end up starting on something and not finishing it properly.

[mrehayden1]

Here's an updated link to the Greiner-Hormann paper: https://www.inf.usi.ch/hormann/papers/Greiner.1998.ECO.pdf