CODEWITHSUNDEEP
c#
ScruffyDuck
ScruffyDuck

Reputation: 2666

Getting the distance between geographically placed objects

I have an application (cad like editor) in which the user may place a lot of positional nodes (defined by their latitude and longitude). The application needs to tell the user if these nodes are very close together - a common design error is to overlap them. What the app is doing is something rather like ReSharper or CodeRush does in the IDE - parses the project and reports problems. A project may have several thousand of these nodes so testing for overlap becomes exponetially more time consuming as the numbers go. At the moment I am using two for loops to get through the list. 

for (int i = 0; i < count - 1; i++) {
     for (int j = i + 1; j < count; j++) {
         // check the distance between the i and j elements and if less than
         // a predetermined value report it
    }
}

I would like to get the process of identifying these into 'real time' so that the user is told at once in the event that an overlap occurs. The looping is expensive as is the testing of the distance between nodes. Most of the comparisons are wasted of course.

I just wonder if there is another way. I have thought about sorting the list by lat and lon and comparing adjacent elements but I suspect that will not work nor necessarily be faster.

My other thought is to move the activity to another thread (I really have no experience of using multiple threads) so that the values are being updated - for example storing a reference to nearby nodes in each object. However I can imagine needing to clone the object tree for the background thread so that there is no conflict with the foreground.

Upvotes: 1

Views: 236

Answers (3)

ScruffyDuck
ScruffyDuck

Reputation: 2666

Thanks to the insights given here I think I have found a reasonable way to deal with this.

*First to sort all the points in latitude order.
*Then loop through the sorted list. 
*For each entry in the list compare the latitude offset (distance in meters) to the entries below it.
*If the latitude offset is less than the test distance then check the actual distance from point to point and if it is inside the test radius report the issue.
*When the latitude offset exceeds the test distance move on to the next point in the list and repeat the tests.

I have not written the code yet but it seems to me that if there are no overlaps then I will make a single pass. Since overlaps are rare in practice then the total number of tests is likely to be quite small. For 1000 points the current method makes 500,000 tests. The new method is unlikely to make more than a few thousand.

Upvotes: 0

Vanwaril
Vanwaril

Reputation: 7528

Since the user is placing these locations, the ideal solution would be to assume all previously placed points are not nearby, and with each new point or moved point, check against the rest -- this becomes a single for loop, which should be reasonable.

Another, more ideal solution however:

Let position of A be lat, lng.
Convert both lat and lng to a fixed-length representation
    (truncating the degree of precision to a value below which 
    you are sure they will overlap)
Let xa = lat . lng (concatenate both)
Let ya = lng . lat

Given some position B, find xb, yb.

B is 'close' to A iff | xa - xb | < delta, | ya - yb | < delta.

So what you can do is sort the values of xi, yi for all your input points. When you want to check for points that are too close, you need to traverse through the list of xi's to find points that are too close together (linear time, since they will be adjacent) and then check if the same points in the list of yi's are too close.

Upvotes: 0

Henk Holterman
Henk Holterman

Reputation: 273244

You could look into Tessealtion.

Executing this on another Thread is a completely separate issue, you could do that with your nested loops as well as with a more efficient algorithm.

Upvotes: 1

Related Questions