My Java Program

[DivideByZero]

Hi.

I created this Java program where you click around anywhere as many times you want then click calculate. After its done thinking, it will find the pixel closest to all of the places you clicked.

 

I can't really explain it well so please view my applet

 

What do you think of it? I'm a new developer so please critique.

 

I put a map of italy on the background and clicked every city except rome then clicked calculate. And then the closest pixel was very close to rome.

[timo]

2 tests:

 

0 points: I was surprised of that a status information (thinking x%) starts to run. Clicking on one of the example pictures to watch them during the (nonsensical) calculation stalled my Firefox.

 

2 points: After killing FF and restarting, I ran with 2 points. Again, a surprisingly long calculation time (this time not disturbed by me) with a strange result (see attachment). Accidently hit calculate again and tried to close the tab which was honored by yet another stall of FF.

[DivideByZero]

2 tests:

 

0 points: I was surprised of that a status information (thinking x%) starts to run. Clicking on one of the example pictures to watch them during the (nonsensical) calculation stalled my Firefox.

 

2 points: After killing FF and restarting, I ran with 2 points. Again, a surprisingly long calculation time (this time not disturbed by me) with a strange result (see attachment). Accidently hit calculate again and tried to close the tab which was honored by yet another stall of FF.

 

Sorry for the annoying time.

There is a bug for when you only click 2 points. Clicking 3 or more gives accurate results. And also don't interfere during the run time because its running a very long for-loop. The reason it takes so long is because it goes through every single pixel to find all the distances, then it orders all the distances from lowest to highest and displays the lowest.

The total run time is less than a minute though.

[Dr.Evil]

Quite interesting. Have you found a practical aplication for it yet?

I like the way it nearly found rome, not coinsidence. Your program could be used to decide the best location to place a delivery service or mabey with a little modification you could use it to calculate the average line of a scatter gragh.

 

I'm sure with a few more line of code you could get it to calculate a lot faster though.

[NeonBlack]

If you only want the smallest distance, why sort? Sorting takes a relatively long time depending on the sort method. Just search for the smallest value. I'm guessing that the majority of the time is not taken by the sort/search, but since the values are not in random order, you could improve the time slighty. However, this may become irrelevant soon as you will see.

 

I suspected you brute forced yesterday when I tried the program, but I didn't have time to post.

 

There is a better way which does not require brute force and does not require sorting or searching.

[DivideByZero]

If you only want the smallest distance, why sort? Sorting takes a relatively long time depending on the sort method. Just search for the smallest value. I'm guessing that the majority of the time is not taken by the sort/search, but since the values are not in random order, you could improve the time slighty. However, this may become irrelevant soon as you will see.

 

I suspected you brute forced yesterday when I tried the program, but I didn't have time to post.

 

There is a better way which does not require brute force and does not require sorting or searching.

 

There is an array containing 120000 numbers. For me to find the smallest number out of the 120000 numbers I ordered them from lowest to highest. How else could I find the smallest number?

 

Also I'm working on a cool modification on the code where there will be a light green dot on the closest pixel, then a bit darker dot on the 2nd closest pixel, then a more darker green dot on the 3rd closest pixel up to the last pixel. I wonder what the picture would look like in the end...

[Aeternus]

There is an array containing 120000 numbers. For me to find the smallest number out of the 120000 numbers I ordered them from lowest to highest. How else could I find the smallest number?

 

Also I'm working on a cool modification on the code where there will be a light green dot on the closest pixel, then a bit darker dot on the 2nd closest pixel, then a more darker green dot on the 3rd closest pixel up to the last pixel. I wonder what the picture would look like in the end...

 

If you want to find the smallest number in a list, it's quicker to just keep a record of the current smallest number and go through the list comparing and replacing that current number with a new one if it's smaller rather than sorting and then just taking the first. The fastest sorting algorithm will likely be O(nlogn) whereas the simple linear search is O(n).

 

