Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Potential geometry things to add #137

Open
4 of 12 tasks
Chillee opened this issue Nov 1, 2019 · 3 comments
Open
4 of 12 tasks

Potential geometry things to add #137

Chillee opened this issue Nov 1, 2019 · 3 comments
Labels

Comments

@Chillee
Copy link
Collaborator

Chillee commented Nov 1, 2019

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)
  • Area of circle intersection (xyz, viet, spaghetti)
  • Manhattan MST (issue exists here: Manhattan MST #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)
  • 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)
  • 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
Copy link
Member

This a nice goal.

number of lattice points below a line.

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

@hockyy
Copy link

hockyy commented Oct 17, 2023

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

3 participants