Пакет Qhull , включая qhull, qconvex и rbox, должен помочь (я сам использовал их для этой цели). Например, на странице примеров qconvex приведено следующее (настроено для более крупного теста):
rbox 100 D3 | qconvex s o TO result
Вышеприведенное вычисляет трехмерную выпуклую оболочку из 100 случайных точек, записывает сводную информацию в консоль и записывает точки и грани в «результат».
Вот пример теста для нахождения 3-й выпуклой оболочки из 40 точек. Очки:
0.3215426810286406 0.1678336189760208 -0.2203710966001927
0.2229772524190855 -0.4213242506806965 -0.1966818060695024
0.3688830163971363 -0.1831502133823468 -0.2056387967482571
-0.1712592515826777 -0.3542439228428937 0.2223876390814666
-0.3309556113844324 -0.370961861099081 0.2439994981922204
-0.1004397059794885 -0.09014152417903909 -0.008600084584765189
0.458374538420117 -0.09914027349943322 -0.2505798421339875
-0.4954086979808367 -0.3339869997780649 -0.3195065691317492
0.053091190339151 0.3036317017894533 0.1380056861210668
0.4615616439483703 0.4665423151725366 0.1766835406205464
-0.4797380864431505 0.0419809916447671 -0.4254776681079321
-0.003168473023146823 -0.2525299883005488 -0.27151530400991
-0.3577162826971303 -0.1375644040643837 -0.04494194644032229
-0.3392973838740004 0.4288679723896719 -0.01599531622230571
0.1667164640191164 0.003605551555385444 -0.4014989499947977
0.00714666676441833 0.1140243407469469 0.407090128778564
-0.03621271768232132 0.3728502838619522 0.4947140370446388
-0.3411871756810576 -0.3328629143842151 -0.4270033635450559
0.3544683273457627 -0.450828987127942 -0.0827870439577727
-0.4018510635028137 0.08917494033386464 -0.2367824197158054
0.3978697768392692 -0.002667689232777493 0.1641431727112673
-0.245701439441835 0.495905311308713 -0.3194406286994373
0.161352035739787 -0.1563404972258401 0.3852604361113724
0.07214279572678994 -0.4960366976410492 0.1112227161519441
0.3201855824516951 0.359077846965825 0.02136723140381946
0.1190541238701475 -0.05734495917087884 0.2032677509852384
0.3210853052521919 0.4807189479290684 0.4433501688235907
0.3862800354941562 0.2085496142586224 0.09336129957191763
0.1233572616459404 0.265491605052251 0.117400122450106
0.1438531872293476 -0.2594872752758556 -0.2026374435076839
0.2724846394476338 -0.3506708492996831 0.2750346518820475
-0.4926118841325975 -0.3279366743079728 0.3683135596740186
0.2459906458351674 0.3647787136629026 -0.1641662355178652
-0.141922976953837 -0.2994764654892278 -0.3009570467294725
-0.1850859398814719 0.2606059478228967 0.004159106876849283
-0.09789466634196664 -0.3156603563722785 -0.303610991503681
0.2100642609503719 -0.4499717643018549 0.3245569875692548
-0.1707163766685095 -0.2301452446078371 -0.05112823569320907
-0.312260808713977 -0.1674135249735914 0.2808831662692904
-0.1966306233747216 0.2291105671125563 -0.3387042454804333
Выпуклая оболочка состоит из следующих точек:
0.3215426810286406 0.1678336189760208 -0.2203710966001927
0.2229772524190855 -0.4213242506806965 -0.1966818060695024
0.458374538420117 -0.09914027349943322 -0.2505798421339875
-0.4954086979808367 -0.3339869997780649 -0.3195065691317492
0.4615616439483703 0.4665423151725366 0.1766835406205464
-0.4797380864431505 0.0419809916447671 -0.4254776681079321
-0.3392973838740004 0.4288679723896719 -0.01599531622230571
0.1667164640191164 0.003605551555385444 -0.4014989499947977
-0.03621271768232132 0.3728502838619522 0.4947140370446388
-0.3411871756810576 -0.3328629143842151 -0.4270033635450559
0.3544683273457627 -0.450828987127942 -0.0827870439577727
0.3978697768392692 -0.002667689232777493 0.1641431727112673
-0.245701439441835 0.495905311308713 -0.3194406286994373
0.161352035739787 -0.1563404972258401 0.3852604361113724
0.07214279572678994 -0.4960366976410492 0.1112227161519441
0.3210853052521919 0.4807189479290684 0.4433501688235907
0.2724846394476338 -0.3506708492996831 0.2750346518820475
-0.4926118841325975 -0.3279366743079728 0.3683135596740186
0.2459906458351674 0.3647787136629026 -0.1641662355178652
0.2100642609503719 -0.4499717643018549 0.3245569875692548
Вот 2D тестовый пример. Очки:
0.3215348546593775 0.03629583077160248
0.02402358131857918 -0.2356728797179394
0.04590851212470659 -0.4156409924995536
0.3218384001607433 0.1379850698988746
0.11506479756447 -0.1059521474930943
0.2622539999543261 -0.29702873322836
-0.161920957418085 -0.4055339716426413
0.1905378631228002 0.3698601009043493
0.2387090918968516 -0.01629827079949742
0.07495888748668034 -0.1659825110491202
0.3319341836794598 -0.1821814101954749
0.07703635755650362 -0.2499430638271785
0.2069242999022122 -0.2232970760420869
0.04604079532068295 -0.1923573186549892
0.05054295812784038 0.4754929463150845
-0.3900589168910486 0.2797829520700341
0.3120693385713448 -0.0506329867529059
0.01138812723698857 0.4002504701728471
0.009645149586391732 0.1060251100976254
-0.03597933197019559 0.2953639456959105
0.1818290866742182 0.001454397571696298
0.444056063372694 0.2502497166863175
-0.05301752458607545 -0.06553921621808712
0.4823896228171788 -0.4776170002088109
-0.3089226845734964 -0.06356112199235814
-0.271780741188471 0.1810810595574612
0.4293626522918815 0.2980897964891882
-0.004796652127799228 0.382663812844701
0.430695573269106 -0.2995073500084759
0.1799668387323309 -0.2973467472915973
0.4932166845474547 0.4928094162538735
-0.3521487911717489 0.4352656197131292
-0.4907368011686362 0.1865826865533206
-0.1047924716070224 -0.247073392148198
0.4374961861758457 -0.001606279519951237
0.003256207800708899 -0.2729194320486108
0.04310378203457577 0.4452604050238248
0.4916198379282093 -0.345391701297268
0.001675087028811806 0.1531837672490476
-0.4404289572876217 -0.2894855991839297
Корпус:
-0.161920957418085 -0.4055339716426413
0.05054295812784038 0.4754929463150845
0.4823896228171788 -0.4776170002088109
0.4932166845474547 0.4928094162538735
-0.3521487911717489 0.4352656197131292
-0.4907368011686362 0.1865826865533206
0.4916198379282093 -0.345391701297268
-0.4404289572876217 -0.2894855991839297