[Scilab-users] need a little help

classic Classic list List threaded Threaded
11 messages Options
der_Phil der_Phil
Reply | Threaded
Open this post in threaded view
|

[Scilab-users] need a little help

Hi experts,

my problem is (I guess) a very common thing, but I somehow get stucked.

I aim to find the nearest position of ANY value in array_1 to ANY position in array_2.

e.g.:

A = array of doubles with 1000 elements.
B = array of doubles with 10'000 elements.

for each element of A I want to know it's nearest value in B.
Also I want to know the index of the nearest value in B.

I could do it in a bunch of for-loops, but this is way to slow, since this loops 1000 values against 10'000 values of B.

something like this:

nearesVal   = zeros(1000);
distIndex    = zeros(1000);

for i=1:1000
  d = 1000000; // just a rediculous big number that is much greater than max(A) & max(B)
  for j = 1:10000
     act_dist = abs( A(i) - B(j) );     // actual minimal distance  
     if act_dist <= d
        d = act_dist;
        nearestVal(i) = B(j);
        distIndex(i)  = j;
      end
   end
end

I do not have Scilab at hand, while I am writing this, but it looks like it should work :-)

Thanks
Phil









_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users
shorne shorne
Reply | Threaded
Open this post in threaded view
|

Re: need a little help

A simpler way --

outarr=zeros(1000)
for i=1:1000
[m,k]=min(abs(B-A(i));
outarr(i)=k;
end;
This will produce a list in outarr such that outarr(n) is the index of the element in B closest to the n'th element in A .

If you want to go faster, consider setting up  a binary tree containing B.  Then use the tree to search for nearest neighbor to A(i) and to -A(i).
Then decide which neighbor is closer.  (I think this works).
Searching the tree goes as log of length of B at the expense of a linear time in setting it up.
For some length of B this will win.

S
 






Inactive hide details for "P M" ---02/15/2019 03:58:32 PM---Hi experts, my problem is (I guess) a very common thing, but I some"P M" ---02/15/2019 03:58:32 PM---Hi experts, my problem is (I guess) a very common thing, but I somehow get stucked.

From: "P M" <[hidden email]>
To: "International users mailing list for Scilab." <[hidden email]>
Date: 02/15/2019 03:58 PM
Subject: [Scilab-users] need a little help
Sent by: "users" <[hidden email]>





Hi experts,

my problem is (I guess) a very common thing, but I somehow get stucked.

I aim to find the nearest position of ANY value in array_1 to ANY position in array_2.

e.g.:

A = array of doubles with 1000 elements.
B = array of doubles with 10'000 elements.

for each element of A I want to know it's nearest value in B.
Also I want to know the index of the nearest value in B.

I could do it in a bunch of for-loops, but this is way to slow, since this loops 1000 values against 10'000 values of B.

something like this:

nearesVal   = zeros(1000);
distIndex    = zeros(1000);

for i=1:1000
  d = 1000000; // just a rediculous big number that is much greater than max(A) & max(B)
  for j = 1:10000
     act_dist = abs( A(i) - B(j) );     // actual minimal distance  
     if act_dist <= d
        d = act_dist;
        nearestVal(i) = B(j);
        distIndex(i)  = j;
      end
   end
end

I do not have Scilab at hand, while I am writing this, but it looks like it should work :-)

Thanks
Phil







_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users



_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users
Samuel GOUGEON Samuel GOUGEON
Reply | Threaded
Open this post in threaded view
|

Re: need a little help

In reply to this post by der_Phil
Hello Phil,

This should work:

--> [A,B] = ndgrid(rand(1,1000), rand(1,10000));  // test's data
--> size(A)
 ans  =
   1000.   10000.
--> [v, i] = min(abs(A-B));


The minimal distances are in v, the index of the closest in B are in i.

Regards
Samuel

Le 15/02/2019 à 21:46, P M a écrit :
Hi experts,

my problem is (I guess) a very common thing, but I somehow get stucked.

I aim to find the nearest position of ANY value in array_1 to ANY position in array_2.

e.g.:

A = array of doubles with 1000 elements.
B = array of doubles with 10'000 elements.

for each element of A I want to know it's nearest value in B.
Also I want to know the index of the nearest value in B.

I could do it in a bunch of for-loops, but this is way to slow, since this loops 1000 values against 10'000 values of B.

something like this:

nearesVal   = zeros(1000);
distIndex    = zeros(1000);

