3

There are two points A, B, and distances x (miles from A), and y (miles from B). Let the distance from A to B be N. So, A is N miles away from B. How do I solve the problem: What are the points available that are (N + x + y) miles away from A? I'm not sure how to explain this any better. I really have no clue on how to attack this problem, I read Fastest Way to Find Distance Between Two Lat/Long Points and I believe the solution given calculates the distance between two points and have no idea if this solution could be used to apply to my problem, or if so, how.

Community
  • 1
  • 1
Derek
  • 11,980
  • 26
  • 103
  • 162
  • 1
    1. If I understand correctly, you are looking to find all the points within a circle whose center is point A and whose radius R = (N + x + y). 2. I assume you are able to calculate R outside MySQL. Are those two assumptions correct? – Tom Haws Jan 06 '12 at 15:08
  • 1
    I am not sire but check these Mysql functions [functions-for-testing-spatial-relations-between-geometric-objects](http://dev.mysql.com/doc/refman/5.1/en/functions-for-testing-spatial-relations-between-geometric-objects.html) – Uday Sawant Jan 06 '12 at 19:05

1 Answers1

2

If you are looking for an approximation algorithm I suggest to look for a k-means algorithm or a hierarchical cluster, especially a monster curve or a space filling curve. First off you can compute a minimal spanning tree of the graph and then remove the longest and expensivest edges. Then the tree makes many little trees and you can use the k-means to compute group of points i.e. clusters.

"The single-link k-clustering algorithm ... is precisely Kruskal's algorithm ... equivalent to finding an MST and deleting the k-1 most expensive edges." See for example here: https://stats.stackexchange.com/questions/1475/visualization-software-for-clustering.

A good example for a monster curve is the hilbert curve. The basic form of this curve is an U-shape and by copy many of it together and rotating it the curve fills the euklidian space. Surprisingly a gray code can help to find out the orientation of this U-shape. You can look up Nick's spatial index quadtree hilbert curve blog article about more details. Instead to calculate the curve's index you can put together a quadkey like in bing maps. The quadkey is unique for each coordinate and it can be used with normal string operations. Each position in the key is part of the U-shape curve and thus you can select this region of points from select partially from left to right from the quadkey.

In this image you can see the green polygon is found using a hilbert curve:

enter image description here

You can find my php classes here: http://www.phpclasses.org/package/6202-PHP-Generate-points-of-an-Hilbert-curve.html

Community
  • 1
  • 1
Micromega
  • 12,486
  • 7
  • 35
  • 72
  • +1 albeit it is hard to understand based on your description, it would be much clearer (and the aha) to have a working example showing how this can be achieve. – Jasonw Jan 20 '12 at 01:47
  • @Jasonw: I've added some more information to my answer. The image and the green polygone is done by myself using a hilbert curve. It can be useful to find the travel salesmane problem. – Micromega Jan 20 '12 at 11:39