Considering your overall method of calculation, I'm pretty sure there are iterative solutions to this problems that work on the points themselves to converge to a solution rather than trying all possible solutions, which would probably be quicker (See http://en.wikipedia.org/wiki/Geometric_median#Computation ).

[DivideByZero]

If you want to find the smallest number in a list, it's quicker to just keep a record of the current smallest number and go through the list comparing and replacing that current number with a new one if it's smaller rather than sorting and then just taking the first. The fastest sorting algorithm will likely be O(nlogn) whereas the simple linear search is O(n).

 

Considering your overall method of calculation, I'm pretty sure there are iterative solutions to this problems that work on the points themselves to converge to a solution rather than trying all possible solutions, which would probably be quicker (See http://en.wikipedia.org/wiki/Geometric_median#Computation ).

 

 

Cool! Thanks so much for the link I never knew there was such a method.

I think you're right, I can make this perform much faster. I'll be working on that soon

[NeonBlack]

What Aeternus said was precisely what I was getting at. Basically, you want to find x and y such to minimize the distances, which is [math]\sum{\sqrt{(x-x_i)^2+(y-y_i)^2}}[/math]

You can use an iterative method to do so.

If you implement this properly, it should run in under a second (or so- I'm guessing).

[Bignose]

Also if there is a bug for just two points, surely you can just write a special case for that --- since the closest point will be in the line between the two points at half the distance. Good use of IF statements should catch that pretty easily.

 

I was actually even thinking a genetic algorithm could be a neat way to solve this... http://en.wikipedia.org/wiki/Genetic_algorithm

Should only take a few generations, and again, probably less than second.

[DivideByZero]

What Aeternus said was precisely what I was getting at. Basically, you want to find x and y such to minimize the distances, which is [math]\sum{\sqrt{(x-x_i)^2+(y-y_i)^2}}[/math]

You can use an iterative method to do so.

If you implement this properly, it should run in under a second (or so- I'm guessing).

 

Thats exactly what I did. That only takes less than a second for my program. What actually takes time in the current program is ordering it.

[Aeternus]

Thats exactly what I did. That only takes less than a second for my program. What actually takes time in the current program is ordering it.

 

You suggested that you are testing every pixel to try and find a solution. This is not what is being suggested. If you look at the wikipedia article, the iterative solution involves choosing a guess and then iteratively improving this guess by use of an equation that converges to a solution. I assume you would most likely stop when two answers remain in a single square pixel (ie sufficient accuracy for you). This is clearly not the same as testing every pixel.

 

Using such a system you wouldn't have to have a list of all the possible pixels and their distances. Even with your current method, you only really need to keep track of the current smallest distance (ie, why keep track of all of them in a large array when only storing the current minimum and comparing as you go would work just as well (well better as the space complexity will be better)).

 

Sorry if I have misunderstood what you are doing.

[NeonBlack]

DBZ, how much calculus are you familiar with?

Think of it like [math]

f(x,y)=\sum{\sqrt{(x-x_i)^2+(y-y_i)^2}}

[/math]

You want to find the minimum of this function. You can do this in a number of ways; I think Newton's Method was the first I learned.

There are other faster ways of doing this, but I think this way is the simplest and speed shouldn't be an issue.

 

As to why you do not need to sort, consider this list of numbers:

12

7

8

5

9

How would you find the smallest number in real life? Sort it? I doubt it.

Look at the first number, 12. So far it's the smallest number we've found. Now look at the next number. 7 is smaller than 12, so now the smallest is 7. Next 8. 7 is still smallest. You get the idea. Keep going until the end.

This is easy to implement and only requires one pass through the list. The simplest sorting algorithms requires n^2 passes through the list. If you have 120000 pixels, it will require 14.4 billion passes through your list to sort!

[timo]

By now, most people should have understood why sorting isn't preferrable when looking for the closest point only. Hence, let's have a look at

Also I'm working on a cool modification on the code where there will be a light green dot on the closest pixel, then a bit darker dot on the 2nd closest pixel, then a more darker green dot on the 3rd closest pixel up to the last pixel. I wonder what the picture would look like in the end...