Potential geometry things to add

[Chillee]

I'd like to cram as much geometry as possible into KACTL. Perhaps not necessarily included by default, but some of these things would be nice to have. Taking lots of these from https://github.com/spaghetti-source/algorithm/tree/master/geometry

• [ ] O(N^2 log N) circle union (xyz)
• [x] Area of circle intersection (xyz, viet, spaghetti)
• [x] Manhattan MST (issue exists here: https://github.com/kth-competitive-programming/kactl/issues/10), implementation here: https://github.com/spaghetti-source/algorithm/blob/master/geometry/rectilinear_mst.cc#L105
• [ ] Polygon triangulation
• [ ] Tangent circles (given 2 lines find the circles of radius r that touch those lines)
• [ ] Maximum circle cover (find circle of radius r that covers as many points as possible)
• [x] number of lattice points below a line.
• [ ] construct visibility graph in O(points^2 * obstacles)
• [ ] Maximum area of empty convex k-gon (given a set of points)
• [x] test whether two polygons are congruent/similar (easy enough if you know the idea).
• [ ] tangent from point to convex polygon (apparently at WF ICPC 2016?)
• [ ] Minkowski Sum

[simonlindholm]

This a nice goal.

number of lattice points below a line.

We sort of have this in the number theory chapter (modsum).

[hockyy]

Might be useful: https://github.com/hockyy/kactl/blob/main/content/geometry/PolygonStab.h https://github.com/hockyy/kactl/blob/main/content/geometry/AllPairPolygonStab.h https://github.com/hockyy/kactl/blob/main/content/geometry/CircleCover.h https://github.com/hockyy/kactl/blob/main/content/geometry/Visualize.h https://github.com/hockyy/kactl/blob/main/content/geometry/onionDecomposition.h https://github.com/hockyy/kactl/blob/main/content/geometry/RotationalSwap.h https://github.com/hockyy/kactl/blob/main/content/geometry/PolygonCount.h https://github.com/hockyy/kactl/blob/main/content/geometry/PolygonTriangulation.h https://github.com/hockyy/kactl/blob/main/content/geometry/TriangleCount.h https://github.com/hockyy/kactl/blob/main/content/geometry/CircleUnion.h

[hockyy]

Tangent Circle Idea: Signature:

typedef pair<P, P> Line
// Returns the center of the tangent circle
P tangentCircle(Line a, Line b, double r) {
  P o = intersect(a, b);
  double agl = (b - o).angle() - (a - o).angle()
  // Normalize this
  if(agl > PI) agl = 2 * PI - agl;
  P middle = a; middle.rotate(agl);
  // If this method fails, lets just do (a - o).unit() + (b - o).unit()
  middle = middle.unit() * (r / sin(agl / 2));
  return middle;
}

• Find the intersection o, get the vector from o to a.fi, get the angle agl from a.fi to b.fi, the length from o to the circle's center is r / sin(agl / 2), get the vector in the middle of a.fi and b.fi from o, get the center