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
-
2495 Solvers
-
1296 Solvers
-
Test if a Number is a Palindrome without using any String Operations
230 Solvers
-
Project Euler: Problem 3, Largest prime factor
1404 Solvers
-
Return elements unique to either input
763 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!