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
-
Find the longest sequence of 1's in a binary sequence.
6129 Solvers
-
2104 Solvers
-
Return elements unique to either input
761 Solvers
-
Rotate input square matrix 90 degrees CCW without rot90
600 Solvers
-
Generate N equally spaced intervals between -L and L
854 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!