http://en.wikipedia.org/wiki/Closest_pair_of_points The problem can be solved in O(n log n) time using the recursive divide and conquer approach, e.g., as follows: Sort points along the x-coordinate Split the set of points into two equal-sized subsets by a vertical line x = xmid Solve the problem recursively in the left and right subsets. This will give … Read more
If i remember correctly, the algorithm is to draw a horizontal line through your test point. Count how many lines of of the polygon you intersect to reach your point. If the answer is odd, you’re inside. If the answer is even, you’re outside. Edit: Yeah, what he said (Wikipedia):
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
First, regarding the line intersection: you do not need the actual point of intersection, only to know if they intersect. See http://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/ for an algorithm that does just that. About the List implementation: In your implementation using Lists, you call indexOf on the sweepline to find nl. This searches the sweepline from start to end. … Read more
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
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
BTW complexity is indeed O(n^3) to lower that you need to: sort the points somehow by x and or y in ascending or descending order. Also use of polar coordinates can help sometimes use divide at impera (divide and conquer) algorithms usually for planar geometry algorithms is good idea to divide area to quadrants and … Read more
you should also add the input in vector form so we can test on your data … I would approach like this: find center of axis aligned bbox O(n) compute max distance in each angle O(n) just create table for enough m angles (like 5 deg step so m = 360/5) where for each angle … Read more
most problem cases are solved by translation vectors intersection check black is the original line/curve whatever … gray is translation vector (normal to black and size = outline distance) blue is outline if the translation vectors not intersect then it is most likely all OK but if they do then just do something like this: … Read more
Perhaps you should check out (PDF warning! Also note that, for some reason, the order of the pages is reversed) “Optimal Algorithms for Computing the Minimum Distance Between Two Finite Planar Sets” by Toussaint and Bhattacharya: It is shown in this paper that the minimum distance between two finite planar sets if [sic] n points … Read more