Problem 1456. Beads on a Necklace (Convex Hulls)

Created by Ned Gulley

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>We may describe a</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://en.wikipedia.org/wiki/Convex_hull\"><w:r><w:t>convex hull</w:t></w:r></w:hyperlink><w:r><w:t> 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</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://en.wikipedia.org/wiki/Convex_and_concave_polygons\"><w:r><w:t>convex polygon</w:t></w:r></w:hyperlink><w:r><w:t>.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>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.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>So, for example, the points below form a single convex hull.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ * *\n\n * *]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>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.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ *\n * \n * *]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Thus if</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ xy = [1 1;1 2;2 2;2 1]]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>then</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ allConvex(xy) => true]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Whereas</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ xy = [1 1;3 1;2 2;2 3]\n allConvex(xy) => false]]></w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

We may describe a <a href = "http://en.wikipedia.org/wiki/Convex_hull">convex hull</a> 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 <a href = "http://en.wikipedia.org/wiki/Convex_and_concave_polygons">convex polygon</a>.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.<pre> * *</pre><pre> * * </pre>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.<pre> *
 * 
 * *</pre>Thus if<pre> xy = [1 1;1 2;2 2;2 1]</pre>then<pre> allConvex(xy) => true</pre>Whereas<pre> xy = [1 1;3 1;2 2;2 3]
 allConvex(xy) => false</pre>

Solve

Solution Stats

101 Solutions
43 Solvers

Last Solution submitted on Jan 25, 2022

Last 200 Solutions

Problem Comments

Problem Recent Solvers43

Problem Tags

geometry

Community Treasure Hunt

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

Start Hunting!

Problem 1456. Beads on a Necklace (Convex Hulls)

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers43

Suggested Problems

More from this Author50

Problem Tags

Community Treasure Hunt

Problem 1456. Beads on a Necklace (Convex Hulls)

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers43

Suggested Problems

More from this Author50

Problem Tags

Community Treasure Hunt

Players