Looking for a solution to group items by their vector

I’m facing a sorting problem: in a drawing there are a number of circles that were placed in sets of 4 along arbitrary axes. The data that I have are the coordinates of the centers for those circles and the normal vector to their face – the same vector may be shared by many groups, so it is not a reliable solution for grouping.

I also cannot resort to group the circles whose centers were collinear since this generates unpredictable results.

To make things worst some of the circles were flipped, so their vectors were opposed.

I feel that the solution should be to combine the vector with the center point in such way to get an identical criteria for items that belong to the same group (share the same axis), but I really don’t have any idea what to do.

This is an excerpt from the data I have to sort (ordered manually for grouping comprehension):

;pairs of center point & vector
'(((2057.63 -5539.35 2576.98) (-0.317429 0.221831 -0.921971))
 ((1997.95 -5497.65 2403.64) (-0.317429 0.221831 -0.921971))
 ((2061.43 -5542.02 2588.04) (0.317429 -0.221831 0.921971))
 ((2057.63 -5539.35 2576.98) (0.317429 -0.221831 0.921971))
 ((1953.87 -5442.46 2559.24) (-0.1917 0.1917 -0.96255))
 ((1917.83 -5406.42 2378.28) (-0.1917 0.1917 -0.96255))
 ((1956.17 -5444.76 2570.79) (0.1917 -0.1917 0.96255))
 ((1953.87 -5442.46 2559.24) (0.1917 -0.1917 0.96255))
 ((1900.23 -5533.61 2574.24) (-0.1917 0.1917 -0.96255))
 ((1864.19 -5497.57 2393.28) (-0.1917 0.1917 -0.96255))
 ((1902.53 -5535.91 2585.79) (-0.1917 0.1917 -0.96255))
 ((1900.23 -5533.61 2574.24) (0.1917 -0.1917 0.96255)))

I will appreciate any suggestions or solutions. Thank you for attention.

Maybe you can make XLINES from obtained normal vectors and center points of circles, do OVERKILL on XLINES to remove duplicate XLINES, and then group circles by XLINE curves with checking their centers as points on XLINE - if (vlax-curve-getparamatpoint) returns some value, then circle is in group for checked XLINE... Process all XLINES as groups and check for all circles by single XLINE...

Here is a generic grouping function that I use regularly:

[color=GREEN];; Group By Function  -  Lee Mac[/color]
[color=GREEN];; Groups items considered equal by a given predicate function[/color]

([color=BLUE]defun[/color] LM:GroupByFunction ( lst fun [color=BLUE]/[/color] tmp1 tmp2 x1 )
   ([color=BLUE]if[/color] ([color=BLUE]setq[/color] x1 ([color=BLUE]car[/color] lst))
       ([color=BLUE]progn[/color]
           ([color=BLUE]foreach[/color] x2 ([color=BLUE]cdr[/color] lst)
               ([color=BLUE]if[/color] (fun x1 x2)
                   ([color=BLUE]setq[/color] tmp1 ([color=BLUE]cons[/color] x2 tmp1))
                   ([color=BLUE]setq[/color] tmp2 ([color=BLUE]cons[/color] x2 tmp2))
               )
           )
           ([color=BLUE]cons[/color] ([color=BLUE]cons[/color] x1 ([color=BLUE]reverse[/color] tmp1)) (LM:GroupByFunction ([color=BLUE]reverse[/color] tmp2) fun))
       )
   )
)

Call the above with:

([color=BLUE]defun[/color] _2D ( x ) ([color=BLUE]list[/color] ([color=BLUE]car[/color] x) ([color=BLUE]cadr[/color] x)))

(LM:GroupByFunction lst
   ([color=BLUE]lambda[/color] ( a b )
       ([color=BLUE]equal[/color]
           (_2D ([color=BLUE]trans[/color] ([color=BLUE]car[/color] a) 0 ([color=BLUE]cadr[/color] a)))
           (_2D ([color=BLUE]trans[/color] ([color=BLUE]car[/color] b) 0 ([color=BLUE]cadr[/color] a)))
           0.1
       )
   )
)

