<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>