Semi line collision with line segment











up vote
0
down vote

favorite












How to tell whether a semi straight line intersects with a line segment?



This is required because I am writing an algorithm to check if a given point lies inside or outside a polygon.



Update



Apparently semi straight line is also known by the name of ray.










share|cite|improve this question




























    up vote
    0
    down vote

    favorite












    How to tell whether a semi straight line intersects with a line segment?



    This is required because I am writing an algorithm to check if a given point lies inside or outside a polygon.



    Update



    Apparently semi straight line is also known by the name of ray.










    share|cite|improve this question


























      up vote
      0
      down vote

      favorite









      up vote
      0
      down vote

      favorite











      How to tell whether a semi straight line intersects with a line segment?



      This is required because I am writing an algorithm to check if a given point lies inside or outside a polygon.



      Update



      Apparently semi straight line is also known by the name of ray.










      share|cite|improve this question















      How to tell whether a semi straight line intersects with a line segment?



      This is required because I am writing an algorithm to check if a given point lies inside or outside a polygon.



      Update



      Apparently semi straight line is also known by the name of ray.







      geometry collision-detection






      share|cite|improve this question















      share|cite|improve this question













      share|cite|improve this question




      share|cite|improve this question








      edited 12 hours ago

























      asked 12 hours ago









      Răzvan Flavius Panda

      977




      977






















          2 Answers
          2






          active

          oldest

          votes

















          up vote
          0
          down vote













          Write the parametric equations of the full line (param. $t=0$ at the origin, and then positive for the part condidered) and that of the segment (param. $s=a$ at one end, $a<s=b$ at the other).



          Determine the crossing point and check if $0 le t$ and $a le s le b$.






          share|cite|improve this answer




























            up vote
            0
            down vote













            Let's say the line segment is between $vec{v}_1$ and $vec{v}_2$, and that the ray starts from $vec{o}$ in direction of $vec{d}$,
            $$bbox{vec{v}_1 = left[begin{matrix}x_1\y_1end{matrix}right]} , quad
            bbox{vec{v}_2 = left[begin{matrix}x_2\y_2end{matrix}right]} , quad
            bbox{vec{o} = left[begin{matrix}x_0\y_0end{matrix}right]} , quad
            bbox{vec{d} = left[begin{matrix}x_d\y_dend{matrix}right]}$$

            We can describe the points on the line segment as a vector-valued function, $vec{p}(t)$
            $$bbox{vec{p}(t) = (1 - t)vec{v}_1 + tvec{v}_2} , quad bbox{0 le t le 1}$$
            Similarly, we can describe the ray as a vector-valued function $vec{r}(tau)$,
            $$bbox{vec{r}(tau) = vec{o} + tau vec{d}}$$
            Their intersection is obviously
            $$bbox{vec{p}(t) = vec{r}(tau)}$$
            Now, remember that those are actually vector-valued functions, so that is actually a system of two linear equations:
            $$bbox{leftlbracebegin{aligned}
            x_o + tau x_d &= (1 - t) x_1 + t x_2 \
            y_o + tau y_d &= (1 - t) y_1 + t y_2 \
            end{aligned}right.} , quad bbox{ 0 le t le 1, ; ; tau ge 0 }$$

            This system has at most one solution,
            $$bbox{leftlbracebegin{aligned}
            displaystyle t &= frac{ y_d (x_1 - x_0) - x_d (y_1 - y_0)}{ x_d (y_2 - y_1) - y_d (x_2 - x_1) } \
            displaystyle tau &= frac{ x_0 (y_1 - y_2) + x_1 (y_2 - y_0) + x_2 (y_0 - y_1) }{ x_d (y_2 - y_1) - y_d (x_2 - x_1) } \
            end{aligned}right.}$$

            Note that they have the same divisor, which is zero if the ray and the line segment are parallel. You also need to verify that $0 le t le 1$ and $tau ge 0$ for the intersection to exist.



            If there is an intersection, it is at $vec{p}(t) = ( (1-t)x_0 + t x_1 ,, (1-t)y_0 + t y_1 )$, which is equivalent to $vec{r}(tau) = ( x_0 + tau x_d ,; y_0 + tau y_d )$.



            Note that although mathematically $(1-t) x_0 + t x_1 = x_0 + t (x_1 - x_0)$, the left side is more stable numerically. It means that if you use floating-point numbers, and $x_0$ and $x_1$ are vastly different in magnitude, the left side will still yield $x_0$ at $t=0$, and $x_1$ at $t=1$; but the right may not match $x_1$ at $t = 1$, because of the limited precision in floating-point numbers.





            The reason I showed the explicit solution above, is that in the real world, the point in polygon test is better solved using a winding number algorithm.



            The trick is that you only consider four directions, not any kind of angles:
            Cardinal winding directions



            You check each polygon edge in order. If the edge crosses the $x$ or $y$ coordinate of the test point, you check which side it does so. (In most cases, you only need to check the axis-aligned bounding box for the edge. In a very few cases, you need to check where the edge crosses the test point $x$ or $y$ coordinate, and in which order.)



            Instead of angles as in degrees, you consider a full turn to be four quarters. A line segment can cross the test point $x$, $y$, or both. If a line segment crosses both, you need to determine which one it crosses first. Then, you only need to remember which axis/direction was crossed last. (If none, then the point is completely outside the polygon.) If the next crossing is counterclockwise from the last one, increase the winding; if the next crossing is clockwise, decrease the winding; repeated crossings of the same direction does not affect the winding.



            If you calculated the crossings correctly, then winding will be an integer multiple of 4 (0, ±4, ±8, ±12, and so on). If the winding is 0, then the point is outside the polygon.



            There are two common definitions for "inside" for self-intersecting polygons: odd-even and nonzero. Odd-even means that if the winding is an odd number of turns (here, not an integer multiple of 8), the point is inside; otherwise it is outside. Nonzero means that if the winding is nonzero, the point is inside. If you consider a pentagram drawn using five lines, the difference between the two definitions is whether the pentagon at the center of the pentagram is "inside" or not. In nonzero it is inside, in odd-even it is outside.






            share|cite|improve this answer





















              Your Answer





              StackExchange.ifUsing("editor", function () {
              return StackExchange.using("mathjaxEditing", function () {
              StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
              StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
              });
              });
              }, "mathjax-editing");

              StackExchange.ready(function() {
              var channelOptions = {
              tags: "".split(" "),
              id: "69"
              };
              initTagRenderer("".split(" "), "".split(" "), channelOptions);

              StackExchange.using("externalEditor", function() {
              // Have to fire editor after snippets, if snippets enabled
              if (StackExchange.settings.snippets.snippetsEnabled) {
              StackExchange.using("snippets", function() {
              createEditor();
              });
              }
              else {
              createEditor();
              }
              });

              function createEditor() {
              StackExchange.prepareEditor({
              heartbeatType: 'answer',
              convertImagesToLinks: true,
              noModals: true,
              showLowRepImageUploadWarning: true,
              reputationToPostImages: 10,
              bindNavPrevention: true,
              postfix: "",
              imageUploader: {
              brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
              contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
              allowUrls: true
              },
              noCode: true, onDemand: true,
              discardSelector: ".discard-answer"
              ,immediatelyShowMarkdownHelp:true
              });


              }
              });














               

              draft saved


              draft discarded


















              StackExchange.ready(
              function () {
              StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3004392%2fsemi-line-collision-with-line-segment%23new-answer', 'question_page');
              }
              );

              Post as a guest















              Required, but never shown

























              2 Answers
              2






              active

              oldest

              votes








              2 Answers
              2






              active

              oldest

              votes









              active

              oldest

              votes






              active

              oldest

              votes








              up vote
              0
              down vote













              Write the parametric equations of the full line (param. $t=0$ at the origin, and then positive for the part condidered) and that of the segment (param. $s=a$ at one end, $a<s=b$ at the other).



              Determine the crossing point and check if $0 le t$ and $a le s le b$.






              share|cite|improve this answer

























                up vote
                0
                down vote













                Write the parametric equations of the full line (param. $t=0$ at the origin, and then positive for the part condidered) and that of the segment (param. $s=a$ at one end, $a<s=b$ at the other).



                Determine the crossing point and check if $0 le t$ and $a le s le b$.






                share|cite|improve this answer























                  up vote
                  0
                  down vote










                  up vote
                  0
                  down vote









                  Write the parametric equations of the full line (param. $t=0$ at the origin, and then positive for the part condidered) and that of the segment (param. $s=a$ at one end, $a<s=b$ at the other).



                  Determine the crossing point and check if $0 le t$ and $a le s le b$.






                  share|cite|improve this answer












                  Write the parametric equations of the full line (param. $t=0$ at the origin, and then positive for the part condidered) and that of the segment (param. $s=a$ at one end, $a<s=b$ at the other).



                  Determine the crossing point and check if $0 le t$ and $a le s le b$.







                  share|cite|improve this answer












                  share|cite|improve this answer



                  share|cite|improve this answer










                  answered 12 hours ago









                  G Cab

                  16.9k31237




                  16.9k31237






















                      up vote
                      0
                      down vote













                      Let's say the line segment is between $vec{v}_1$ and $vec{v}_2$, and that the ray starts from $vec{o}$ in direction of $vec{d}$,
                      $$bbox{vec{v}_1 = left[begin{matrix}x_1\y_1end{matrix}right]} , quad
                      bbox{vec{v}_2 = left[begin{matrix}x_2\y_2end{matrix}right]} , quad
                      bbox{vec{o} = left[begin{matrix}x_0\y_0end{matrix}right]} , quad
                      bbox{vec{d} = left[begin{matrix}x_d\y_dend{matrix}right]}$$

                      We can describe the points on the line segment as a vector-valued function, $vec{p}(t)$
                      $$bbox{vec{p}(t) = (1 - t)vec{v}_1 + tvec{v}_2} , quad bbox{0 le t le 1}$$
                      Similarly, we can describe the ray as a vector-valued function $vec{r}(tau)$,
                      $$bbox{vec{r}(tau) = vec{o} + tau vec{d}}$$
                      Their intersection is obviously
                      $$bbox{vec{p}(t) = vec{r}(tau)}$$
                      Now, remember that those are actually vector-valued functions, so that is actually a system of two linear equations:
                      $$bbox{leftlbracebegin{aligned}
                      x_o + tau x_d &= (1 - t) x_1 + t x_2 \
                      y_o + tau y_d &= (1 - t) y_1 + t y_2 \
                      end{aligned}right.} , quad bbox{ 0 le t le 1, ; ; tau ge 0 }$$

                      This system has at most one solution,
                      $$bbox{leftlbracebegin{aligned}
                      displaystyle t &= frac{ y_d (x_1 - x_0) - x_d (y_1 - y_0)}{ x_d (y_2 - y_1) - y_d (x_2 - x_1) } \
                      displaystyle tau &= frac{ x_0 (y_1 - y_2) + x_1 (y_2 - y_0) + x_2 (y_0 - y_1) }{ x_d (y_2 - y_1) - y_d (x_2 - x_1) } \
                      end{aligned}right.}$$

                      Note that they have the same divisor, which is zero if the ray and the line segment are parallel. You also need to verify that $0 le t le 1$ and $tau ge 0$ for the intersection to exist.



                      If there is an intersection, it is at $vec{p}(t) = ( (1-t)x_0 + t x_1 ,, (1-t)y_0 + t y_1 )$, which is equivalent to $vec{r}(tau) = ( x_0 + tau x_d ,; y_0 + tau y_d )$.



                      Note that although mathematically $(1-t) x_0 + t x_1 = x_0 + t (x_1 - x_0)$, the left side is more stable numerically. It means that if you use floating-point numbers, and $x_0$ and $x_1$ are vastly different in magnitude, the left side will still yield $x_0$ at $t=0$, and $x_1$ at $t=1$; but the right may not match $x_1$ at $t = 1$, because of the limited precision in floating-point numbers.





                      The reason I showed the explicit solution above, is that in the real world, the point in polygon test is better solved using a winding number algorithm.



                      The trick is that you only consider four directions, not any kind of angles:
                      Cardinal winding directions



                      You check each polygon edge in order. If the edge crosses the $x$ or $y$ coordinate of the test point, you check which side it does so. (In most cases, you only need to check the axis-aligned bounding box for the edge. In a very few cases, you need to check where the edge crosses the test point $x$ or $y$ coordinate, and in which order.)



                      Instead of angles as in degrees, you consider a full turn to be four quarters. A line segment can cross the test point $x$, $y$, or both. If a line segment crosses both, you need to determine which one it crosses first. Then, you only need to remember which axis/direction was crossed last. (If none, then the point is completely outside the polygon.) If the next crossing is counterclockwise from the last one, increase the winding; if the next crossing is clockwise, decrease the winding; repeated crossings of the same direction does not affect the winding.



                      If you calculated the crossings correctly, then winding will be an integer multiple of 4 (0, ±4, ±8, ±12, and so on). If the winding is 0, then the point is outside the polygon.



                      There are two common definitions for "inside" for self-intersecting polygons: odd-even and nonzero. Odd-even means that if the winding is an odd number of turns (here, not an integer multiple of 8), the point is inside; otherwise it is outside. Nonzero means that if the winding is nonzero, the point is inside. If you consider a pentagram drawn using five lines, the difference between the two definitions is whether the pentagon at the center of the pentagram is "inside" or not. In nonzero it is inside, in odd-even it is outside.






                      share|cite|improve this answer

























                        up vote
                        0
                        down vote













                        Let's say the line segment is between $vec{v}_1$ and $vec{v}_2$, and that the ray starts from $vec{o}$ in direction of $vec{d}$,
                        $$bbox{vec{v}_1 = left[begin{matrix}x_1\y_1end{matrix}right]} , quad
                        bbox{vec{v}_2 = left[begin{matrix}x_2\y_2end{matrix}right]} , quad
                        bbox{vec{o} = left[begin{matrix}x_0\y_0end{matrix}right]} , quad
                        bbox{vec{d} = left[begin{matrix}x_d\y_dend{matrix}right]}$$

                        We can describe the points on the line segment as a vector-valued function, $vec{p}(t)$
                        $$bbox{vec{p}(t) = (1 - t)vec{v}_1 + tvec{v}_2} , quad bbox{0 le t le 1}$$
                        Similarly, we can describe the ray as a vector-valued function $vec{r}(tau)$,
                        $$bbox{vec{r}(tau) = vec{o} + tau vec{d}}$$
                        Their intersection is obviously
                        $$bbox{vec{p}(t) = vec{r}(tau)}$$
                        Now, remember that those are actually vector-valued functions, so that is actually a system of two linear equations:
                        $$bbox{leftlbracebegin{aligned}
                        x_o + tau x_d &= (1 - t) x_1 + t x_2 \
                        y_o + tau y_d &= (1 - t) y_1 + t y_2 \
                        end{aligned}right.} , quad bbox{ 0 le t le 1, ; ; tau ge 0 }$$

                        This system has at most one solution,
                        $$bbox{leftlbracebegin{aligned}
                        displaystyle t &= frac{ y_d (x_1 - x_0) - x_d (y_1 - y_0)}{ x_d (y_2 - y_1) - y_d (x_2 - x_1) } \
                        displaystyle tau &= frac{ x_0 (y_1 - y_2) + x_1 (y_2 - y_0) + x_2 (y_0 - y_1) }{ x_d (y_2 - y_1) - y_d (x_2 - x_1) } \
                        end{aligned}right.}$$

                        Note that they have the same divisor, which is zero if the ray and the line segment are parallel. You also need to verify that $0 le t le 1$ and $tau ge 0$ for the intersection to exist.



                        If there is an intersection, it is at $vec{p}(t) = ( (1-t)x_0 + t x_1 ,, (1-t)y_0 + t y_1 )$, which is equivalent to $vec{r}(tau) = ( x_0 + tau x_d ,; y_0 + tau y_d )$.



                        Note that although mathematically $(1-t) x_0 + t x_1 = x_0 + t (x_1 - x_0)$, the left side is more stable numerically. It means that if you use floating-point numbers, and $x_0$ and $x_1$ are vastly different in magnitude, the left side will still yield $x_0$ at $t=0$, and $x_1$ at $t=1$; but the right may not match $x_1$ at $t = 1$, because of the limited precision in floating-point numbers.





                        The reason I showed the explicit solution above, is that in the real world, the point in polygon test is better solved using a winding number algorithm.



                        The trick is that you only consider four directions, not any kind of angles:
                        Cardinal winding directions



                        You check each polygon edge in order. If the edge crosses the $x$ or $y$ coordinate of the test point, you check which side it does so. (In most cases, you only need to check the axis-aligned bounding box for the edge. In a very few cases, you need to check where the edge crosses the test point $x$ or $y$ coordinate, and in which order.)



                        Instead of angles as in degrees, you consider a full turn to be four quarters. A line segment can cross the test point $x$, $y$, or both. If a line segment crosses both, you need to determine which one it crosses first. Then, you only need to remember which axis/direction was crossed last. (If none, then the point is completely outside the polygon.) If the next crossing is counterclockwise from the last one, increase the winding; if the next crossing is clockwise, decrease the winding; repeated crossings of the same direction does not affect the winding.



                        If you calculated the crossings correctly, then winding will be an integer multiple of 4 (0, ±4, ±8, ±12, and so on). If the winding is 0, then the point is outside the polygon.



                        There are two common definitions for "inside" for self-intersecting polygons: odd-even and nonzero. Odd-even means that if the winding is an odd number of turns (here, not an integer multiple of 8), the point is inside; otherwise it is outside. Nonzero means that if the winding is nonzero, the point is inside. If you consider a pentagram drawn using five lines, the difference between the two definitions is whether the pentagon at the center of the pentagram is "inside" or not. In nonzero it is inside, in odd-even it is outside.






                        share|cite|improve this answer























                          up vote
                          0
                          down vote










                          up vote
                          0
                          down vote









                          Let's say the line segment is between $vec{v}_1$ and $vec{v}_2$, and that the ray starts from $vec{o}$ in direction of $vec{d}$,
                          $$bbox{vec{v}_1 = left[begin{matrix}x_1\y_1end{matrix}right]} , quad
                          bbox{vec{v}_2 = left[begin{matrix}x_2\y_2end{matrix}right]} , quad
                          bbox{vec{o} = left[begin{matrix}x_0\y_0end{matrix}right]} , quad
                          bbox{vec{d} = left[begin{matrix}x_d\y_dend{matrix}right]}$$

                          We can describe the points on the line segment as a vector-valued function, $vec{p}(t)$
                          $$bbox{vec{p}(t) = (1 - t)vec{v}_1 + tvec{v}_2} , quad bbox{0 le t le 1}$$
                          Similarly, we can describe the ray as a vector-valued function $vec{r}(tau)$,
                          $$bbox{vec{r}(tau) = vec{o} + tau vec{d}}$$
                          Their intersection is obviously
                          $$bbox{vec{p}(t) = vec{r}(tau)}$$
                          Now, remember that those are actually vector-valued functions, so that is actually a system of two linear equations:
                          $$bbox{leftlbracebegin{aligned}
                          x_o + tau x_d &= (1 - t) x_1 + t x_2 \
                          y_o + tau y_d &= (1 - t) y_1 + t y_2 \
                          end{aligned}right.} , quad bbox{ 0 le t le 1, ; ; tau ge 0 }$$

                          This system has at most one solution,
                          $$bbox{leftlbracebegin{aligned}
                          displaystyle t &= frac{ y_d (x_1 - x_0) - x_d (y_1 - y_0)}{ x_d (y_2 - y_1) - y_d (x_2 - x_1) } \
                          displaystyle tau &= frac{ x_0 (y_1 - y_2) + x_1 (y_2 - y_0) + x_2 (y_0 - y_1) }{ x_d (y_2 - y_1) - y_d (x_2 - x_1) } \
                          end{aligned}right.}$$

                          Note that they have the same divisor, which is zero if the ray and the line segment are parallel. You also need to verify that $0 le t le 1$ and $tau ge 0$ for the intersection to exist.



                          If there is an intersection, it is at $vec{p}(t) = ( (1-t)x_0 + t x_1 ,, (1-t)y_0 + t y_1 )$, which is equivalent to $vec{r}(tau) = ( x_0 + tau x_d ,; y_0 + tau y_d )$.



                          Note that although mathematically $(1-t) x_0 + t x_1 = x_0 + t (x_1 - x_0)$, the left side is more stable numerically. It means that if you use floating-point numbers, and $x_0$ and $x_1$ are vastly different in magnitude, the left side will still yield $x_0$ at $t=0$, and $x_1$ at $t=1$; but the right may not match $x_1$ at $t = 1$, because of the limited precision in floating-point numbers.





                          The reason I showed the explicit solution above, is that in the real world, the point in polygon test is better solved using a winding number algorithm.



                          The trick is that you only consider four directions, not any kind of angles:
                          Cardinal winding directions



                          You check each polygon edge in order. If the edge crosses the $x$ or $y$ coordinate of the test point, you check which side it does so. (In most cases, you only need to check the axis-aligned bounding box for the edge. In a very few cases, you need to check where the edge crosses the test point $x$ or $y$ coordinate, and in which order.)



                          Instead of angles as in degrees, you consider a full turn to be four quarters. A line segment can cross the test point $x$, $y$, or both. If a line segment crosses both, you need to determine which one it crosses first. Then, you only need to remember which axis/direction was crossed last. (If none, then the point is completely outside the polygon.) If the next crossing is counterclockwise from the last one, increase the winding; if the next crossing is clockwise, decrease the winding; repeated crossings of the same direction does not affect the winding.



                          If you calculated the crossings correctly, then winding will be an integer multiple of 4 (0, ±4, ±8, ±12, and so on). If the winding is 0, then the point is outside the polygon.



                          There are two common definitions for "inside" for self-intersecting polygons: odd-even and nonzero. Odd-even means that if the winding is an odd number of turns (here, not an integer multiple of 8), the point is inside; otherwise it is outside. Nonzero means that if the winding is nonzero, the point is inside. If you consider a pentagram drawn using five lines, the difference between the two definitions is whether the pentagon at the center of the pentagram is "inside" or not. In nonzero it is inside, in odd-even it is outside.






                          share|cite|improve this answer












                          Let's say the line segment is between $vec{v}_1$ and $vec{v}_2$, and that the ray starts from $vec{o}$ in direction of $vec{d}$,
                          $$bbox{vec{v}_1 = left[begin{matrix}x_1\y_1end{matrix}right]} , quad
                          bbox{vec{v}_2 = left[begin{matrix}x_2\y_2end{matrix}right]} , quad
                          bbox{vec{o} = left[begin{matrix}x_0\y_0end{matrix}right]} , quad
                          bbox{vec{d} = left[begin{matrix}x_d\y_dend{matrix}right]}$$

                          We can describe the points on the line segment as a vector-valued function, $vec{p}(t)$
                          $$bbox{vec{p}(t) = (1 - t)vec{v}_1 + tvec{v}_2} , quad bbox{0 le t le 1}$$
                          Similarly, we can describe the ray as a vector-valued function $vec{r}(tau)$,
                          $$bbox{vec{r}(tau) = vec{o} + tau vec{d}}$$
                          Their intersection is obviously
                          $$bbox{vec{p}(t) = vec{r}(tau)}$$
                          Now, remember that those are actually vector-valued functions, so that is actually a system of two linear equations:
                          $$bbox{leftlbracebegin{aligned}
                          x_o + tau x_d &= (1 - t) x_1 + t x_2 \
                          y_o + tau y_d &= (1 - t) y_1 + t y_2 \
                          end{aligned}right.} , quad bbox{ 0 le t le 1, ; ; tau ge 0 }$$

                          This system has at most one solution,
                          $$bbox{leftlbracebegin{aligned}
                          displaystyle t &= frac{ y_d (x_1 - x_0) - x_d (y_1 - y_0)}{ x_d (y_2 - y_1) - y_d (x_2 - x_1) } \
                          displaystyle tau &= frac{ x_0 (y_1 - y_2) + x_1 (y_2 - y_0) + x_2 (y_0 - y_1) }{ x_d (y_2 - y_1) - y_d (x_2 - x_1) } \
                          end{aligned}right.}$$

                          Note that they have the same divisor, which is zero if the ray and the line segment are parallel. You also need to verify that $0 le t le 1$ and $tau ge 0$ for the intersection to exist.



                          If there is an intersection, it is at $vec{p}(t) = ( (1-t)x_0 + t x_1 ,, (1-t)y_0 + t y_1 )$, which is equivalent to $vec{r}(tau) = ( x_0 + tau x_d ,; y_0 + tau y_d )$.



                          Note that although mathematically $(1-t) x_0 + t x_1 = x_0 + t (x_1 - x_0)$, the left side is more stable numerically. It means that if you use floating-point numbers, and $x_0$ and $x_1$ are vastly different in magnitude, the left side will still yield $x_0$ at $t=0$, and $x_1$ at $t=1$; but the right may not match $x_1$ at $t = 1$, because of the limited precision in floating-point numbers.





                          The reason I showed the explicit solution above, is that in the real world, the point in polygon test is better solved using a winding number algorithm.



                          The trick is that you only consider four directions, not any kind of angles:
                          Cardinal winding directions



                          You check each polygon edge in order. If the edge crosses the $x$ or $y$ coordinate of the test point, you check which side it does so. (In most cases, you only need to check the axis-aligned bounding box for the edge. In a very few cases, you need to check where the edge crosses the test point $x$ or $y$ coordinate, and in which order.)



                          Instead of angles as in degrees, you consider a full turn to be four quarters. A line segment can cross the test point $x$, $y$, or both. If a line segment crosses both, you need to determine which one it crosses first. Then, you only need to remember which axis/direction was crossed last. (If none, then the point is completely outside the polygon.) If the next crossing is counterclockwise from the last one, increase the winding; if the next crossing is clockwise, decrease the winding; repeated crossings of the same direction does not affect the winding.



                          If you calculated the crossings correctly, then winding will be an integer multiple of 4 (0, ±4, ±8, ±12, and so on). If the winding is 0, then the point is outside the polygon.



                          There are two common definitions for "inside" for self-intersecting polygons: odd-even and nonzero. Odd-even means that if the winding is an odd number of turns (here, not an integer multiple of 8), the point is inside; otherwise it is outside. Nonzero means that if the winding is nonzero, the point is inside. If you consider a pentagram drawn using five lines, the difference between the two definitions is whether the pentagon at the center of the pentagram is "inside" or not. In nonzero it is inside, in odd-even it is outside.







                          share|cite|improve this answer












                          share|cite|improve this answer



                          share|cite|improve this answer










                          answered 6 hours ago









                          Nominal Animal

                          6,4852517




                          6,4852517






























                               

                              draft saved


                              draft discarded



















































                               


                              draft saved


                              draft discarded














                              StackExchange.ready(
                              function () {
                              StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3004392%2fsemi-line-collision-with-line-segment%23new-answer', 'question_page');
                              }
                              );

                              Post as a guest















                              Required, but never shown





















































                              Required, but never shown














                              Required, but never shown












                              Required, but never shown







                              Required, but never shown

































                              Required, but never shown














                              Required, but never shown












                              Required, but never shown







                              Required, but never shown







                              Popular posts from this blog

                              android studio warns about leanback feature tag usage required on manifest while using Unity exported app?

                              SQL update select statement

                              'app-layout' is not a known element: how to share Component with different Modules