Where lst is your list of center/normal pairs.

For testing:

([color=BLUE]defun[/color] _2D ( x ) ([color=BLUE]list[/color] ([color=BLUE]car[/color] x) ([color=BLUE]cadr[/color] x)))
([color=BLUE]mapcar[/color]
   ([color=BLUE]function[/color]
       ([color=BLUE]lambda[/color] ( x )
           ([color=BLUE]mapcar[/color]
               ([color=BLUE]function[/color]
                   ([color=BLUE]lambda[/color] ( a b )
                       ([color=BLUE]entmake[/color] ([color=BLUE]list[/color] '(0 . [color=MAROON]"LINE"[/color]) ([color=BLUE]cons[/color] 10 ([color=BLUE]car[/color] a)) ([color=BLUE]cons[/color] 11 ([color=BLUE]car[/color] b))))
                   )
               )
               x ([color=BLUE]cdr[/color] x)
           )
       )
   )
   (LM:GroupByFunction lst
       ([color=BLUE]lambda[/color] ( a b )
           ([color=BLUE]equal[/color]
               (_2D ([color=BLUE]trans[/color] ([color=BLUE]car[/color] a) 0 ([color=BLUE]cadr[/color] a)))
               (_2D ([color=BLUE]trans[/color] ([color=BLUE]car[/color] b) 0 ([color=BLUE]cadr[/color] a)))
               0.1
           )
       )
   )
)

By the way, your list contains data resulting in duplicate circles:

'(
[color=red]    ((2057.63 -5539.35 2576.98) (-0.317429 0.221831 -0.921971))[/color]
   ((1997.95 -5497.65 2403.64) (-0.317429 0.221831 -0.921971))
   ((2061.43 -5542.02 2588.04) (0.317429 -0.221831 0.921971))
   [color=red]((2057.63 -5539.35 2576.98) (0.317429 -0.221831 0.921971))[/color]
[color=green]    ((1953.87 -5442.46 2559.24) (-0.1917 0.1917 -0.96255))[/color]
   ((1917.83 -5406.42 2378.28) (-0.1917 0.1917 -0.96255))
   ((1956.17 -5444.76 2570.79) (0.1917 -0.1917 0.96255))
   [color=green]((1953.87 -5442.46 2559.24) (0.1917 -0.1917 0.96255))[/color]
[color=blue]    ((1900.23 -5533.61 2574.24) (-0.1917 0.1917 -0.96255))[/color]
   ((1864.19 -5497.57 2393.28) (-0.1917 0.1917 -0.96255))
   ((1902.53 -5535.91 2585.79) (-0.1917 0.1917 -0.96255))
   [color=blue]((1900.23 -5533.61 2574.24) (0.1917 -0.1917 0.96255))[/color]
)

What I meant to say, you'll have to check beside center on curve also and point obtained as center+normal vector... As a matter a fact, if you create those XLINES with all circles centers and their normals, and after that do OVERKILL on them all, you'll be left with exactly those XLINES that also represent circles groups... So number of groups is also number of left XLINES...

(LM:GroupByFunction lst
   ([color=BLUE]lambda[/color] ( a b )
       ([color=BLUE]equal[/color]
           (_2D ([color=BLUE]trans[/color] ([color=BLUE]car[/color] a) 0 [color=red](cadr a)[/color]))
           (_2D ([color=BLUE]trans[/color] ([color=BLUE]car[/color] b) 0 [color=red](cadr a)[/color]))
           0.1
       )
   )
)

Lee, your lisp will group collinear circles but I think Mircea wants collinear circles AND in parallel planes (or else, what will be the criteria for collinearity, since the normal vector for the first circle is simply an arbitrary one).

Here, I have to mention that on example list, and according to image in OP, your routine gives a good result. But try it on this list:

'(((2057.63 -5539.35 2576.98) (-0.317429  0.221831 -0.921971))
 ((1997.95 -5497.65 2403.64) (0 0 1))
 ((2061.43 -5542.02 2588.04) a)
 ((2057.63 -5539.35 2576.98) nil)
 ((1953.87 -5442.46 2559.24) (-0.1917  0.1917 -0.96255))
 ((1917.83 -5406.42 2378.28) (-0.1917  0.1917 -0.96255))
 ((1956.17 -5444.76 2570.79) ( 0.1917 -0.1917  0.96255))
 ((1953.87 -5442.46 2559.24) ( 0.1917 -0.1917  0.96255))
 ((1900.23 -5533.61 2574.24) (-0.1917  0.1917 -0.96255))
 ((1864.19 -5497.57 2393.28) (-0.1917  0.1917 -0.96255))
 ((1902.53 -5535.91 2585.79) (-0.1917  0.1917 -0.96255))
 ((1900.23 -5533.61 2574.24) ( 0.1917 -0.1917  0.96255)))