for i=1:1000
  d = 1000000; // just a rediculous big number that is much greater than max(A) & max(B)
  for j = 1:10000
     act_dist = abs( A(i) - B(j) );     // actual minimal distance  
     if act_dist <= d
        d = act_dist;
        nearestVal(i) = B(j);
        distIndex(i)  = j;
      end
   end
end

I do not have Scilab at hand, while I am writing this, but it looks like it should work :-)

Thanks
Phil










_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users



_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users
Samuel GOUGEON Samuel GOUGEON
Reply | Threaded
Open this post in threaded view
|

Re: need a little help

In reply to this post by der_Phil
Sorry, instead of my previous message, please read

--> [A,B] = ndgrid(rand(1,1000), rand(1,10000));  // test's data
--> size(A)
 ans  =
   1000.   10000.
--> [v, i] = min(abs(A-B),
"c");

Samuel


_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users
Samuel GOUGEON Samuel GOUGEON
Reply | Threaded
Open this post in threaded view
|

Re: need a little help

... and even clearer, with respect to your own notations:

--> A = rand(1,1000);  // test's data
--> B = rand(1,10000);

--> [a, b] = ndgrid(A, B);

--> size(a)  // same for b
 ans  =
   1000.   10000.
--> [v, i] = min(abs(a-b),
"c");


_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users
der_Phil der_Phil
Reply | Threaded
Open this post in threaded view
|

Re: need a little help

Ok, thanks for your help..

Actually the sizes I gave where just for demonstation.

If I use the real array sizes, I get a message: can not allocate  7469.60MB memory...which maybe is true.
available RAM after starting Scilab is 3701 MB

actual array sizes:

A has 1076 elements
B has 1'350'000 elements, with a lot of Nan's in it

if I use thrownan(B) I can reduce the array size of B to 867751 elements but still get the Message above.

(without thrownan() the memory scilab wants to allocate is even bigger)




Am Fr., 15. Feb. 2019 um 23:25 Uhr schrieb Samuel Gougeon <[hidden email]>:
... and even clearer, with respect to your own notations:

--> A = rand(1,1000);  // test's data
--> B = rand(1,10000);

--> [a, b] = ndgrid(A, B);

--> size(a)  // same for b
 ans  =
   1000.   10000.
--> [v, i] = min(abs(a-b),
"c");

_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users

_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users
der_Phil der_Phil
Reply | Threaded
Open this post in threaded view
|

Re: need a little help

problem solved.....I had to think differently than before.

Actually my goal was to compare point coordinates to map coordinates and find the points on the map which are closest to the given point coordinates.

The map is of width:    900    // in reality the map is based on an image with 900x1500 pixels
The map is of height: 1500

The points are building a line on the map...e.g: the line consists of 1076 points
So from the map I have build:

x = map(1,:);   // contains all x coordinates of the map
y = map(2,:);   // contains all y coordinates of the map

points = [ lineX, lineY];      // points contain the X-Y-coordinates of the line

for i = 1:n
     actPoint = points(i,:);
     [nearestX xInd]   = min(abs(actPoint(1)-x));
     [nearestY yInd]  = min(abs(actPoint(2)-y));
     nearestPoint(i,:) = [x(xInd) y(yInd)];
end


This is what works for now, though it is still slow.

For searching 100 points of the line it needs about 10 seconds.
For searching 200 points of the line it needs about 19 seconds.
For searching 500 points of the line it needs about 45 seconds.
For searching 1000 points of the line it needs about 98 seconds.







Am Mo., 18. Feb. 2019 um 16:39 Uhr schrieb P M <[hidden email]>:
Ok, thanks for your help..

Actually the sizes I gave where just for demonstation.

If I use the real array sizes, I get a message: can not allocate  7469.60MB memory...which maybe is true.
available RAM after starting Scilab is 3701 MB

actual array sizes:

A has 1076 elements
B has 1'350'000 elements, with a lot of Nan's in it

if I use thrownan(B) I can reduce the array size of B to 867751 elements but still get the Message above.

(without thrownan() the memory scilab wants to allocate is even bigger)




Am Fr., 15. Feb. 2019 um 23:25 Uhr schrieb Samuel Gougeon <[hidden email]>:
... and even clearer, with respect to your own notations:

--> A = rand(1,1000);  // test's data
--> B = rand(1,10000);

--> [a, b] = ndgrid(A, B);

--> size(a)  // same for b
 ans  =
   1000.   10000.
--> [v, i] = min(abs(a-b),
"c");

_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users

_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users
der_Phil der_Phil
Reply | Threaded
Open this post in threaded view
|

Re: need a little help

..update: removing all NaN's from the map it takes about 27seconds to find all nearest points...
I think, I can live with that...unless somebody else has another brilliant idea.

