Android Question Close Points

[Terradrones]

Hi Everybody

With the help of Klaus (Thank you Klaus), I have managed to write a simple CAD program (which is part of the CEASER Program), which the Surveyor uses in the Field with either a Total Station or a GPS. As the Surveyor picks up Topo points in the Field, those Points get plotted on the screen.

The Surveyor can then add CAD Entities to the screen where the Topo Points are plotted. Available functions are:
1. Points
2. Lines
3. Polylines
4. Circles
5. Arcs
6. Text

Layers, Colors and Linetypes are also included.

This way the Surveyor can semi complete the Survey Drawing in the Field. The Topo Points and the CAD drawing are stored in 2 different Tables in SQLite. The CAD drawing can be exported as a DXF file.

I also have snap options available while drawing:
1. Snap to Topo Point
2. Snap to CAD Point
3. Snap to end of a Line
4. Snap to the center of a Line
5. Snap to the Center of a Circle

This is where my problem is. If I turn on the Snap function and I have selected the "Snap to Topo Point" option and I draw a Line, the program runs through al the Topo Points and calculates the shortest distance between my finger position and the Topo Points. The start of the Line will be to the Topo Point with the Shortest distance. As I move my finger over the screen to draw the line, it will plot a round circle around the Topo Point closest to my Finger.The same applies when I lift my finger off the screen to complete the line.

For this I am using the Phytharos formula. This is fine if I have say 100 Topo Points plotted on the screen, but if there are say 5000 Topo Points plotted on the screen, it takes forever to find the closest Topo Point to my Finger.

Any ideas or maybe a kick in the right direction. Sometimes one cannot the Forest for the Wood.

 

[Brian Dean]

I assume that your points are organised as a simple list and you are testing them sequentially. If so there are two fairly well-known shortcuts worth taking -

