{"id":34442,"date":"2024-11-01T09:28:09","date_gmt":"2024-11-01T09:28:09","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=34442"},"modified":"2024-11-01T11:41:14","modified_gmt":"2024-11-01T11:41:14","slug":"javascript-coding-test-course-checking-the-intersection-of-line-segments","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/34442\/","title":{"rendered":"JavaScript Coding Test Course, Checking the Intersection of Line Segments"},"content":{"rendered":"<article>\n<p>Hello everyone! Today we will discuss one of the frequently encountered problems in JavaScript coding tests: &#8216;Determining if line segments intersect&#8217;. This problem is often asked in interviews and is very helpful in developing the ability to understand geometric concepts and implement them in code.<\/p>\n<h2>Problem Description<\/h2>\n<p>This problem is about determining whether two given line segments intersect. Each segment is defined by two points: segment A is represented by points A1(x1, y1) and A2(x2, y2), while segment B is represented by points B1(x3, y3) and B2(x4, y4). We need to determine whether these two segments intersect.<\/p>\n<h2>Input<\/h2>\n<ul>\n<li>A1: (x1, y1)<\/li>\n<li>A2: (x2, y2)<\/li>\n<li>B1: (x3, y3)<\/li>\n<li>B2: (x4, y4)<\/li>\n<\/ul>\n<h2>Output<\/h2>\n<p>If they intersect, the output should be <code>true<\/code>; otherwise, it should return <code>false<\/code>.<\/p>\n<h2>Examples<\/h2>\n<h3>Input Example<\/h3>\n<pre>\n    A1: (1, 1), A2: (4, 4)\n    B1: (1, 4), B2: (4, 1)\n  <\/pre>\n<h3>Output Example<\/h3>\n<pre>\n    true\n  <\/pre>\n<h2>Approach to the Problem<\/h2>\n<p>To solve this problem, we need to utilize some geometric concepts and algorithms. We will introduce two methods to determine whether the line segments intersect. The first method uses the area of a polygon, while the second utilizes the concept of the cross product of vectors.<\/p>\n<h3>1. Determining intersection using the cross product<\/h3>\n<p>To determine if the segments intersect, we use the cross product of vectors. If the cross product of two direction vectors A and B is greater than 0, they are on one side; if less than 0, they are on the opposite side.<\/p>\n<h4>Equation of a line<\/h4>\n<pre>\n    Let's define line segments A and B:\n    A: [(x1, y1), (x2, y2)]\n    B: [(x3, y3), (x4, y4)]\n  <\/pre>\n<h4>Cross product formula<\/h4>\n<p>The following cross product formula can be used for segments AB and AC:<\/p>\n<pre>\n    cross(A, B) = (A.x * B.y - A.y * B.x)\n  <\/pre>\n<h3>2. Determining intersection between a segment and a line<\/h3>\n<p>When given a segment, we can use another technique to determine if a specific line intersects the segment. This fundamentally involves reading the line defined by the endpoints of the segments and calculating the intersection.<\/p>\n<h2>Implementation Code<\/h2>\n<p>Now, let\u2019s implement the actual code using the methods described above.<\/p>\n<pre><code>\n    function isIntersect(A1, A2, B1, B2) {\n      const orientation = (p, q, r) =&gt; {\n        const val = (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1]);\n        if (val === 0) return 0; \/\/ collinear\n        return (val &gt; 0) ? 1 : 2; \/\/ clock or counterclockwise\n      };\n      \n      const onSegment = (p, q, r) =&gt; {\n        return (\n          q[0] &lt;= Math.max(p[0], r[0]) &amp;&amp;\n          q[0] &gt;= Math.min(p[0], r[0]) &amp;&amp;\n          q[1] &lt;= Math.max(p[1], r[1]) &amp;&amp;\n          q[1] &gt;= Math.min(p[1], r[1])\n        );\n      };\n      \n      const o1 = orientation(A1, A2, B1);\n      const o2 = orientation(A1, A2, B2);\n      const o3 = orientation(B1, B2, A1);\n      const o4 = orientation(B1, B2, A2);\n      \n      if (o1 !== o2 &amp;&amp; o3 !== o4) return true;\n      if (o1 === 0 &amp;&amp; onSegment(A1, B1, A2)) return true;\n      if (o2 === 0 &amp;&amp; onSegment(A1, B2, A2)) return true;\n      if (o3 === 0 &amp;&amp; onSegment(B1, A1, B2)) return true;\n      if (o4 === 0 &amp;&amp; onSegment(B1, A2, B2)) return true;\n\n      return false;\n    }\n\n    \/\/ Example usage\n    const A1 = [1, 1],\n          A2 = [4, 4],\n          B1 = [1, 4],\n          B2 = [4, 1];\n\n    console.log(isIntersect(A1, A2, B1, B2)); \/\/ true\n  <\/code><\/pre>\n<h2>Code Explanation<\/h2>\n<p>First, the <code>orientation<\/code> function determines the directionality of the three given points (p, q, r). This helps determine the intersection of segments A and B.<\/p>\n<p>Next, the <code>onSegment<\/code> function checks if the point q lies on the segment pr. After confirming the intersection, further checks are performed for specific cases (when all three points coincide).<\/p>\n<h2>Time Complexity<\/h2>\n<p>The time complexity of this algorithm is O(1) since the intersection can be determined with just one comparison.<\/p>\n<h2>Conclusion<\/h2>\n<p>In this tutorial, we explored an algorithm to determine the intersection of line segments using JavaScript. I hope this helps enhance your understanding of geometric problems and coding skills. I wish you the best in your interview preparation, and I look forward to seeing you in the next lesson!<\/p>\n<\/article>\n","protected":false},"excerpt":{"rendered":"<p>Hello everyone! Today we will discuss one of the frequently encountered problems in JavaScript coding tests: &#8216;Determining if line segments intersect&#8217;. This problem is often asked in interviews and is very helpful in developing the ability to understand geometric concepts and implement them in code. Problem Description This problem is about determining whether two given &hellip; <a href=\"https:\/\/atmokpo.com\/w\/34442\/\" class=\"more-link\">\ub354 \ubcf4\uae30<span class=\"screen-reader-text\"> &#8220;JavaScript Coding Test Course, Checking the Intersection of Line Segments&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[141],"tags":[],"class_list":["post-34442","post","type-post","status-publish","format-standard","hentry","category-javascript-coding-test"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v26.2 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>JavaScript Coding Test Course, Checking the Intersection of Line Segments - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8<\/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:\/\/atmokpo.com\/w\/34442\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"JavaScript Coding Test Course, Checking the Intersection of Line Segments - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"Hello everyone! Today we will discuss one of the frequently encountered problems in JavaScript coding tests: &#8216;Determining if line segments intersect&#8217;. This problem is often asked in interviews and is very helpful in developing the ability to understand geometric concepts and implement them in code. Problem Description This problem is about determining whether two given &hellip; \ub354 \ubcf4\uae30 &quot;JavaScript Coding Test Course, Checking the Intersection of Line Segments&quot;\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/34442\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:28:09+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T11:41:14+00:00\" \/>\n<meta name=\"author\" content=\"root\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:site\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:label1\" content=\"\uae00\uc4f4\uc774\" \/>\n\t<meta name=\"twitter:data1\" content=\"root\" \/>\n\t<meta name=\"twitter:label2\" content=\"\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04\" \/>\n\t<meta name=\"twitter:data2\" content=\"3\ubd84\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/atmokpo.com\/w\/34442\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34442\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"JavaScript Coding Test Course, Checking the Intersection of Line Segments\",\"datePublished\":\"2024-11-01T09:28:09+00:00\",\"dateModified\":\"2024-11-01T11:41:14+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34442\/\"},\"wordCount\":440,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"Javascript Coding Test\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/34442\/\",\"url\":\"https:\/\/atmokpo.com\/w\/34442\/\",\"name\":\"JavaScript Coding Test Course, Checking the Intersection of Line Segments - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:28:09+00:00\",\"dateModified\":\"2024-11-01T11:41:14+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34442\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/34442\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/34442\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"JavaScript Coding Test Course, Checking the Intersection of Line Segments\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/atmokpo.com\/w\/#website\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"description\":\"\",\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/atmokpo.com\/w\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"ko-KR\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"contentUrl\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"width\":400,\"height\":400,\"caption\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\"},\"image\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/x.com\/bebubo4\"]},{\"@type\":\"Person\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\",\"name\":\"root\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"caption\":\"root\"},\"sameAs\":[\"http:\/\/atmokpo.com\/w\"],\"url\":\"https:\/\/atmokpo.com\/w\/author\/root\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"JavaScript Coding Test Course, Checking the Intersection of Line Segments - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","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:\/\/atmokpo.com\/w\/34442\/","og_locale":"ko_KR","og_type":"article","og_title":"JavaScript Coding Test Course, Checking the Intersection of Line Segments - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"Hello everyone! Today we will discuss one of the frequently encountered problems in JavaScript coding tests: &#8216;Determining if line segments intersect&#8217;. This problem is often asked in interviews and is very helpful in developing the ability to understand geometric concepts and implement them in code. Problem Description This problem is about determining whether two given &hellip; \ub354 \ubcf4\uae30 \"JavaScript Coding Test Course, Checking the Intersection of Line Segments\"","og_url":"https:\/\/atmokpo.com\/w\/34442\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:28:09+00:00","article_modified_time":"2024-11-01T11:41:14+00:00","author":"root","twitter_card":"summary_large_image","twitter_creator":"@bebubo4","twitter_site":"@bebubo4","twitter_misc":{"\uae00\uc4f4\uc774":"root","\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04":"3\ubd84"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/atmokpo.com\/w\/34442\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/34442\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"JavaScript Coding Test Course, Checking the Intersection of Line Segments","datePublished":"2024-11-01T09:28:09+00:00","dateModified":"2024-11-01T11:41:14+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/34442\/"},"wordCount":440,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["Javascript Coding Test"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/34442\/","url":"https:\/\/atmokpo.com\/w\/34442\/","name":"JavaScript Coding Test Course, Checking the Intersection of Line Segments - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:28:09+00:00","dateModified":"2024-11-01T11:41:14+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/34442\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/34442\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/34442\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"JavaScript Coding Test Course, Checking the Intersection of Line Segments"}]},{"@type":"WebSite","@id":"https:\/\/atmokpo.com\/w\/#website","url":"https:\/\/atmokpo.com\/w\/","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","description":"","publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/atmokpo.com\/w\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"ko-KR"},{"@type":"Organization","@id":"https:\/\/atmokpo.com\/w\/#organization","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","url":"https:\/\/atmokpo.com\/w\/","logo":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/","url":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","contentUrl":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","width":400,"height":400,"caption":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8"},"image":{"@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/x.com\/bebubo4"]},{"@type":"Person","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7","name":"root","image":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","caption":"root"},"sameAs":["http:\/\/atmokpo.com\/w"],"url":"https:\/\/atmokpo.com\/w\/author\/root\/"}]}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34442","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/comments?post=34442"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34442\/revisions"}],"predecessor-version":[{"id":34443,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34442\/revisions\/34443"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=34442"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=34442"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=34442"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}