best regards,
Philipp


Am Mo., 18. Feb. 2019 um 18:08 Uhr schrieb P M <[hidden email]>:
problem solved.....I had to think differently than before.

Actually my goal was to compare point coordinates to map coordinates and find the points on the map which are closest to the given point coordinates.

The map is of width:    900    // in reality the map is based on an image with 900x1500 pixels
The map is of height: 1500

The points are building a line on the map...e.g: the line consists of 1076 points
So from the map I have build:

x = map(1,:);   // contains all x coordinates of the map
y = map(2,:);   // contains all y coordinates of the map

points = [ lineX, lineY];      // points contain the X-Y-coordinates of the line

for i = 1:n
     actPoint = points(i,:);
     [nearestX xInd]   = min(abs(actPoint(1)-x));
     [nearestY yInd]  = min(abs(actPoint(2)-y));
     nearestPoint(i,:) = [x(xInd) y(yInd)];
end


This is what works for now, though it is still slow.

For searching 100 points of the line it needs about 10 seconds.
For searching 200 points of the line it needs about 19 seconds.
For searching 500 points of the line it needs about 45 seconds.
For searching 1000 points of the line it needs about 98 seconds.







Am Mo., 18. Feb. 2019 um 16:39 Uhr schrieb P M <[hidden email]>:
Ok, thanks for your help..

Actually the sizes I gave where just for demonstation.

If I use the real array sizes, I get a message: can not allocate  7469.60MB memory...which maybe is true.
available RAM after starting Scilab is 3701 MB

actual array sizes:

A has 1076 elements
B has 1'350'000 elements, with a lot of Nan's in it

if I use thrownan(B) I can reduce the array size of B to 867751 elements but still get the Message above.

(without thrownan() the memory scilab wants to allocate is even bigger)




Am Fr., 15. Feb. 2019 um 23:25 Uhr schrieb Samuel Gougeon <[hidden email]>:
... and even clearer, with respect to your own notations:

--> A = rand(1,1000);  // test's data
--> B = rand(1,10000);

--> [a, b] = ndgrid(A, B);

--> size(a)  // same for b
 ans  =
   1000.   10000.
--> [v, i] = min(abs(a-b),
"c");

_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users

_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users
Claus Futtrup Claus Futtrup
Reply | Threaded
Open this post in threaded view
|

Re: need a little help

In reply to this post by der_Phil
Hi Philipp

>problem solved.....I had to think differently than before.

Heh!

It helps to know what you actually want to do (and also the size of the problem).

Cheers,
Claus

On 18.02.2019 18:08, P M wrote:
problem solved.....I had to think differently than before.

Actually my goal was to compare point coordinates to map coordinates and find the points on the map which are closest to the given point coordinates.

The map is of width:    900    // in reality the map is based on an image with 900x1500 pixels
The map is of height: 1500

The points are building a line on the map...e.g: the line consists of 1076 points
So from the map I have build:

x = map(1,:);   // contains all x coordinates of the map
y = map(2,:);   // contains all y coordinates of the map

points = [ lineX, lineY];      // points contain the X-Y-coordinates of the line

for i = 1:n
     actPoint = points(i,:);
     [nearestX xInd]   = min(abs(actPoint(1)-x));
     [nearestY yInd]  = min(abs(actPoint(2)-y));
     nearestPoint(i,:) = [x(xInd) y(yInd)];
end


This is what works for now, though it is still slow.

For searching 100 points of the line it needs about 10 seconds.
For searching 200 points of the line it needs about 19 seconds.
For searching 500 points of the line it needs about 45 seconds.
For searching 1000 points of the line it needs about 98 seconds.







Am Mo., 18. Feb. 2019 um 16:39 Uhr schrieb P M <[hidden email]>:
Ok, thanks for your help..

Actually the sizes I gave where just for demonstation.

If I use the real array sizes, I get a message: can not allocate  7469.60MB memory...which maybe is true.
available RAM after starting Scilab is 3701 MB

actual array sizes:

A has 1076 elements
B has 1'350'000 elements, with a lot of Nan's in it

if I use thrownan(B) I can reduce the array size of B to 867751 elements but still get the Message above.

(without thrownan() the memory scilab wants to allocate is even bigger)




Am Fr., 15. Feb. 2019 um 23:25 Uhr schrieb Samuel Gougeon <[hidden email]>:
... and even clearer, with respect to your own notations:

--> A = rand(1,1000);  // test's data
--> B = rand(1,10000);

--> [a, b] = ndgrid(A, B);

--> size(a)  // same for b
 ans  =
   1000.   10000.
