How to find nearest points

[Anonymous]

Hi to all.
I have a grid model with point situated on a fixed distance one from another. It's the same as grid, but it is slightly rotated. My question is, is there any fast way, for finding the nearest 4 points to a point that I pick in the drawing? The grid model is in a big array of coordinates, not in Model Space(if it matters). I need a fast way, because the grid array is at least 500x500 elements.

[Anonymous]

If the grid is rectilinear then you can use a coordinate system
aligned with the grid to store the locations of the grid lines
instead of the locations of the points. This would allow you to
store a 500 x 500 grid in 1003 values (including the origin and
rotation of the coordinate system) instead of 250000. You
would then translate the input point into the coordinate system
of the grid and do a binary search of the horizontal and vertical
lines to find the ones between which the point lies. If the grid
has constant spacing in either or both directions then you can
further reduce the storage and find the coordinates in the
constant-spacing direction(s) using division. Then simply
translate the four (or one?, or two?, or five?, or six?) found
points back to the original coordinate system.

[Bryco]

The first thing is to create a ucs that has the sames axis as your grid, then you can translate the picked point into that ucs.
Now you divide the picked point x by 500, that'll give allow you to derive the x of the 4 points, then do the same for y.
Now translate those 4 points into world

[jbooth]

IMO, Bryco has the best idea for you. simply translate your source point into the new coordinate system (this is what user-coordinate systems are for).

It's much easier to create a UCS that aligns with your custom grid than it is to check the distance to 1000 different lines, or to 250000 unique point definitions.

Get the point relative to your custom UCS and round the result to the accuracy you want. You can then convert it back to the world coordinate system to get the resultant point on your grid.

[Anonymous]

10x to you all, but you all don't get my point. This grid, that I'm speaking about is not in model space. It is in a VBA array. I'm looking for a mathematical way for finding that zone.

[Bryco]

Matricies are all about math.
If you make a ucs for your grid, the math will come.

[jbooth]

The ucs transform theory is all about linear transforms from one coordinate system to another, which is exactly what you want.

Even staying out of autocad you can create a rotation/translation matrix that will move a point from the world coordinate system in autocad to your custom coordinate system.

It doesn't matter that your grid is in modelspace, the only thing that matters is if your coordinate space is a basis of R3 or R2 (ie: 2D or 3D space).

However, you will need to learn two things:

1. How to create a rotational and/or translational matrix.
2. How to multiply one matrix with another.

The Autocad class library can do this for you, I don't know if they are available in VBA. You might have to use lisp or objectarx.

Good luck.

[Anonymous]

Neycho:

There is no need to go to matrix multiplication, you only need to translate
One point, say the origin of the grid, all the other points will be in a
rectangular array and can be calculated in base to dx and dy of the original
grid, as the rotation transform is an isometric one(preserve distances). In
other words:

Let X0,Y0 the origin of the rotated grid, X',Y' the rotated Origin of the
grid, then

theta= rotation angle, maybe negative in this case
X' = X*cos(theta) + Y*sin(theta)
Y' = -Xsin(theta) + Y*cos(theta)

X'n = X' + n*dx
Y'n= Y' + n*dy

so now you have to transform the test point using the same method of X',Y',
and check if is inside the ij rectangle a= dx;b= dy , that's easy:

Let Xt,Yt the test point, dx,dy the x and y steps of the grid


Function IsInside(X' as double, Y' as double, dx as double, dy as double, Xt
as double, Yt as double) as boolean
dim i as integer
dim j as integer
dim Xinside as boolean
dim YInside as boolean

IsInside=false
Xinside=false
Yinside=false

'Avoid to nest for cicles
'Check if Xt is in some vertical strip
'You can obtain i and j in the same way
for j=0 to 499
if ((X' + (j-1)*dx) < Xt and Xt < (X' + j*dx) ) then
Xinside=true
exit for
end for
next j

'Check if Yt is in some horizontal strip
for i= 0 to 499
if (Y' + (i-1)*dy) < Yt) and (Yt < (Y' + i*dy))then
IsInside=true
exit for
end if
next i

IsInside=Xinside and Yinside
End function









wrote in message news:5845121@discussion.autodesk.com...
10x to you all, but you all don't get my point. This grid, that I'm speaking
about is not in model space. It is in a VBA array. I'm looking for a
mathematical way for finding that zone.

[Bryco]

Gaston your stuff is doing what matricies do, moving from one origin to another then rotating. But it looks simpler so thats good. The possible 500 loops dont seem necessary though as you can simply divide by dx to reckon the x grid numbers

[Anonymous]

that's true, just trying to explain how to check if a point is inside a
rectangular well aligned box. This method with the
(X't-X'0)/dx aproach would be a very efficient computational aproach to the
task of find the cell sourrounding the test point, needs to transform only
One point of the grid a n test points.
The loop aproach is usefull when the spacing of one or both axis is a non
linear function, example: a logarithmic graph.



wrote in message news:5846375@discussion.autodesk.com...
Gaston your stuff is doing what matricies do, moving from one origin to
another then rotating. But it looks simpler so thats good. The possible 500
loops dont seem necessary though as you can simply divide by dx to reckon
the x grid numbers

[jbooth]

From: Gaston Nunez
Date: Feb/12/08 - 21:51 (PST)
The loop aproach is usefull when the spacing of one or both axis is a non
linear function, example: a logarithmic graph.


This can also be done with a matrix if set up properly. The advantage of using linear algebra is that (once set up) you can use your transformation matrix on any array of points, with one multiplication operation.

Anyway, every solution explained in this thread so far will work just fine for what you seem to need to do.