Finding extreme points in the convex hull

2 views (last 30 days)
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.

Accepted Answer

John D'Errico
John D'Errico on 21 Mar 2019
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 Comments
John D'Errico
John D'Errico on 23 Mar 2019
Edited: John D'Errico on 23 Mar 2019
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);
>> discardList = setdiff(1:size(A,1),facets1)
discardList =
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
Jan on 30 Mar 2019
[MOVED] Sultan wrote on 28 Mar 2019 at 18:13.
Thanks John D'Errico!
@Sultan: Please use flags only to inform admins about contents, which conflict with the terms of use.

Sign in to comment.

More Answers (0)

Categories

Find more on Bounding Regions in Help Center and File Exchange

Community Treasure Hunt

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

Start Hunting!