Problem 44059. Convex Hull Capture

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>Imagine four points in uv that form a square.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ uv = [ ...\n    0,0;\n    0,2;\n    2,2;\n    2,0];]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Now we have two more points in xy: one at [1,1] and the other at [1,3]. The first one is in the square, and the second is outside it.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ xy = [ ...\n    1,1;\n    3,1];]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Here is the challenge. Consider the</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"https://en.wikipedia.org/wiki/Convex_hull\"><w:r><w:t>convex hull</w:t></w:r></w:hyperlink><w:r><w:t> formed by the points in uv. Which points in xy lie inside this hull?</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>In this case, the answer would be the logical vector [1,0], since the first row of xy is in the box defined by uv, whereas the second row is not.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Example</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ uv = [13,12;10,18;8,4;12,10;16,4;13,2;];\n xy = [12,15;9,7;9,13;13,8;];\n\n in_correct = [0;1;0;1;];]]></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>"}]}

Solve

Solution Stats

44 Solutions
19 Solvers

Last Solution submitted on Jun 30, 2020

Last 200 Solutions

Problem Comments

1 Comment

1 Comment

Peng Liu on 1 Feb 2017

This problem may be generalized to a more challenging case: the N-D convex hull.

Problem Recent Solvers19

Problem Tags

geometry

Problem 44059. Convex Hull Capture

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers19

Suggested Problems

More from this Author49

Problem Tags

Problem 44059. Convex Hull Capture

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers19

Suggested Problems

More from this Author49

Problem Tags

Players