## Shortest distance between points algorithm

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

## Geo Fencing – point inside/outside polygon

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):

## How do I detect intersections between a circle and any other circle in the same plane?

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

## Implementing Hoey Shamos algorithm with C#

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

Categories c#

## How to check if line segment intersects a rectangle?

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

## Largest circle inside a non-convex polygon

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

## Given n points on a 2D plane, find the maximum number of points that lie on the same straight line

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

## How to Compute OBB of Multiple Curves?

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

## draw outline for some connected lines

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

## What is the fastest algorithm to calculate the minimum distance between two sets of points?

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