# Finding extreme points in the convex hull

22 ビュー (過去 30 日間)
Sultan 2019 年 3 月 21 日
コメント済み: Jan 2019 年 3 月 30 日
Suppose I have 1000 extreme points. I am computing volume of the convex hull generated by the points. But in these extreme points, there may exit some points which do not play any role in increasing the volume because they are a linear combination of the others. For example, in the figure, if we remove the extreme points 3, 6, 7, and 8 then the volume of the convex hull still will be the same.
Now I just want to know that how I can find those points which are not contributing in the volume?
Note: I have computed volume by using all the extreme points.

サインインしてコメントする。

### 採用された回答

John D'Errico 2019 年 3 月 21 日
Why not do the obvious?
xy = rand(1000,2);
>> ch = convhull(xy)
ch =
55
460
890
204
908
222
189
419
798
351
931
465
508
800
888
516
55
What does the output of convhull tell you? What do those numbers mean? You started with a list of 1000 points. Which points are not part of the convex hull? If they are not used in the convex hull, what does that tell you about them?
I suppose, since you figured out how to compute the area, then you are actually computing with the delaunayTriangulation tool first?
T = delaunayTriangulation(xy(:,1),xy(:,2))
T =
delaunayTriangulation with properties:
Points: [1000×2 double]
ConnectivityList: [1982×3 double]
Constraints: []
ch = convexHull(T);
You will get to the same place. So now, you need to think about what that list of numbers means, and how it tells you how those points which are internal to the convex hull are removed.
As far as knowing when a point lies on the surface of the convex hull, we might try this:
methods(T)
Methods for class delaunayTriangulation:
barycentricToCartesian delaunayTriangulation featureEdges isInterior size
cartesianToBarycentric edgeAttachments freeBoundary nearestNeighbor vertexAttachments
circumcenter edges incenter neighbors vertexNormal
convexHull faceNormal isConnected pointLocation voronoiDiagram
Do any of the methods you see listed there give you any ideas? For example, might the isInterior method help you?
Another idea is to consider if the inpolygon function could have helped you, given the output of convhull? How could you use ch as I computed it in several ways above, to compute something that inpolygon can use? Or, perhaps you might use polyshape?
x = [0 1 .5 0 .25];
>> y = [0 0 .5 1 .25];
>> ch = convhull(x,y)
ch =
1
2
3
4
1
>> S = polyshape(x(ch),y(ch));
Warning: Polyshape has duplicate vertices, intersections, or other inconsistencies that may produce inaccurate or unexpected results. Input data has been
modified to create a well-defined polyshape.
> In polyshape/checkAndSimplify (line 481)
In polyshape (line 175)
>> S
S =
polyshape with properties:
Vertices: [3×2 double]
NumRegions: 1
NumHoles: 0
Get your hands dirty. Play around. try a few things. Read the help for some of these methods, some functions. I'd wager you will learn a lot along the way.

#### 6 件のコメント