1. Compare the squares of the distances (that is, don't waste time taking square roots).

2. But do take the square root of the shortest distance so far. If either the x-distance or y-distance of a point is greater than this then it can be ignored immediately.

To get better than this you have to reorganise your points list into a tree structure. That is quite an overhead unless you are going to be using the tree repeatedly. Even then deleting points from the tree can be a real pain. I have a coded a points-tree in Delphi but I don't have a B4X version, I'm afraid.

 

[Terradrones]

Thanks Brian, its work faster now.

 

[Brian Dean]

Its been a wet afternoon and I had a couple of hours to spare so I decided to translate my Delphi tree search code into B4J. I have run some tests and got some interesting results. I created a list of 10000 points randomly spread over a 1000000 x 1000000 grid. I compared searching this set of points for the point closest to the centre one hundred thousand times using both a straight list search and using the tree search. I am glad to say that both methods always returned the same point.

The results the list search returned times of around 50msec, although I got one isolated value of 33msec. The times for the tree search were around 4 to 6 msec, although more than once I got a search time of zero. These times are for 100 1000 searches.

The tree search is noticeably quicker, but typically only by a factor of ten. And a simple sequential list search of 10000 points took only half a 0.03 millisecond, so I am surprised that you are seeing unworkable delays when searching 5000 points. Its true that I ran my tests on a PC, but it is nothing special. Anyway, if you are interested I will publish my tree search code somewhere on the forum, but I need to do some more tests and checks first.

Edit : Corrected test count to 1000 (was previously mistakenly stated as 100). Also the overhead of the counting loop is noticeable : increasing the number of test cycles by a factor of ten only increased the test times by a factor of six. But the conclusion is the same - there should be no problem scanning 5000 points.

 

[klaus]

In stead of calculating the distance between the point and the cursor position you could you could check if :

If Abs(CursorX - PointX) < SnapDsitance And Abs(CursorY - PointY) < SnapDsitance Then
    'point is close
End If

Or

SnapDsitance2 = SnapDsitance * SnapDsitance
If (CursorX - PointX) * (CursorX - PointX) + (CursorY - PointY) * (CursorY - PointY) < SnapDsitance2 Then
    'point is close SnapDsitance2 =
End If

I do not know which one is faster.

If your points are in a SQL table you could do it with a query.
You may have a look at this post, it is for GPS locations but it shows the principle.
The test equation in the second example above should be adapted in the query.

 

[emexes]

list of 10000 points randomly spread over a 1000000 x 1000000 grid

The results the list search returned times of around 50msec

I did the same thing using X and Y Arrays rather than List, and I'm getting search speeds of 78 million points per second = 7800 searches of 10000 points per second = 0.128 ms per search (ie 0.000128 seconds).

cf your timings... I know I'm good, but I also know I'm not *that* good. ?

edit: was done with B4J on laptop rather than B4A on phone, but... is hard to believe the (almost) 400x speed differential between the two

You mentioned 1 million x 1 million grid, so I used 32 bit Ints for coordinates, and 64 bit Longs to do the math. Did you do same, or use floating point?

Also, I did squaring using * rather than ^

edit: Also, I searched for random points rather than repeatedly for the centre.

edit: Also, there are some Logs included within the timed section, because I was having trouble believing the times I was getting

Done using B4J on elcheapo Windows laptop bought new maybe six months ago for < $400 (ie < 250 USD ?)

Sub AppStart (Args() As String)
    Log("Hello world!!!")
 
    Dim NumPoints As Int = 10000
 
    Dim X(NumPoints) As Int
    Dim Y(NumPoints) As Int
 
    For I = 0 To NumPoints - 1
        X(I) = Rnd(-500000, 500000)
        Y(I) = Rnd(-500000, 500000)
    Next
 
    Log(DateTime.Now)
    Dim StartTime As Long = DateTime.Now
 
    Dim NumBurls As Int = 1000
    Dim NumCalcs As Int = 0
 
    For Burl = 1 To NumBurls
        Dim FindX As Long = Rnd(-510000, 510000)
        Dim FindY As Long = Rnd(-510000, 510000)
    
        Dim ClosestI As Int
        Dim ClosestDistanceSquared As Long
    
        For I = 0 To NumPoints - 1
            Dim DX As Long = FindX - X(I)
            Dim DY As Long = FindY - Y(I)
            Dim DistanceSquared As Long = DX * DX + DY * DY
        
            If I = 0 Then
                ClosestI = I
                ClosestDistanceSquared = DistanceSquared
            else If DistanceSquared < ClosestDistanceSquared Then
                ClosestI = I
                ClosestDistanceSquared = DistanceSquared
            End If       
        
            NumCalcs = NumCalcs + 1
        Next

        '''Log(Burl & tab & FindX & TAB & FindY & TAB & ClosestI & TAB & ClosestDistanceSquared)
        If Burl Mod 100 = 0 Then Log(Burl & TAB & (DateTime.Now - StartTime))
    Next
 
    Dim EndTime As Long = DateTime.Now
    Log(DateTime.Now)
 
    Log(((EndTime - StartTime) / NumBurls) & TAB & NumCalcs & TAB & ClosestI & TAB & ClosestDistanceSquared)
    Log(NumberFormat(NumCalcs / ((EndTime - StartTime) / 1000), 1, 0))

End Sub

Waiting for debugger to connect...
Program started.
Hello world!!!
1698295569995
100    23
200    78
300    84
400    92
500    97
600    105
700    111
800    117
900    123
1000    128
1698295570123
0.128    10000000    6292    1142480
78,125,000
Program terminated (StartMessageLoop was not called).

 

[Brian Dean]

cf your timings... I know I'm good, but I also know I'm not *that* good.

I wasn't happy with my timings - they were a bit rushed; that is was why I wanted to do some more checks. But I was surprised that @Terradrones was having problems in the first place - 5000 points is nothing in a vector mapping application, and is nothing compared to the amount of screen processing that is taking place anyway.

I used 32 bit Ints for coordinates, and 64 bit Longs to do the math.

Yes - I did that too. And multiply rather than exponentiate.

I am tied up today so will not have time to look at this, but I am not sure that it will be worth my while anyway. I think that you have demonstrated that there is an easier solution to the problem.

 

[emexes]

For this I am using the Phytharos formula.

Pythagoras? as in hypotenuse = Sqrt(A ^ 2 + B ^ 2) ?

Or is Phytharos a GIS formula for great-circle distance or similar, with multiple trig function calls?

Logarithmic and trigonometric functions are usually 10-100 times slower than basic arithmetic operations.

but if there are say 5000 Topo Points plotted on the screen, it takes forever to find the closest Topo Point to my Finger.

Are you doing the how-close-is-finger-to-point calculations using (x, y) pixel coordinates or (latitude, longitude) coordinates?

Any ideas or maybe a kick in the right direction. Sometimes one cannot the Forest for the Wood.

Yeah, that happened to me - high school homework to implement binary search, and I got bogged down thinking that the indices had to be integral powers of two. My program worked and I was very happy with it, until the teacher pointed out that it worked even better if I deleted most of it.

Anyway, see the sample code above. Even if you use floating point coordinates rather than integer, and List of Type rather than Array of simple numeric, it should still be fast enough.

 

[Brian Dean]

Hi again @emexes - you were right. There were errors in my testing - the main one being that I had understated the number of trials by a factor of ten! I have corrected my earlier post. However there might be other factors that I have overlooked.

I copied my class and test code to B4A and ran it on my Pixel 4a to see how test times compared with my desktop. They look broadly comparable -

** Activity (main) Resume **
10000 points
Tree search = 557 mSec for 100000 searches
Test point = 503425 : 502282
List search = 12436 mSec for 100000 searches
Checkpoint = 503425 : 502282
** Activity (main) Pause, UserClosed = false **

Note that these times are for 100000 searches. The times for the tree search can vary considerably because the tree is not balanced.

 

[emexes]

The times for the tree search can vary considerably because the tree is not balanced.

At < 6 µs average ? I think we can survive considerable variation ? but it's good to know the slack is there in case ever need more speed.