Main insight here was that with any beacon being scanned from scanners 0
and s it holds that b₀ = Tₛ + bₛ*Rₛ with b₀, bₛ being the beacons
coordinates relative to 0, s resp., Tₛ is s' translation vector and Rₛ the
cube rotation matrix belonging to s.
This means Tₛ = b₀ - bₛ*Rₛ and we can calculate all combinations of 0's and
s' beacons for all 24 cube rotations and identify the rotation Rₛ with
translation Tₛ which appears at least 12 times (if this is the case).
This logic is implemented in the verb tx below. J Session follows - note
that after reading in the data, first the 24 cube rotations are constructed:
rd=: {{ ([: ".&.:> }.);._2 ,&a: <;._2 rplc&('-';'_') y }}
]d=: rd 0 : 0
--- scanner 0 ---
404,-588,-901
528,-643,409
-838,591,734
390,-675,-793
-537,-823,-458
-485,-357,347
-345,-311,381
-661,-816,-575
-876,649,763
-618,-824,-621
553,345,-567
474,580,667
-447,-329,318
-584,868,-557
544,-627,-890
564,392,-477
455,729,728
-892,524,684
-689,845,-530
423,-701,434
7,-33,-71
630,319,-379
443,580,662
-789,900,-551
459,-707,401
--- scanner 1 ---
686,422,578
605,423,415
515,917,-361
-336,658,858
95,138,22
-476,619,847
-340,-569,-846
567,-361,727
-460,603,-452
669,-402,600
729,430,532
-500,-761,534
-322,571,750
-466,-666,-811
-429,-592,574
-355,545,-477
703,-491,-529
-328,-685,520
413,935,-424
-391,539,-444
586,-435,557
-364,-763,-893
807,-499,-711
755,-354,-619
553,889,-390
--- scanner 2 ---
649,640,665
682,-795,504
-784,533,-524
-644,584,-595
-588,-843,648
-30,6,44
-674,560,763
500,723,-460
609,671,-379
-555,-800,653
-675,-892,-343
697,-426,-610
578,704,681
493,664,-388
-671,-858,530
-667,343,800
571,-461,-707
-138,-166,112
-889,563,-600
646,-828,498
640,759,510
-630,509,768
-681,-892,-333
673,-379,-804
-742,-814,-386
577,-820,562
--- scanner 3 ---
-589,542,597
605,-692,669
-500,565,-823
-660,373,557
-458,-679,-417
-488,449,543
-626,468,-788
338,-750,-386
528,-832,-391
562,-778,733
-938,-730,414
543,643,-506
-524,371,-870
407,773,750
-104,29,83
378,-903,-323
-778,-728,485
426,699,580
-438,-605,-362
-469,-447,-387
509,732,623
647,635,-688
-868,-804,481
614,-800,639
595,780,-596
--- scanner 4 ---
727,592,562
-293,-554,779
441,611,-461
-714,465,-776
-743,427,-804
-660,-479,-426
832,-632,460
927,-485,-438
408,393,-506
466,436,-512
110,16,151
-258,-428,682
-393,719,612
-211,-452,876
808,-476,-593
-575,615,604
-485,667,467
-680,325,-822
-627,-443,-432
872,-547,-609
833,512,582
807,604,487
839,-516,451
891,-625,532
-652,-548,-490
30,-46,-14
)
+--------------+--------------+--------------+--------------+--------------+
| 404 _588 _901| 686 422 578| 649 640 665|_589 542 597| 727 592 562|
| 528 _643 409| 605 423 415| 682 _795 504| 605 _692 669|_293 _554 779|
|_838 591 734| 515 917 _361|_784 533 _524|_500 565 _823| 441 611 _461|
| 390 _675 _793|_336 658 858|_644 584 _595|_660 373 557|_714 465 _776|
|_537 _823 _458| 95 138 22|_588 _843 648|_458 _679 _417|_743 427 _804|
|_485 _357 347|_476 619 847| _30 6 44|_488 449 543|_660 _479 _426|
|_345 _311 381|_340 _569 _846|_674 560 763|_626 468 _788| 832 _632 460|
|_661 _816 _575| 567 _361 727| 500 723 _460| 338 _750 _386| 927 _485 _438|
|_876 649 763|_460 603 _452| 609 671 _379| 528 _832 _391| 408 393 _506|
|_618 _824 _621| 669 _402 600|_555 _800 653| 562 _778 733| 466 436 _512|
| 553 345 _567| 729 430 532|_675 _892 _343|_938 _730 414| 110 16 151|
| 474 580 667|_500 _761 534| 697 _426 _610| 543 643 _506|_258 _428 682|
|_447 _329 318|_322 571 750| 578 704 681|_524 371 _870|_393 719 612|
|_584 868 _557|_466 _666 _811| 493 664 _388| 407 773 750|_211 _452 876|
| 544 _627 _890|_429 _592 574|_671 _858 530|_104 29 83| 808 _476 _593|
| 564 392 _477|_355 545 _477|_667 343 800| 378 _903 _323|_575 615 604|
| 455 729 728| 703 _491 _529| 571 _461 _707|_778 _728 485|_485 667 467|
|_892 524 684|_328 _685 520|_138 _166 112| 426 699 580|_680 325 _822|
|_689 845 _530| 413 935 _424|_889 563 _600|_438 _605 _362|_627 _443 _432|
| 423 _701 434|_391 539 _444| 646 _828 498|_469 _447 _387| 872 _547 _609|
| 7 _33 _71| 586 _435 557| 640 759 510| 509 732 623| 833 512 582|
| 630 319 _379|_364 _763 _893|_630 509 768| 647 635 _688| 807 604 487|
| 443 580 662| 807 _499 _711|_681 _892 _333|_868 _804 481| 839 _516 451|
|_789 900 _551| 755 _354 _619| 673 _379 _804| 614 _800 639| 891 _625 532|
| 459 _707 401| 553 889 _390|_742 _814 _386| 595 780 _596|_652 _548 _490|
| | | 577 _820 562| | 30 _46 _14|
+--------------+--------------+--------------+--------------+--------------+
mm=: +/ .* NB. Matrix multiplication
'x y z'=: I=: e.@i. 3 NB. Unit vectors
Z=: (y,(-x),:z) mm^:(i.4) I NB. 4 rotations around z-axis
NB. R ~ Matrix representations of all 24 cube rotations
$R=: ,/ ((z,y,:-x) mm^:(i.4) I) mm"2/ Z
16 3 3
$R=: R, ,/ ((x,z,:-y) mm^:(1 3) I) mm"2/ Z
24 3 3
B=: 0{::d NB. Beacons relative to scanner 0
S=: }. i. #d NB. Remaining scanners' indices
T=: 0 0 0 $~ 3,~ #d NB. Scanners' translation vectors
ol=: ~. #~ [: 12&<: #/.~ NB. Check for 12 overlapping beacons
NB. tx ~ for scanner y=s calculate all possible translations Tₛ
NB. with b₀ = Tₛ + bₛ*Rₛ => Tₛ = b₀ - bₛ*Rₛ and identify
NB. the one with 12 overlapping beacons - if available
tx=: {{ ol&.> ;/ ,/"3 B -"1/"2 (y{::d) mm"1/"2 R }}"0
3 : 0 '' NB. Apply tx to all remaining scanners S and identify
those
while. 0<$S do. NB. with 12 overlaps - s is the 1st and has rotation r{R
s=. {&S {. 'i r'=. {. ($ #: I.@,) 1&= #&>X=. tx S
T=: (,(<i,r){::X) s} T NB. Store translation vector Tₛ
B=: ~. B, (s{T) +"1 (r{R) mm"1/"2~ s{::d NB. Update B with s' beacons
S=: S -. s NB. Drop s from scanners S
end.
)
# B NB. (*)
79
>./ ,([: +/ |@-)"1/~ T NB. (**)
3621
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