So, maybe this:

(LM:GroupByFunction l
       (lambda ( a b )
           (or
               (equal
                   (_2D (trans (car a) 0 (cadr a)))
                   (_2D (trans (car b) 0 (cadr b)))
                   0.1
               )
               (equal
                   (_2D (trans (car a) 0 (cadr a)))
                   (_2D (trans (car b) 0 (mapcar '- (cadr b))))
                   0.1
               )
           )
       )
   )

Good catch Stefan, however, your proposed modification will incorrectly group the following list:

(setq l '(((3.0 4.0 5.0) (0.0 0.0 1.0)) ((-5.0 -3.0 4.0) (-1.0 0.0 0.0))))

I propose instead:

(LM:GroupByFunction l
   (lambda ( a b )
       (and
           (or (equal (cadr a) (cadr b) 0.1)
               (equal (cadr a) (mapcar '- (cadr b)) 0.1)
           )
           (equal
               (_2D (trans (car a) 0 (cadr a)))
               (_2D (trans (car b) 0 (cadr a)))
               0.1
           )
       )
   )
)

Thank you very much Marko, Lee and Stefan for you interest and support! I can hardly wait to test those solutions tomorrow morning.

Some comments: the vectors/axes of the groups were not neccessarily parallel - I'm interested to sort the circles by their common axis. About the identical sets of data - that this is from the fact that, in some cases, there are concentrical circles.

You're very welcome Mircea, let us know how you get on!

Gentlemen, I have investigated the above examples and learned something new - I wasn't aware that can use a sense vector as argument for TRANS function.

All those solutions were grouping the circles in pairs, while I'm looking to have them as lists that store all items from the same axis. However from your code excerpts I have enough know-how now to write my sorting routine. Thank you very much again!

Lee, if you don't mind, I believe that there is an issue in your last code:

(equal
(_2D (trans (car a) 0 (cadr a))[color=red])[/color] [s][color=red]0.1)[/color][/s]
(_2D (trans (car b) 0 (cadr a))[color=red])[/color] 0.1[s][color=red])[/color][/s]
)

Gentlemen, I have investigated the above examples and learned something new - I wasn't aware that can use a sense vector as argument for TRANS function.

Indeed, the trans function can accept an integer, entity name, or normal vector (furthermore, this normal vector need not be of unit length).

All those solutions were grouping the circles in pairs, while I'm looking to have them as lists that store all items from the same axis. However from your code excerpts I have enough know-how now to write my sorting routine. Thank you very much again!

Upon testing the functions with your example data, I receive three groups of four items where each item in the group resides in a plane parallel to the other items, with the circle centers aligned - is this not what is required?

Lee, if you don't mind, I believe that there is an issue in your last code:

(equal
(_2D (trans (car a) 0 (cadr a))[color=red])[/color] [s][color=red]0.1)[/color][/s]
(_2D (trans (car b) 0 (cadr a))[color=red])[/color] 0.1[s][color=red])[/color][/s]
)

Good catch Mircea!

I shall update my code to fix the typo for those reading the thread in future.

I have to apologize for my previous statement. It is true, the items were grouped correctly, by four and not two by two - I got confused by the connecting lines which were generated from those lists. Sorry for inconvenience.

No problem at all Mircea, no need to apologise my friend