{"id":973,"date":"2020-07-19T20:00:16","date_gmt":"2020-07-19T20:00:16","guid":{"rendered":"https:\/\/www.parametriczoo.com\/?p=973"},"modified":"2020-07-19T20:06:21","modified_gmt":"2020-07-19T20:06:21","slug":"fit-an-arbitrary-polyline-into-a-given-rectangle","status":"publish","type":"post","link":"https:\/\/www.parametriczoo.com\/index.php\/2020\/07\/19\/fit-an-arbitrary-polyline-into-a-given-rectangle\/","title":{"rendered":"Fit an arbitrary set of points into a given rectangle."},"content":{"rendered":"

[et_pb_section fb_built=”1″ _builder_version=”3.22.7″][et_pb_row _builder_version=”3.22.7″][et_pb_column type=”4_4″ _builder_version=”3.22.7″][et_pb_text _builder_version=”3.22.7″]<\/p>\n

A simple problem : <\/strong><\/p>\n

Fit a flat set of points on XY plane into a given rectangle. Or in other words place the given rectangle around the set of points which contains all the points. In the same time determine if the problem has a solution or not?<\/span><\/p>\n

In this video I used Rhino+Grasshopper….<\/span><\/p>\n

[\/et_pb_text][et_pb_video src=”https:\/\/youtu.be\/pXTXsuFN8XU” _builder_version=”3.22.7″][\/et_pb_video][et_pb_text _builder_version=”3.22.7″]<\/p>\n

Note that this problem is different than finding the minimum bounding rectangle<\/a> of the poly-line which can be solved using Rotating calipers. <\/a><\/p>\n

In this problem we don’t need to find the rectangle but, find the transformation which places all the points inside the  rectangle. Such that transformation has two components, Rotation<\/strong> and Translation<\/strong>. In a 2D problem we can reduce the unknown to three variable r<\/strong>,x<\/strong> and y <\/strong>which represent the rotation amount (r<\/strong><\/em>) , and the x<\/strong><\/em> and y<\/em><\/strong> coordinates of the translation vector. Before we start thinking of a solution , we can reduce the problem further using convex hull of the points instead of the point set itself , simply because any points inside the convex hull will be automatically inside our rectangle.<\/p>\n

We define transformation A<\/strong> which transform all points of the convex hull P<\/strong> into a set Q<\/strong>: <\/p>\n

<\/b><\/p>\n

[\/et_pb_text][et_pb_image align=”center” width=”65%” src=”https:\/\/www.parametriczoo.com\/wp-content\/uploads\/2020\/07\/image001.png” _builder_version=”3.22.7″][\/et_pb_image][et_pb_text _builder_version=”3.22.7″]<\/p>\n

In order for all points in Q<\/strong> to be inside the rectangle (W,H)<\/strong><\/em> where W<\/strong> is the width along X<\/strong> axis and H<\/strong> is the height along Y<\/strong> axis, the following must be held for all points:<\/p>\n

[\/et_pb_text][et_pb_image align=”center” width=”75%” src=”https:\/\/www.parametriczoo.com\/wp-content\/uploads\/2020\/07\/image004.png” _builder_version=”3.22.7″][\/et_pb_image][et_pb_text _builder_version=”3.22.7″]<\/p>\n

In above q\u2093<\/strong><\/em> and q\u1d67<\/strong><\/em> are the X<\/strong> and Y<\/strong> coordinates of the point q<\/strong><\/em>. This is shown in the images below.<\/p>\n

The left image shows the convex hull P before transformation and in the right image you find the set Q<\/strong><\/em> after transformation in which all points are within the rectangle (W,H)<\/strong><\/em>:<\/p>\n

[\/et_pb_text][\/et_pb_column][\/et_pb_row][et_pb_row _builder_version=”3.22.7″][et_pb_column type=”1_2″ _builder_version=”3.22.7″][et_pb_image src=”https:\/\/www.parametriczoo.com\/wp-content\/uploads\/2020\/07\/before.png” _builder_version=”3.22.7″][\/et_pb_image][\/et_pb_column][et_pb_column type=”1_2″ _builder_version=”3.22.7″][et_pb_image src=”https:\/\/www.parametriczoo.com\/wp-content\/uploads\/2020\/07\/after-transformation.png” _builder_version=”3.22.7″][\/et_pb_image][\/et_pb_column][\/et_pb_row][et_pb_row _builder_version=”3.22.7″][et_pb_column type=”4_4″ _builder_version=”3.22.7″][et_pb_text _builder_version=”3.22.7″]<\/p>\n

Now we write the transformation A<\/strong><\/em> as product of its two component T\u2093,\u1d67<\/strong> for translation and R\u1d63<\/strong> for rotation . Note that T<\/strong> is a function of x<\/strong> <\/em>and y<\/strong><\/em> and R<\/strong><\/em> is a function of r<\/strong><\/em>, therefore we use the subscripts x,y<\/strong><\/em> and r<\/strong><\/em> to indicate that matrices T<\/strong> and R<\/strong> are depending on these variables.  <\/p>\n

[\/et_pb_text][et_pb_image align=”center” width=”86%” src=”https:\/\/www.parametriczoo.com\/wp-content\/uploads\/2020\/07\/image005-1.png” _builder_version=”3.22.7″][\/et_pb_image][et_pb_text _builder_version=”3.22.7″]<\/p>\n

We find the minimum rectangle along X<\/strong> and Y<\/strong> axis which contains all the points in Q<\/strong>. This can be achieved by creating two sets of real numbers from x<\/strong><\/em> and y<\/strong><\/em> components of the points in set Q<\/strong><\/em>.  <\/p>\n

[\/et_pb_text][et_pb_image align=”center” width=”80%” src=”https:\/\/www.parametriczoo.com\/wp-content\/uploads\/2020\/07\/image007-1.png” _builder_version=”3.22.7″][\/et_pb_image][et_pb_image align=”center” width=”80%” src=”https:\/\/www.parametriczoo.com\/wp-content\/uploads\/2020\/07\/image009-1.png” _builder_version=”3.22.7″][\/et_pb_image][et_pb_text _builder_version=”3.22.7″]<\/p>\n

The width of the min-rectangle is the difference between min and max in the set Q\u2081<\/strong> and in the same way the height of the min-rectangle could be found in set Q\u2082<\/strong>. <\/p>\n

[\/et_pb_text][et_pb_image align=”center” width=”80%” src=”https:\/\/www.parametriczoo.com\/wp-content\/uploads\/2020\/07\/image011-1.png” _builder_version=”3.22.7″][\/et_pb_image][et_pb_image align=”center” width=”80%” src=”https:\/\/www.parametriczoo.com\/wp-content\/uploads\/2020\/07\/image013-1.png” _builder_version=”3.22.7″][\/et_pb_image][et_pb_text _builder_version=”3.22.7″]<\/p>\n

Notice that the function \u0394(r)<\/strong> is independent from the x<\/strong> <\/em>and y<\/strong><\/em> variables.This is quiet obvious because the translation has no effect on the distance between the min and max point, in other words the displacement T<\/strong> moved the min point with the same amount and in the same direction as the max point , therefore it will cancel out in equation (5-1)<\/strong> and (5-2)<\/strong>.<\/p>\n

Below image demonstrate the function \u0394\u2093(r) <\/strong> and \u0394\u1d67(r)<\/strong> : <\/span><\/p>\n

[\/et_pb_text][et_pb_image align=”center” width=”53%” src=”https:\/\/www.parametriczoo.com\/wp-content\/uploads\/2020\/07\/min-rectangle.png” _builder_version=”3.22.7″][\/et_pb_image][et_pb_text _builder_version=”3.22.7″]<\/p>\n

The aim is find such r<\/strong> that the rectangle ( \u0394\u2093(r) , \u0394\u1d67(r) )<\/strong> as such that it fits inside the given rectangle (W,H)<\/strong> , hence we can write :<\/p>\n

[\/et_pb_text][et_pb_image align=”center” width=”69%” src=”https:\/\/www.parametriczoo.com\/wp-content\/uploads\/2020\/07\/image019.png” _builder_version=”3.22.7″][\/et_pb_image][et_pb_image align=”center” width=”69%” src=”https:\/\/www.parametriczoo.com\/wp-content\/uploads\/2020\/07\/image021.png” _builder_version=”3.22.7″][\/et_pb_image][et_pb_text _builder_version=”3.22.7″]<\/p>\n

\u2080This is a non-linear system of inequalities which can be solved by minimizing both w(r)<\/strong><\/em> and h(r)<\/strong><\/em> till both inequalities are satisfied. Looking at equations 5-1 and 5-2 it is also clear that the problem is non-differentiable.  The points that function are not differentiable is actually the points where one of the edges of convex hull P<\/strong> is aligned with either X<\/strong> or Y<\/strong> axis. To overcome this problem we must divide the domain of the function into the intervals which the bounding rectangle moves smoothly. This can be done by subdividing the domain at angles between one edge to the other. Note that the domain for r<\/strong><\/em> does not have to be [0,2\u03c0<\/span> ]<\/strong><\/em>. this is because rotating the poly-line P<\/strong><\/em> by 90 degree will swap the values of w(r)<\/strong> <\/em>and h(r)<\/strong><\/em> , therefore we can limit our search safely to the domain [0,\u03c0<\/span>]<\/strong><\/em> . <\/p>\n

In the future posts I propose an algorithm for solving the inequalities (6) and (7) and dividing the problem to a series of sub-domains where both functions are differentiable. Till then stay tuned…. <\/p>\n

[\/et_pb_text][\/et_pb_column][\/et_pb_row][\/et_pb_section]<\/p>\n","protected":false},"excerpt":{"rendered":"

A simple problem : Fit a flat set of points on XY plane into a given rectangle. Or in other words place the given rectangle around the set of points which contains all the points. In the same time determine if the problem has a solution or not? In this video I used Rhino+Grasshopper…. Note […]<\/p>\n","protected":false},"author":1,"featured_media":1024,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_et_pb_use_builder":"on","_et_pb_old_content":"","_et_gb_content_width":""},"categories":[60,46],"tags":[61,62],"yoast_head":"\nFit an arbitrary set of points into a given rectangle. - Parametric Zoo<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/www.parametriczoo.com\/index.php\/2020\/07\/19\/fit-an-arbitrary-polyline-into-a-given-rectangle\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Fit an arbitrary set of points into a given rectangle. - Parametric Zoo\" \/>\n<meta property=\"og:description\" content=\"A simple problem : Fit a flat set of points on XY plane into a given rectangle. Or in other words place the given rectangle around the set of points which contains all the points. In the same time determine if the problem has a solution or not? In this video I used Rhino+Grasshopper.... Note […]\" \/>\n<meta property=\"og:url\" content=\"https:\/\/www.parametriczoo.com\/index.php\/2020\/07\/19\/fit-an-arbitrary-polyline-into-a-given-rectangle\/\" \/>\n<meta property=\"og:site_name\" content=\"Parametric Zoo\" \/>\n<meta property=\"article:published_time\" content=\"2020-07-19T20:00:16+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2020-07-19T20:06:21+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/www.parametriczoo.com\/wp-content\/uploads\/2020\/07\/result-2.png\" \/>\n\t<meta property=\"og:image:width\" content=\"638\" \/>\n\t<meta property=\"og:image:height\" content=\"735\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/png\" \/>\n<meta name=\"author\" content=\"PARA\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"PARA\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"6 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebSite\",\"@id\":\"https:\/\/www.parametriczoo.com\/#website\",\"url\":\"https:\/\/www.parametriczoo.com\/\",\"name\":\"Parametric Zoo\",\"description\":\"\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/www.parametriczoo.com\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"en-US\"},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/www.parametriczoo.com\/index.php\/2020\/07\/19\/fit-an-arbitrary-polyline-into-a-given-rectangle\/#primaryimage\",\"url\":\"https:\/\/www.parametriczoo.com\/wp-content\/uploads\/2020\/07\/result-2.png\",\"contentUrl\":\"https:\/\/www.parametriczoo.com\/wp-content\/uploads\/2020\/07\/result-2.png\",\"width\":638,\"height\":735},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/www.parametriczoo.com\/index.php\/2020\/07\/19\/fit-an-arbitrary-polyline-into-a-given-rectangle\/\",\"url\":\"https:\/\/www.parametriczoo.com\/index.php\/2020\/07\/19\/fit-an-arbitrary-polyline-into-a-given-rectangle\/\",\"name\":\"Fit an arbitrary set of points into a given rectangle. - Parametric Zoo\",\"isPartOf\":{\"@id\":\"https:\/\/www.parametriczoo.com\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/www.parametriczoo.com\/index.php\/2020\/07\/19\/fit-an-arbitrary-polyline-into-a-given-rectangle\/#primaryimage\"},\"datePublished\":\"2020-07-19T20:00:16+00:00\",\"dateModified\":\"2020-07-19T20:06:21+00:00\",\"author\":{\"@id\":\"https:\/\/www.parametriczoo.com\/#\/schema\/person\/0368c6eb8bfe3a003504793be2a2e0e3\"},\"breadcrumb\":{\"@id\":\"https:\/\/www.parametriczoo.com\/index.php\/2020\/07\/19\/fit-an-arbitrary-polyline-into-a-given-rectangle\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/www.parametriczoo.com\/index.php\/2020\/07\/19\/fit-an-arbitrary-polyline-into-a-given-rectangle\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/www.parametriczoo.com\/index.php\/2020\/07\/19\/fit-an-arbitrary-polyline-into-a-given-rectangle\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/www.parametriczoo.com\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Fit an arbitrary set of points into a given rectangle.\"}]},{\"@type\":\"Person\",\"@id\":\"https:\/\/www.parametriczoo.com\/#\/schema\/person\/0368c6eb8bfe3a003504793be2a2e0e3\",\"name\":\"PARA\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/www.parametriczoo.com\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/2b2ff0ff40493545df12d0b31a504675?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/2b2ff0ff40493545df12d0b31a504675?s=96&d=mm&r=g\",\"caption\":\"PARA\"},\"url\":\"https:\/\/www.parametriczoo.com\/index.php\/author\/para\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Fit an arbitrary set of points into a given rectangle. - Parametric Zoo","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/www.parametriczoo.com\/index.php\/2020\/07\/19\/fit-an-arbitrary-polyline-into-a-given-rectangle\/","og_locale":"en_US","og_type":"article","og_title":"Fit an arbitrary set of points into a given rectangle. - Parametric Zoo","og_description":"A simple problem : Fit a flat set of points on XY plane into a given rectangle. Or in other words place the given rectangle around the set of points which contains all the points. In the same time determine if the problem has a solution or not? In this video I used Rhino+Grasshopper.... Note […]","og_url":"https:\/\/www.parametriczoo.com\/index.php\/2020\/07\/19\/fit-an-arbitrary-polyline-into-a-given-rectangle\/","og_site_name":"Parametric Zoo","article_published_time":"2020-07-19T20:00:16+00:00","article_modified_time":"2020-07-19T20:06:21+00:00","og_image":[{"width":638,"height":735,"url":"https:\/\/www.parametriczoo.com\/wp-content\/uploads\/2020\/07\/result-2.png","type":"image\/png"}],"author":"PARA","twitter_card":"summary_large_image","twitter_misc":{"Written by":"PARA","Est. reading time":"6 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebSite","@id":"https:\/\/www.parametriczoo.com\/#website","url":"https:\/\/www.parametriczoo.com\/","name":"Parametric Zoo","description":"","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/www.parametriczoo.com\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"en-US"},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/www.parametriczoo.com\/index.php\/2020\/07\/19\/fit-an-arbitrary-polyline-into-a-given-rectangle\/#primaryimage","url":"https:\/\/www.parametriczoo.com\/wp-content\/uploads\/2020\/07\/result-2.png","contentUrl":"https:\/\/www.parametriczoo.com\/wp-content\/uploads\/2020\/07\/result-2.png","width":638,"height":735},{"@type":"WebPage","@id":"https:\/\/www.parametriczoo.com\/index.php\/2020\/07\/19\/fit-an-arbitrary-polyline-into-a-given-rectangle\/","url":"https:\/\/www.parametriczoo.com\/index.php\/2020\/07\/19\/fit-an-arbitrary-polyline-into-a-given-rectangle\/","name":"Fit an arbitrary set of points into a given rectangle. - Parametric Zoo","isPartOf":{"@id":"https:\/\/www.parametriczoo.com\/#website"},"primaryImageOfPage":{"@id":"https:\/\/www.parametriczoo.com\/index.php\/2020\/07\/19\/fit-an-arbitrary-polyline-into-a-given-rectangle\/#primaryimage"},"datePublished":"2020-07-19T20:00:16+00:00","dateModified":"2020-07-19T20:06:21+00:00","author":{"@id":"https:\/\/www.parametriczoo.com\/#\/schema\/person\/0368c6eb8bfe3a003504793be2a2e0e3"},"breadcrumb":{"@id":"https:\/\/www.parametriczoo.com\/index.php\/2020\/07\/19\/fit-an-arbitrary-polyline-into-a-given-rectangle\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/www.parametriczoo.com\/index.php\/2020\/07\/19\/fit-an-arbitrary-polyline-into-a-given-rectangle\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/www.parametriczoo.com\/index.php\/2020\/07\/19\/fit-an-arbitrary-polyline-into-a-given-rectangle\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/www.parametriczoo.com\/"},{"@type":"ListItem","position":2,"name":"Fit an arbitrary set of points into a given rectangle."}]},{"@type":"Person","@id":"https:\/\/www.parametriczoo.com\/#\/schema\/person\/0368c6eb8bfe3a003504793be2a2e0e3","name":"PARA","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/www.parametriczoo.com\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/2b2ff0ff40493545df12d0b31a504675?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/2b2ff0ff40493545df12d0b31a504675?s=96&d=mm&r=g","caption":"PARA"},"url":"https:\/\/www.parametriczoo.com\/index.php\/author\/para\/"}]}},"jetpack_featured_media_url":"https:\/\/www.parametriczoo.com\/wp-content\/uploads\/2020\/07\/result-2.png","_links":{"self":[{"href":"https:\/\/www.parametriczoo.com\/index.php\/wp-json\/wp\/v2\/posts\/973"}],"collection":[{"href":"https:\/\/www.parametriczoo.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.parametriczoo.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.parametriczoo.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.parametriczoo.com\/index.php\/wp-json\/wp\/v2\/comments?post=973"}],"version-history":[{"count":0,"href":"https:\/\/www.parametriczoo.com\/index.php\/wp-json\/wp\/v2\/posts\/973\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.parametriczoo.com\/index.php\/wp-json\/wp\/v2\/media\/1024"}],"wp:attachment":[{"href":"https:\/\/www.parametriczoo.com\/index.php\/wp-json\/wp\/v2\/media?parent=973"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.parametriczoo.com\/index.php\/wp-json\/wp\/v2\/categories?post=973"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.parametriczoo.com\/index.php\/wp-json\/wp\/v2\/tags?post=973"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}