{"id":1076,"date":"2021-05-24T16:03:13","date_gmt":"2021-05-24T16:03:13","guid":{"rendered":"https:\/\/www.parametriczoo.com\/?p=1076"},"modified":"2021-05-24T16:13:19","modified_gmt":"2021-05-24T16:13:19","slug":"doubly-connected-edge-lists","status":"publish","type":"post","link":"https:\/\/www.parametriczoo.com\/index.php\/2021\/05\/24\/doubly-connected-edge-lists\/","title":{"rendered":"Doubly Connected Edge Lists"},"content":{"rendered":"<p>[et_pb_section fb_built=&#8221;1&#8243; _builder_version=&#8221;3.22.7&#8243;][et_pb_row custom_margin=&#8221;-6px|auto||auto||&#8221; _builder_version=&#8221;3.22.7&#8243;][et_pb_column type=&#8221;4_4&#8243; _builder_version=&#8221;3.22.7&#8243;][et_pb_image src=&#8221;https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/0\/07\/Dcel-halfedge-connectivity.svg\/330px-Dcel-halfedge-connectivity.svg.png&#8221; _builder_version=&#8221;3.22.7&#8243;][\/et_pb_image][et_pb_text _builder_version=&#8221;3.22.7&#8243;]<\/p>\n<p><span>DCEL (doubly connected edge list) is very useful data structure which provides linear access to various components of a flat graph. I looked for an implementation in C# , but I couldn&#8217;t find one, so I decided to re-write my C++ code in DotNet framework and now here you have a simple , brief version of it. <\/span><\/p>\n<p>[\/et_pb_text][et_pb_button button_url=&#8221;https:\/\/github.com\/Torabi\/DoublyConnectedEdgeList&#8221; button_text=&#8221;GItHub&#8221; button_alignment=&#8221;center&#8221; _builder_version=&#8221;3.22.7&#8243; custom_button=&#8221;on&#8221; button_font=&#8221;||||||||&#8221; button_text_size=&#8221;20px&#8221; button_border_width=&#8221;3px&#8221;][\/et_pb_button][et_pb_text _builder_version=&#8221;3.22.7&#8243;]<\/p>\n<p><span>Below is an example of the usage, The polygon is first triangulated\u00a0and then using a doubly connected edge list is decomposed to sub-convex-polygons. In each step an edge is removed from the graph which the sum of the angles on each end will be less than 180 degree after removal. This way you can achieve the decomposition in linear time when the DCEL provides access to different objects (node\/edge and faces ) of graph also in a linear time.<\/span><\/p>\n<p>[\/et_pb_text][et_pb_video src=&#8221;https:\/\/youtu.be\/kIOwXa_G94s&#8221; _builder_version=&#8221;3.22.7&#8243;][\/et_pb_video][\/et_pb_column][\/et_pb_row][\/et_pb_section]<\/p>\n","protected":false},"excerpt":{"rendered":"<p>DCEL (doubly connected edge list) is very useful data structure which provides linear access to various components of a flat graph. I looked for an implementation in C# , but I couldn&#8217;t find one, so I decided to re-write my C++ code in DotNet framework and now here you have a simple , brief version [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"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":[],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v19.3 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>Doubly Connected Edge Lists - 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\/2021\/05\/24\/doubly-connected-edge-lists\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Doubly Connected Edge Lists - Parametric Zoo\" \/>\n<meta property=\"og:description\" content=\"DCEL (doubly connected edge list) is very useful data structure which provides linear access to various components of a flat graph. I looked for an implementation in C# , but I couldn&#039;t find one, so I decided to re-write my C++ code in DotNet framework and now here you have a simple , brief version [&hellip;]\" \/>\n<meta property=\"og:url\" content=\"https:\/\/www.parametriczoo.com\/index.php\/2021\/05\/24\/doubly-connected-edge-lists\/\" \/>\n<meta property=\"og:site_name\" content=\"Parametric Zoo\" \/>\n<meta property=\"article:published_time\" content=\"2021-05-24T16:03:13+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2021-05-24T16:13:19+00:00\" \/>\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=\"1 minute\" \/>\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\":\"WebPage\",\"@id\":\"https:\/\/www.parametriczoo.com\/index.php\/2021\/05\/24\/doubly-connected-edge-lists\/\",\"url\":\"https:\/\/www.parametriczoo.com\/index.php\/2021\/05\/24\/doubly-connected-edge-lists\/\",\"name\":\"Doubly Connected Edge Lists - Parametric Zoo\",\"isPartOf\":{\"@id\":\"https:\/\/www.parametriczoo.com\/#website\"},\"datePublished\":\"2021-05-24T16:03:13+00:00\",\"dateModified\":\"2021-05-24T16:13:19+00:00\",\"author\":{\"@id\":\"https:\/\/www.parametriczoo.com\/#\/schema\/person\/0368c6eb8bfe3a003504793be2a2e0e3\"},\"breadcrumb\":{\"@id\":\"https:\/\/www.parametriczoo.com\/index.php\/2021\/05\/24\/doubly-connected-edge-lists\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/www.parametriczoo.com\/index.php\/2021\/05\/24\/doubly-connected-edge-lists\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/www.parametriczoo.com\/index.php\/2021\/05\/24\/doubly-connected-edge-lists\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/www.parametriczoo.com\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Doubly Connected Edge Lists\"}]},{\"@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":"Doubly Connected Edge Lists - 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\/2021\/05\/24\/doubly-connected-edge-lists\/","og_locale":"en_US","og_type":"article","og_title":"Doubly Connected Edge Lists - Parametric Zoo","og_description":"DCEL (doubly connected edge list) is very useful data structure which provides linear access to various components of a flat graph. I looked for an implementation in C# , but I couldn't find one, so I decided to re-write my C++ code in DotNet framework and now here you have a simple , brief version [&hellip;]","og_url":"https:\/\/www.parametriczoo.com\/index.php\/2021\/05\/24\/doubly-connected-edge-lists\/","og_site_name":"Parametric Zoo","article_published_time":"2021-05-24T16:03:13+00:00","article_modified_time":"2021-05-24T16:13:19+00:00","author":"PARA","twitter_card":"summary_large_image","twitter_misc":{"Written by":"PARA","Est. reading time":"1 minute"},"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":"WebPage","@id":"https:\/\/www.parametriczoo.com\/index.php\/2021\/05\/24\/doubly-connected-edge-lists\/","url":"https:\/\/www.parametriczoo.com\/index.php\/2021\/05\/24\/doubly-connected-edge-lists\/","name":"Doubly Connected Edge Lists - Parametric Zoo","isPartOf":{"@id":"https:\/\/www.parametriczoo.com\/#website"},"datePublished":"2021-05-24T16:03:13+00:00","dateModified":"2021-05-24T16:13:19+00:00","author":{"@id":"https:\/\/www.parametriczoo.com\/#\/schema\/person\/0368c6eb8bfe3a003504793be2a2e0e3"},"breadcrumb":{"@id":"https:\/\/www.parametriczoo.com\/index.php\/2021\/05\/24\/doubly-connected-edge-lists\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/www.parametriczoo.com\/index.php\/2021\/05\/24\/doubly-connected-edge-lists\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/www.parametriczoo.com\/index.php\/2021\/05\/24\/doubly-connected-edge-lists\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/www.parametriczoo.com\/"},{"@type":"ListItem","position":2,"name":"Doubly Connected Edge Lists"}]},{"@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":"","_links":{"self":[{"href":"https:\/\/www.parametriczoo.com\/index.php\/wp-json\/wp\/v2\/posts\/1076"}],"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=1076"}],"version-history":[{"count":0,"href":"https:\/\/www.parametriczoo.com\/index.php\/wp-json\/wp\/v2\/posts\/1076\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.parametriczoo.com\/index.php\/wp-json\/wp\/v2\/media?parent=1076"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.parametriczoo.com\/index.php\/wp-json\/wp\/v2\/categories?post=1076"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.parametriczoo.com\/index.php\/wp-json\/wp\/v2\/tags?post=1076"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}