Need help to compare two lists of points

I hope I can make myself clear...

I have 2 lists of points (3 reals).

I want to draw a line between the 2 closest points found in List 1 and List
2.
So I need to compare each point in each list to find which points are the
closest distance to each other.

For instance...
List 1 = ((157.638 1926.17 0.0) (334.924 1767.03 0.0) (527.254 1971.24 0.0)
(364.985 2133.51 0.0)...)
List 2 = ((2234.78 1983.32 0.0) (2042.39 1700.95 0.0) (2030.37 2091.46 0.0)
(1819.94 1917.23 0.0)...)

Result...
From List 1 (527.254 1971.24 0.0)<- This point is closest
From List 2 (1819.94 1917.23 0.0) <- To this point

After comparing all points in both lists, it is found that the points above
have the closest distance between them.

List 1 Points
+
+ + <- Ignore these points
+ <- This point is closest
|
| <- Draw a line from 2 closest points
|
+ <- To this point
+ + <- Ignore these points
+
List 2 Points

The result of the function will be a list of the points from List1 and List2
which are the closest to each other
((527.254 1971.24 0.0) (1819.94 1917.23 0.0))

Thanks

Don Butler

 

Thanks Alan,

Actually, List1 and List2 are lists of lists so the IF function would not
work. There could be hundreds of points in each list.

I'm sure there's an eloquent way to find the answer so maybe one of our
"Guru" friends will help.

Thanks again.

Don

 

Something like this?

(setq List1 '((157.638 1926.17 0.0) (334.924 1767.03 0.0) (527.254 1971.24
0.0) (364.985 2133.51 0.0)))
(setq List2 '((2234.78 1983.32 0.0) (2042.39 1700.95 0.0) (2030.37 2091.46
0.0) (1819.94 1917.23 0.0)))

(defun closestPts (list1 list2 / dist temp pt1 pt2)
(setq dist 10e20);artificially large number to start with
(foreach x list1
(foreach y list2
(if (< (setq temp (distance x y)) dist)
(progn
(setq dist temp)
(setq pt1 x pt2 y)
)
)
)
)
(list pt1 pt2)
)

_$ (closestpts list1 list2)
((527.254 1971.24 0.0) (1819.94 1917.23 0.0))
_$

 

Don,
In the STDLIB at Reini Urban's website, there are some combinatorial
functions that may be of assistance to you for this. They will create, for
example, a list of all combinations of point pairs, which could then grind
through individually. Due to the tremendous number of possibilities as the
lists grow in numbers of elements, you may run into limitations in using
them, if the number of points grows too large. IOW, it might help, and it
might not. - but it may at least give you some ideas:

http://xarch.tu-graz.ac.at/autocad/stdlib/COMBINATIONS.LSP

Of course, if there is a more analytical geometrical solution for this,
perhaps using the vlax-curve- functions, I'd be happy to know of it.

hth,
David Kozina

 

Thanks Dave

Don

 

Sorry about posting my reply to your e-mail.

Looks great Jeff.

Thanks,

Don

 

this is a fun problem because certain approaches run literally 200 times faster than the straight comparison of each to
every other will do.
Here is the sequence I have found to work:

1) Make a list of the coordinates of all points
2) decide the upper limit of the search distance
3) sort the list by x coordinate
4) remove items with x coordinate further away than the search distance from the point in question
5) sort by Y and remove items again
6) loop through the remaining items using the actual distance and keep the one with the shortest distance

It turns out sorting the list of coordinates is super fast compared to the distance function.
So avid the distance function as much a possible and you will speed things up.

