Test case data for convex-hull

I need to make a 2D convex hull function for a class assignment and I want a more robust test cases than the assignment provides. Does anyone known of a largish test cases (25 < n < 100) with the solution?

回答1:

The Qhull package, including qhull, qconvex, and rbox should do the trick (I've used them for this exact purpose myself). For example, the qconvex examples page gives the following (tweaked for a larger test case):

rbox 100 D3 | qconvex s o TO result

The above computes the 3-d convex hull of 100 random points, writes a summary to the console, and writes the points and facets to 'result'.

Here's a sample test case for finding the 3-d convex hull of 40 points. The points are:

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

The convex hull is composed of the following points:

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

Here's a 2D test case. Points:

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

Hull:

-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

回答2:

Here's some more test data:

Here's some test data:

Test 1

8 7 7 7 -7 -7 -7 -7 7 9 0 -9 0 0 9 0 -9

Test 2

16 7 7 7 -7 -7 -7 -7 7 9 0 -9 0 0 9 0 -9 0 0 1 2 -2 1 -1 -1 3 4 4 3 -5 4 6 5

Test 3

72 0 0 1 2 -2 1 -1 -1 3 4 4 3 -5 4 6 5 7 7 7 -7 -7 -7 -7 7 9 0 -9 0 0 9 0 -9 -8 0 8 0 -7 0 7 0 -6 0 6 0 -5 0 5 0 -4 0 4 0 -3 0 3 0 -2 0 2 0 -1 0 1 0 0 -8 0 8 0 -7 0 7 0 -6 0 6 0 -5 0 5 0 -4 0 4 0 -3 0 3 0 -2 0 2 0 -1 0 1 1 1 2 2 3 3 4 4 5 5 6 6 1 -1 2 -2 3 -3 4 -4 5 -5 6 -6 -1 1 -2 2 -3 3 -4 4 -5 5 -6 6 -1 -1 -2 -2 -3 -3 -4 -4 -5 -5 -6 -6

All answers are the same: 8 (0, -9) (7, -7) (9, 0) (7, 7) (0, 9) (-7, 7) (-9, 0) (-7, -7)