Two circles intersect if, and only if, the distance between their centers is between the sum and the difference of their radii. Given two circles (x0, y0, R0) and (x1, y1, R1), the formula is as follows: ABS(R0 – R1) <= SQRT((x0 – x1)^2 + (y0 – y1)^2) <= (R0 + R1) Squaring both sides … Read more
Update in July 2016: Thanks to a number of volunteers (especially Nikolai Nowaczyk and I), there is now far more robust / correct code for handling Voronoi diagrams on the surface of a sphere in Python. This is officially available as scipy.spatial.SphericalVoronoi from version 0.18 of scipy onwards. There’s a working example of usage and … Read more
I solved the equations for you: k = ((y2-y1) * (x3-x1) – (x2-x1) * (y3-y1)) / ((y2-y1)^2 + (x2-x1)^2) x4 = x3 – k * (y2-y1) y4 = y3 + k * (x2-x1) Where ^2 means squared
One very simple option would be to use a standard algorithm for checking whether two line segments intersect to check whether the line segments intersects any of the four line segments that make up the corners of the box. It’s computationally very efficient to check if two line segments intersect, so I would expect that … Read more
I took @MitchWheat and @templatetypedef’s idea of sampling points on a circle and took it a bit farther. In my application I need to be able to control how weird the polygons are, ie start with regular polygons and as I crank up the parameters they get increasingly chaotic. The basic idea is as stated … Read more
You may organize your points in an Octree. Then you only need to search a small subset. A Octree is a fairly simple data structure you can implement yourself (which would be a valuable learning experience), or you may find some helpful libraries to get you going.
There is likely no solution to this problem that is significantly better than O(n^2) in a standard model of computation. The problem of finding three collinear points reduces to the problem of finding the line that goes through the most points, and finding three collinear points is 3SUM-hard, meaning that solving it in less than … Read more
The problem can be solved by finding a feasible point of a Linear Program. If you’re interested in the full details, as opposed to just plugging an LP into an existing solver, I’d recommend reading Chapter 11.4 in Boyd and Vandenberghe’s excellent book on convex optimization. Set A = (X[1] X[2] … X[n]), that is, … Read more
The key to solving this problem is first making an observation: the center of the largest circle that will fit inside an arbitrary polygon is the point that is: Inside the polygon; and Furthest from any point on the edges of the polygon. Why? Because every point on the edge of a circle is equidistant … Read more
Does each vertex have its own normals or does each triangle have its own normals? Like so often the answer is: “It depends”. Since a normal is defined as being the vector perpendicular to all vectors within a given plane (in N dimensions), you need a plane to calculate a normal. A vertex position is … Read more