"Don Butler" <>
|>I hope I can make myself clear...
|>
|>I have 2 lists of points (3 reals).
|>
|>I want to draw a line between the 2 closest points found in List 1 and List
|>2.
|>So I need to compare each point in each list to find which points are the
|>closest distance to each other.
|>
|>For instance...
|>List 1 = ((157.638 1926.17 0.0) (334.924 1767.03 0.0) (527.254 1971.24 0.0)
|>(364.985 2133.51 0.0)...)
|>List 2 = ((2234.78 1983.32 0.0) (2042.39 1700.95 0.0) (2030.37 2091.46 0.0)
|>(1819.94 1917.23 0.0)...)
|>
|>Result...
|>From List 1 (527.254 1971.24 0.0)<- This point is closest
|>From List 2 (1819.94 1917.23 0.0) <- To this point
|>
|>After comparing all points in both lists, it is found that the points above
|>have the closest distance between them.
|>
|>List 1 Points
|> +
|>+ + <- Ignore these points
|> + <- This point is closest
|> |
|> | <- Draw a line from 2 closest points
|> |
|> + <- To this point
|>+ + <- Ignore these points
|> +
|>List 2 Points
|>
|>The result of the function will be a list of the points from List1 and List2
|>which are the closest to each other
|>((527.254 1971.24 0.0) (1819.94 1917.23 0.0))
|>
|>Thanks
|>
|>Don Butler
|>
|>
|>
|>
|>
|>
|>
|>
|>---
|>Outgoing mail is certified Virus Free.
|>Checked by AVG anti-virus system (http://www.grisoft.com).
|>Version: 6.0.779 / Virus Database: 526 - Release Date: 10/19/2004
|>

James Maeding
jmaeding at hunsaker dot com
Civil Engineer/Programmer

 

Nice what?, algorithm?
Very nice. Thanks, James!

faster than the straight comparison of each to

 

I'll give your approach a try.

Thanks,

Don

 

Would this be a little faster?

Code:

(defun closestpts (list1 list2 / dist temp pt1 pt2)
(setq dist 10e20) ;artificially large number to start with
(mapcar
(function
(lambda (x)
(mapcar
(function
(lambda (y)
(and (< (setq temp (distance x y)) dist)
(setq dist temp
pt1  x
pt2  y
)
)
)
)
list2
)
)
)
list1
)
(list pt1 pt2)
)

James
if you are using the distance command in step 4, you are still iterating through the entire list
with the distance command.

4) remove items with x coordinate further away than the search distance from the point in question

Or did i miss a step?

 

IIUC, James was suggesting using (- rather than (dist
to compare X and Y (and I suppose Z for 3D) values.
IOW, find differences, rather than calculate distances, which is more
involved mathematically, of course. If the X or Y difference is greater
than the 'compare distance', you KNOW automatically that the points in
question are no good.

Over hundreds or thousands of points, seems to me the trick would be
determining the 'upper limit of the search distance'. If this is unknown,
what would it be to just grab the distance between the first two points, and
use that value for the first 'weeding'?

Then, what if, say, each time the distance decreases to less than 70% (50%?)
of its original value, another point 'weeding' takes place through the
remaining lists, and so forth?

Would that be beneficial?

Just thinking out loud.
Somebody stop me

 

Yes, the tweaks you can do to my algorythm will speed things up even more.
The weeding idea is excellent. You just have to be careful not to weed too often.

One tricky way to do this would be to look at the item before and after the point in question when the list gets sorted
by x coordinate. The delta between theitem with the closest x coord would be a possible radius to use.
Then do the same thing for the Y coordinate maybe to refine the distance.

I did a routine to detect duplicate points and had to say every time what the search radius was. I used a small number
(1') so the speed increase was several hundred fold. That was a bit different though because it was ok to not find a
point within the radius.

Thats why this is fun, several approaches might be the best, I'm sure GIS people have good algorythms for this kind of
thing.


"David Kozina" <>
|>IIUC, James was suggesting using (- rather than (dist
|>to compare X and Y (and I suppose Z for 3D) values.
|>IOW, find differences, rather than calculate distances, which is more
|>involved mathematically, of course. If the X or Y difference is greater
|>than the 'compare distance', you KNOW automatically that the points in
|>question are no good.
|>
|>Over hundreds or thousands of points, seems to me the trick would be
|>determining the 'upper limit of the search distance'. If this is unknown,
|>what would it be to just grab the distance between the first two points, and
|>use that value for the first 'weeding'?
|>
|>Then, what if, say, each time the distance decreases to less than 70% (50%?)
|>of its original value, another point 'weeding' takes place through the
|>remaining lists, and so forth?
|>
|>Would that be beneficial?
|>
|>Just thinking out loud.
|>Somebody stop me
|>
|>
|>|>> Would this be a little faster?
|>>

Code:

(defun closestpts (list1 list2 / dist temp pt1 pt2)
|>>  (setq dist 10e20) ;artificially large number to start with
|>>  (mapcar
|>>    (function
|>>      (lambda (x)
|>>        (mapcar
|>>          (function
|>>            (lambda (y)
|>>              (and (< (setq temp (distance x y)) dist)
|>>                   (setq dist temp
|>>                         pt1  x
|>>                         pt2  y
|>>                   )
|>>              )
|>>            )
|>>          )
|>>          list2
|>>        )
|>>      )
|>>    )
|>>    list1
|>>  )
|>>  (list pt1 pt2)
|>> )

|>>
|>> James
|>> if you are using the distance command in step 4, you are still iterating
|>> through the entire list
|>> with the distance command.
|>>
|>> 4) remove items with x coordinate further away than the search distance
|>> from the point in question
|>>
|>> Or did i miss a step?
|>

James Maeding
jmaeding at hunsaker dot com
Civil Engineer/Programmer