<html>
  <head>
    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
  </head>
  <body bgcolor="#FFFFFF" text="#000000">
    <p><br>
    </p>
    <div class="moz-cite-prefix">On 3/11/19 8:29 PM, Martin Davis wrote:<br>
    </div>
    <blockquote type="cite"
cite="mid:CAK2ens0BMPcCXzb1BtVEE4K5NH+z-Qh93yOd_34+gXyfxDKe6A@mail.gmail.com">
      <div dir="ltr">
        <div dir="ltr">
          <div>This looks impressive. </div>
          <div><br>
          </div>
          <div>I was going to suggest if all that was really needed was
            polygon triangulation then perhaps ear-clipping would be
            faster.  But if this is already faster...</div>
          <div><br>
          </div>
          <div>And yes, ear-clipping can produce very ugly
            triangulations.  For an approach to solving that see my blog
            post from a long time back: <a
href="http://lin-ear-th-inking.blogspot.com/2011/04/polygon-triangulation-via-ear-clipping.html">http://lin-ear-th-inking.blogspot.com/2011/04/polygon-triangulation-via-ear-clipping.html</a></div>
          <div><br>
          </div>
          <div>The risk of crashing hard is a bit of a worry though. Any
            idea if that can be fixed?</div>
        </div>
      </div>
    </blockquote>
    <p><br>
    </p>
    <p>Yes it should be possible to prevent. Most cases is just me
      haven't added proper handling.</p>
    <p>But the most annoying case is when searching the triangles I do
      it through the edges who have the triangles on both sides
      registered. <br>
    </p>
    <p>If there is a bug making the search just switch back and forth
      between two triangles it seems unstoppable. Maybe there is some
      magic code to put there, but I have had occations when kill pid
      haven't stopped it.</p>
    <p>So I have had to kill the machine or the VM (I am on Qubes so it
      is easy in my case).</p>
    <p>If it is just switching between 2 triangles it will be easy to
      put in a guard checking if that is happening. But if there might
      be any occasion when the search travels in a circle jumping over
      many triangles before getting back it will be harder.</p>
    <p>I cannot see what that situation could be, but there must be some
      way to handle also that or it might put a production server in a
      very bad state.</p>
    <p>But I think it is this way of searching that makes it so fast. A
      lot of things can be resolved in a very few steps this way.</p>
    <p>For instance when checking point in triangle, that function,
      instead of returning false (when point is not in the triangle) 
      returns a number from 1 to 3 telling what edge should be search on
      the opposite side to get closer to the point.</p>
    <p>So it can very fast do a recursive search and find the point.
      Since the points are added in the order of the boundary the next
      point is seldom far away, so it is just a few iterations.<br>
    </p>
    <p><br>
    </p>
    <p><br>
    </p>
    <p><br>
    </p>
    <blockquote type="cite"
cite="mid:CAK2ens0BMPcCXzb1BtVEE4K5NH+z-Qh93yOd_34+gXyfxDKe6A@mail.gmail.com">
      <div dir="ltr">
        <div dir="ltr"><br>
          <div class="gmail_quote">
            <div dir="ltr" class="gmail_attr">On Mon, Mar 11, 2019 at
              11:44 AM Nicklas Avén <<a
                href="mailto:nicklas.aven@jordogskog.no">nicklas.aven@jordogskog.no</a>>
              wrote:</div>
            <blockquote class="gmail_quote" style="margin:0px 0px 0px
              0.8ex;border-left:1px solid
              rgb(204,204,204);padding-left:1ex">
              <div bgcolor="#FFFFFF">
                <p>I hope Martin also gets the chance to take a look. He
                  managed to review my homemade faster distance
                  algorithm almost a decade ago. Still glad for that
                  review :-)</p>
              </div>
            </blockquote>
            <div>I'll look forward to reviewing this, and reading
              through the paper.   <br>
            </div>
          </div>
        </div>
      </div>
    </blockquote>
    <p>Thanks! I will try to make it more readable, but it will take a
      few days before I get the time.</p>
    <p><br>
    </p>
    <p><br>
    </p>
    <p>/Nicklas<br>
    </p>
    <br>
    <p><br>
    </p>
    <blockquote type="cite"
cite="mid:CAK2ens0BMPcCXzb1BtVEE4K5NH+z-Qh93yOd_34+gXyfxDKe6A@mail.gmail.com">
      <div dir="ltr">
        <div dir="ltr">
          <div class="gmail_quote">
            <blockquote class="gmail_quote" style="margin:0px 0px 0px
              0.8ex;border-left:1px solid
              rgb(204,204,204);padding-left:1ex">
              _______________________________________________<br>
              postgis-devel mailing list<br>
              <a href="mailto:postgis-devel@lists.osgeo.org"
                target="_blank">postgis-devel@lists.osgeo.org</a><br>
              <a
                href="https://lists.osgeo.org/mailman/listinfo/postgis-devel"
                rel="noreferrer" target="_blank">https://lists.osgeo.org/mailman/listinfo/postgis-devel</a></blockquote>
          </div>
        </div>
      </div>
      <br>
      <fieldset class="mimeAttachmentHeader"></fieldset>
      <pre class="moz-quote-pre" wrap="">_______________________________________________
postgis-devel mailing list
<a class="moz-txt-link-abbreviated" href="mailto:postgis-devel@lists.osgeo.org">postgis-devel@lists.osgeo.org</a>
<a class="moz-txt-link-freetext" href="https://lists.osgeo.org/mailman/listinfo/postgis-devel">https://lists.osgeo.org/mailman/listinfo/postgis-devel</a></pre>
    </blockquote>
  </body>
</html>