Problem 1456. Beads on a Necklace (Convex Hulls)
We may describe a convex hull as a rubber band stretched around a list of points. Some of the points will be inside the rubber band, and some will define vertices of (or lie along the edge of) a convex polygon.
Given an n-by-2 list of points xy where each row describes a point, your job is to determine if all the points belong to the convex hull for those points. In the matrix xy, the x coordinate is the first column and the y coordinate is the second column.
So, for example, the points below form a single convex hull.
* *
* *
In contrast, the points below do not, since the convex hull is a triangle that includes an interior point. Any polygon that includes all the points must necessarily be concave.
* * * *
Thus if
xy = [1 1;1 2;2 2;2 1]
then
allConvex(xy) => true
Whereas
xy = [1 1;3 1;2 2;2 3] allConvex(xy) => false
Solution Stats
Problem Comments
Solution Comments
Show commentsProblem Recent Solvers49
Suggested Problems
-
2715 Solvers
-
1263 Solvers
-
238 Solvers
-
107 Solvers
-
find the maximum element of the matrix
490 Solvers
More from this Author50
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!