Sultan 2019 年 3 月 23 日
Sorry John D'Errico, I am getting wrong volume generated by the following matrix:
A = [1 1 1 0 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1 1 1 1 1
0.175142813658706 0.692169550572821 0.811640055081682 0.527731006873297 0.625578699074237 0.902158703876362 0.999999718179987 0.477054064645894 0.567550369277295 0.909509394972227 0.999999714655547 0.999956488989382 0.999956489109395 0.999999999881126
1 0 1 0 1 0 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 0 0 1 1 1 1 1
0 1 1 0 0 1 1 1 1 1 1 1 1 1
0.333333333333333 0.333333333333333 0.666666666666667 0.333333333333333 0.666666666666667 0.666666666666667 1 0.333333333333333 0.666666666666667 0.666666666666667 1 0.666666666666667 1 1
0.500000000000000 0 0.500000000000000 0.500000000000000 1 0.500000000000000 1 0.500000000000000 1 0.500000000000000 1 1 1 1
0 0.500000000000000 0.500000000000000 0.500000000000000 0.500000000000000 1 1 0.500000000000000 0.500000000000000 1 1 1 1 1
0 0 0 0 0 0 0 1 1 1 1 1 1 1
0 0 0 1 1 1 1 0 0 0 0 1 1 1
0 1 1 0 0 1 1 0 0 1 1 0 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0
0.497015877909149 0.497016067293893 0.840925894134826 0.531866375374743 0.765933133150656 0.765933242224084 1 0.531866375374743 0.765933133150656 0.765933242224084 1 1 1 1
0.242802140176088 0.238919579429391 0.349084162310578 0.262432456203338 0.357062286794043 0.355741397297938 0.436273613351990 0.662496137267479 0.841905137788078 0.836616305211572 0.933821166441762 0.897061979387265 0.950684689920800 0.947896592651385
0.230759257383744 0.228691173819494 0.347878495209359 0.661311410624516 0.837594354546628 0.831763512030162 0.937745506471509 0.255083284316262 0.346416652646412 0.351205440509780 0.434458524696830 0.893485279843158 0.947676352293766 0.948545947119172
0.230420046405159 0.685147816585810 0.820111453696594 0.220139554812513 0.361273371518753 0.815677714504223 0.917407338139174 0.218145565761602 0.365411779754937 0.814800251715698 0.919955096443319 0.425638940107427 0.480465357919348 0.945173761873583
0.684984576744918 0.229407109555457 0.818817195712070 0.220528811937092 0.815017515754926 0.372342419750687 0.922676028213150 0.229635348723607 0.818914406752354 0.351741931075334 0.909747165812448 0.430401961283242 0.947830102062482 0.482572609553778
0.754329897644891 0.716644926322426 0.880645099795776 0.728439197767964 0.863239309840341 0.855482672193250 0.955293004808391 0.725549959441084 0.857999981426944 0.853877902419788 0.951849347605524 0.954980547627352 0.962970183137014 0.992010963888211
0.731156896578669 0.233637085134105 0.872832575178561 0.713611540914814 0.845563723714238 0.852635453667819 0.983053042276448 0.278567672031913 0.891919095204298 0.353409195647206 0.957488038517925 0.944430523117453 0.975697973699684 0.968904483846556
0.720681323143561 0.232889836085790 0.869906357625563 0.275896293292514 0.889864848441574 0.356745295640446 0.961096106136496 0.704471798900404 0.835836967746586 0.850752653762153 0.980815776873804 0.941514253322573 0.971659665650331 0.969977696228598
0.240266338621729 0.707198552837162 0.872020709794412 0.698072566588830 0.860684986540137 0.823003285016481 0.984133806346245 0.280131157991610 0.350880800278606 0.892850326431872 0.957867739420176 0.942987645403940 0.965572291775147 0.977528591249230
0.233052939516194 0.714618340796733 0.870795661926255 0.271271434079533 0.351733120690822 0.890185848999073 0.961758624806289 0.702315168410352 0.855990436784508 0.827841429365553 0.980228649186015 0.939627348821708 0.969307013476340 0.970469885827875
0.717237426017183 0.722172459691952 0.808121353653809 0.462975522418128 0.853678286708359 0.860143514590053 0.938680168622427 0.677789884278913 0.835699471771237 0.810474011840523 0.879994868788342 0.911224092707613 0.968779457425341 0.942458040916897
0.708595900785586 0.463890636629888 0.916932445670562 0.698997220890729 0.801313521940941 0.901971814269626 0.999982877307703 0.491643335698033 0.916051357588011 0.538738733990132 0.963143879488791 0.974981886894070 0.999982973433316 0.974998970854808
0.752727553247561 0.504888884862676 0.913952161079509 0.544510870447013 0.908197370620518 0.592329993122026 0.956012790839300 0.735202747347081 0.851625140805652 0.889467561859571 0.999984239082504 0.976218093361274 0.999983916382935 0.976234180298655
0.434465230099397 0.693767541908835 0.930777500774693 0.683947219322594 0.914253869080225 0.771144112921188 0.999991443693847 0.461130396661282 0.509930607726805 0.934174987502519 0.982974154194888 0.986532665208966 0.986541390576298 0.999991281919020
0.494549502023564 0.699851282524005 0.921153170848706 0.513250304151022 0.553722169352890 0.918912687212985 0.959380694569185 0.696085298926813 0.914554471802799 0.787025400825100 0.999976175739399 0.972102238720743 0.972125737293748 0.999976595668322
0.499269277164859 0.499915432294210 0.569982571534209 0.498301658004337 0.562801193504701 0.562585237640903 0.605729602700318 0.675170461017115 0.907408888242719 0.907321371242467 0.965188007787883 0.940159738318138 0.970798793288888 0.969612738663114
0.488868537961680 0.487543215711433 0.557042169951008 0.689541375124604 0.901236636853649 0.901365106043118 0.956416834018062 0.490741537055750 0.557657377919263 0.557288973660541 0.601513433071030 0.940798236772880 0.969937729480944 0.971110837442013
0.700700379718829 0.395787728372357 0.870202350225594 0.703599821676465 0.767792001507802 0.874033691242416 0.934435856160353 0.179438028283333 0.806158545172310 0.495171253686035 0.957467848658297 0.833556858403869 0.863468505280805 0.972931155474173
0.296624268491064 0.661288281265754 0.873137604443738 0.657677801508179 0.867107183009603 0.729915458990306 0.938756600795567 0.210137172276586 0.421029699584070 0.820812983486443 0.985011413674523 0.850560666669124 0.986472561602853 0.864411842561658
0.490954206768756 0.482246673840639 0.572792796156786 0.509683499367423 0.568842561609398 0.563501091483195 0.615675615787120 0.508956866046219 0.886579033429390 0.879674491440022 0.965268412316540 0.918704483346348 0.962377477492821 0.959640002772761
0.688785226389047 0.179115632552026 0.806552897659724 0.523112508877886 0.883889914975452 0.619332076340209 0.980053045668759 0.455990732287393 0.892010382463012 0.542689162204875 0.978703631227714 0.969014693387822 0.999989982666163 0.969370746031424
0.504756651920428 0.485178542711923 0.892376283735074 0.506530270460377 0.575430373527838 0.891946243890951 0.957949684079035 0.501343201992163 0.903737089880931 0.563231615916955 0.964759330583724 0.921266933528005 0.970801229710372 0.967842149448522
0.746573848583144 0.430344510772095 0.886716057635660 0.190073334234415 0.839337277543362 0.533307097860553 0.968953946893125 0.740168189099084 0.804529448461713 0.878729148420868 0.940457080294262 0.866145769968257 0.886694972126335 0.981474377797552
0.582620228561246 0.250637021093829 0.787828353336300 0.568628109123815 0.781541258160587 0.749191638888287 0.961222222487926 0.274802293377159 0.784653695944978 0.449589830596829 0.936031979617259 0.831959986063074 0.927940713940689 0.941329624811622
0.671760351818017 0.146031639063064 0.776285690771163 0.626540531745160 0.895462860606134 0.726299280669077 0.993329903525026 0.342758292470611 0.923527995656574 0.406502233574626 0.982567742154178 0.960381335844574 0.999698269442009 0.985968400365717
0.469882777834895 0.173586002920053 0.557880690478452 0.476700414714904 0.541117254140735 0.565700679668466 0.627678160013517 0.472873841245575 0.897532790868628 0.561313766355447 0.939251028075020 0.914676767425363 0.963397951851580 0.951279456205961
0.680192542488811 0.126217748195720 0.770363313110940 0.444218291651861 0.852276469893683 0.518686792234142 0.926602606601628 0.152884130923332 0.774302968386270 0.277506202888629 0.864355345156742 0.597049673336827 0.929510213672009 0.667665698019861
0.460345485643126 0.465727235653395 0.899749624998155 0.498652308206004 0.921525136194463 0.579656724944702 0.999999167295661 0.493734646679607 0.574330802396640 0.921909460547619 0.999999999407080 0.988995555911133 0.999999410286372 0.999999092912589
0.661011879036529 0.166483997688653 0.777328021567137 0.349320638529515 0.910989311160755 0.418556139013951 0.974959643889453 0.618174708220752 0.883192342469390 0.728644186986235 0.991328044478066 0.953932640618984 0.999988424317447 0.980013553446141
0.550903295720016 0.337564729801848 0.770969431216228 0.340072911810705 0.771847163165835 0.510368176775650 0.912695295363261 0.538546140256805 0.722547437841861 0.801094124593413 0.942613284261446 0.855745880300275 0.896060704519924 0.960835349649707
0.474203717515232 0.166169916138273 0.565557587718472 0.463628735798373 0.917325551701226 0.553520291120360 0.949565600884357 0.479343655147028 0.543403276427790 0.566645542737863 0.630114198073889 0.929458708581362 0.979318255512021 0.951980500202724
0.491479183562584 0.502455086262929 0.874067407716022 0.137926240967775 0.589770695115936 0.602881002674236 0.960527823362130 0.471598717186379 0.570695602274287 0.876935170004948 0.952722549894584 0.608252332439169 0.634519368774635 0.974521430273052
1 0 1 1 1 1 1 0 1 0 1 1 1 1
0.268181946849737 0.590419542376498 0.782737283058776 0.579100236666751 0.760406450136328 0.774084528161780 0.951875481766792 0.287232041138163 0.458765272356504 0.794046501172972 0.939934015542182 0.836001435528283 0.950973262571854 0.931204746744783
0.148597275306796 0.665348579805026 0.777024762773015 0.625287529233607 0.731225943318612 0.887611927702111 0.992271787209549 0.340178047550897 0.409149937226747 0.918609874507788 0.983839257829888 0.962752077503718 0.986133842573564 0.997277595799593
0.420765715062472 0.719256337202655 0.868164858455924 0.167949599129054 0.537210721558048 0.809211019832145 0.954682333601872 0.711955253470750 0.858794198551986 0.804594294121591 0.946916246492309 0.845154147834245 0.974744077132768 0.874186866385943
0.146203162461749 0.447046472380105 0.533384040088087 0.473223893992208 0.557872733305196 0.526263617036060 0.609345647316835 0.457681896638353 0.540307024685709 0.884260080823777 0.926156664156026 0.913637847823410 0.951269328186312 0.962973449967148
0.162646568801262 0.729630956388227 0.822844245757289 0.485392191981697 0.559361156574656 0.883021986484372 0.956968004349507 0.178872656806226 0.235009839758498 0.826007543362027 0.872197635102020 0.607045472456100 0.630437834305428 0.976628617842418
0.352705903752143 0.546711827756428 0.763654945903020 0.361323064459455 0.514848532488369 0.765738782814154 0.893409120063983 0.536426355305780 0.795023811806857 0.730645291943679 0.947235873676542 0.858016141043373 0.946864930153850 0.912778220650616
0.168065502043254 0.661305974192813 0.779017241991321 0.347604814913758 0.416907121694394 0.907825058130347 0.972312432715329 0.618541076189157 0.730271397510614 0.881602657703722 0.991076586237943 0.953438929678101 0.977931558045486 0.999998937623339
0.162389295476681 0.470794392558663 0.555997321958237 0.467369290578372 0.552120449032661 0.905887394704287 0.942288189649943 0.476398614474878 0.562365867149863 0.540902998698742 0.624783009052633 0.920445554360768 0.950844456765280 0.969626085613132
0.145714109956607 0.710910127591983 0.808461915040802 0.154917169825878 0.228716616984941 0.812909953229809 0.866316284192106 0.477116551351018 0.558973605654870 0.868234784462826 0.949961335542330 0.604437601158708 0.640501613440790 0.970059387326928
0.176347049041242 0.169046394155620 0.249903881975278 0.473782742433013 0.572305121677332 0.569515776178670 0.628831095341289 0.485077898429872 0.585578762671969 0.582651106310877 0.642563864354230 0.952518288319671 0.975729715335820 0.979091633215722
0.145383165706158 0.474784898649169 0.585449897709110 0.166736326186459 0.221410063802585 0.587791279187342 0.641341187075793 0.484765942801607 0.588058958892718 0.864021851842020 0.956735056907036 0.636637426972548 0.659806131836188 0.976831295153664
0.473844954833496 0.139723841596358 0.585881573233941 0.171282080540700 0.578389342024766 0.232916145505990 0.638838964667429 0.494453933348092 0.874479568163200 0.586988221373231 0.961765463352062 0.650961145112266 0.979014560913084 0.676191844423152
0.136644155697607 0.452223855421373 0.569112689776395 0.492705123759843 0.595822868061753 0.863698653975254 0.961991753774511 0.169326976867456 0.231477327416696 0.568813036405541 0.628937232634225 0.656365499749644 0.683175116697576 0.977439215180933
0.472041703654075 0.133294508932123 0.573093345258528 0.484510731626852 0.874760616882987 0.565840049066046 0.948861764870378 0.159464314298747 0.563311114520554 0.234522966287578 0.636004654471240 0.630224039252047 0.966028158799687 0.664205075179988
0.485517369158653 0.485062688227763 0.930518316435339 0.165488055385004 0.582867908474545 0.583628518268064 0.990589037958432 0.165560912624103 0.582897769251884 0.583658486493461 0.990590475545914 0.330897989584712 0.669024910834460 0.668809469777177];
[~,v] = convhulln(A);
v= 1.2346e-13
% Now let me consider your procedure:
edges = convhulln(A);
% then edges will be 35372x14 dim,
% discardList = [16 17 18 19 25 30 34 36 38 40 45 46 51 52 55 56 57 60]
% totalNoOfDiscPoints = 18
% Now, If I remove the points from A with the indices given in the discardList, i.e., A(16,:)=[], ..., A(60,:)=[], and then compute the volume of A i.e., 44x14 dim matrix.
[~,v] = convhulln(A)
v = 1.1409e-13
% The volume is not the same. So I want to know how can I remove those points which are not contributing in volume increment or What is the minimum number of points in A that generates the boundary of the convex hull?
% Another way, what are the extreme points in A that are sufficient to generate the same volume v= 1.2346e-13.
% % Can we check volume after removing points one by one? After removing one point if we have the same volume then we move to the next point else we stay with the last matrix. How to code it? Or is there any other method?
John D'Errico 2019 年 3 月 23 日
In 14 dimensional space, the algebra to compute a convex hull gets nasty. I am worried you might have some problems doing this in double precision. I have seen that triangulations and convex hulls in as few as 7 dimensions can get difficult, but that was in older versions of MATLAB. (I'm going back over 20 years for that memory.) So maybe the MATLAB of today will succeed. They are now using better algorithms than they used 28 years ago or so.
Anyway, let me test your claim to see if you actually did what you just said you did.
[facets1,v1] = convhulln(A);
16 17 18 19 25 30 34 36 38 40 45 46 51 52 55 56 57 60
>> [facets2,v2] = convhulln(A(unique(facets1(:)),:));
>> whos facets1 facets2
Name Size Bytes Class Attributes
facets1 35372x14 3961664 double
facets2 35372x14 3961664 double
>> v1
v1 =
1.2346e-13
>> v2
v2 =
1.2346e-13
unique(facets1)'
ans =
Columns 1 through 26
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 20 21 22 23 24 26 27 28 29 31 32
Columns 27 through 44
33 35 37 39 41 42 43 44 47 48 49 50 53 54 58 59 61 62
A pleasant surprise, that MATLAB did not have a problem in 14 dimensions. But, clearly nothing you just said is correct. When you make a claim, try to make sure that you know what you are talking about.
The second convex hull, created using only the points that were in the first convex hull, is indeed identical to the first one. I'm sorry. I have no idea what you actually did, but it apparently had nothing to do with what you claim to have done.
Jan 2019 年 3 月 30 日
[MOVED] Sultan wrote on 28 Mar 2019 at 18:13.
Thanks John D'Errico!

サインインしてコメントする。

### Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by