--> [v, i] = min(abs(a-b),
"c");

_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users

_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users



Virus-free. www.avast.com

_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users
der_Phil der_Phil
Reply | Threaded
Open this post in threaded view
|

Re: need a little help

@ Claus:

...well actually I wanted to treat every coordinate separatly....so A would be my X coordinate of the map and B would be the x coordinate of the line.
Afterwarsd I would do the same with the Y-coordinate..

So I think my question expressed what I wanted to do in the beginning.

What I did not expect was, that the size of the arrays would matter  (did not expect this memory issue).

Anyways....of course you are right.
Cheers,
Philipp
 


Am Mo., 18. Feb. 2019 um 18:32 Uhr schrieb Claus Futtrup <[hidden email]>:
Hi Philipp

>problem solved.....I had to think differently than before.

Heh!

It helps to know what you actually want to do (and also the size of the problem).

Cheers,
Claus

On 18.02.2019 18:08, P M wrote:
problem solved.....I had to think differently than before.

Actually my goal was to compare point coordinates to map coordinates and find the points on the map which are closest to the given point coordinates.

The map is of width:    900    // in reality the map is based on an image with 900x1500 pixels
The map is of height: 1500

The points are building a line on the map...e.g: the line consists of 1076 points
So from the map I have build:

x = map(1,:);   // contains all x coordinates of the map
y = map(2,:);   // contains all y coordinates of the map

points = [ lineX, lineY];      // points contain the X-Y-coordinates of the line

for i = 1:n
     actPoint = points(i,:);
     [nearestX xInd]   = min(abs(actPoint(1)-x));
     [nearestY yInd]  = min(abs(actPoint(2)-y));
     nearestPoint(i,:) = [x(xInd) y(yInd)];
end


This is what works for now, though it is still slow.

For searching 100 points of the line it needs about 10 seconds.
For searching 200 points of the line it needs about 19 seconds.
For searching 500 points of the line it needs about 45 seconds.
For searching 1000 points of the line it needs about 98 seconds.







Am Mo., 18. Feb. 2019 um 16:39 Uhr schrieb P M <[hidden email]>:
Ok, thanks for your help..

Actually the sizes I gave where just for demonstation.

If I use the real array sizes, I get a message: can not allocate  7469.60MB memory...which maybe is true.
available RAM after starting Scilab is 3701 MB

actual array sizes:

A has 1076 elements
B has 1'350'000 elements, with a lot of Nan's in it

if I use thrownan(B) I can reduce the array size of B to 867751 elements but still get the Message above.

(without thrownan() the memory scilab wants to allocate is even bigger)




Am Fr., 15. Feb. 2019 um 23:25 Uhr schrieb Samuel Gougeon <[hidden email]>:
... and even clearer, with respect to your own notations:

--> A = rand(1,1000);  // test's data
--> B = rand(1,10000);

--> [a, b] = ndgrid(A, B);

--> size(a)  // same for b
 ans  =
   1000.   10000.
--> [v, i] = min(abs(a-b),
"c");

_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users

_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users



Virus-free. www.avast.com
_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users

_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users
Christophe Dang Ngoc Chan Christophe Dang Ngoc Chan
Reply | Threaded
Open this post in threaded view
|

Re: {EXT} Re: need a little help

In reply to this post by der_Phil
Hello,

> De : users [mailto:[hidden email]] De la part de P M
> Envoyé : lundi 18 février 2019 18:09
>
> Actually my goal was to compare point coordinates to map coordinates
> and find the points on the map which are closest to the given point coordinates.
> [...]
> The points are building a line on the map

I'm not sure I understand your problem well but:

If you want to find the points of the maps that are close to a line, You might considere the Cartesian equation of the line

f(x, y) = 0 with f(x, y) = ax + by + c

and search for the points of the map which abs(f(x, y)) value is low.

From what I understand about your statement, you have a set of points = [ lineX, lineY] ; you  might extract the (a, b, c) parameters of the line by linear regression, something like

X = [x ; ones(x)];

A = y\X;

(if the line is not vertical) then look at abs(A(1)*x - y + A(2)) < threshold or something like that.

Otherwise, if you want to detect a line in a map, you might have a look at the Hough transform.

Regards

--
Christophe Dang Ngoc Chan
Mechanical calculation engineer

Public
This e-mail may contain confidential and/or privileged information. If you are not the intended recipient (or have received this e-mail in error), please notify the sender immediately and destroy this e-mail. Any unauthorized copying, disclosure or distribution of the material in this e-mail is strictly forbidden.
_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users