<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<p>Hi</p>
<p><br>
</p>
<p>Thanks for feedback!<br>
</p>
<div class="moz-cite-prefix">On 3/11/19 6:45 PM, Darafei "Komяpa"
Praliaskouski wrote:<br>
</div>
<blockquote type="cite"
cite="mid:CAC8Q8tJLjoz61iczMRVT-nO+Ba-N=N-hMwjMzOQxQuNG+VtJMA@mail.gmail.com">
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<div dir="ltr">
<div dir="ltr">
<div dir="ltr">
<div class="gmail_quote"><br>
<div>PostGIS is GPL2, your code is GPL3. Please change
before I look at it so I can still do something for
PostGIS in Delaunay :)</div>
</div>
</div>
</div>
</div>
</blockquote>
<p>Yes, you are right. I should put GPLv2+ on it. GPLv2 is not
acceptable since PostGIS is distributed as GPLv2+, which would
break.</p>
<p>This license thing is a horror sometimes. I will have to keep the
code I have now that I can relicense (since I am the only
contributor so far) since I want to include it in TilelessMap. If
then I want it to be usable for our Apple-friends, from what I
understand it must be a more permissive license than the GPL.</p>
<p>I want it in GPL, but I also want it to be usable for those poor
people choosing to be locked in by Apple ;-) . And Apples
infrastructure for iPhone and iPad isn't compatible with GPL from
what I have read. For Android I have it on F-Droid.<br>
</p>
<p>TilelessMap is now GPL v3 and that should not be a problem if I
license this code to GPLv2+.</p>
<p>I will do the change.<br>
</p>
<p><br>
</p>
<blockquote type="cite"
cite="mid:CAC8Q8tJLjoz61iczMRVT-nO+Ba-N=N-hMwjMzOQxQuNG+VtJMA@mail.gmail.com">
<div dir="ltr">
<div dir="ltr">
<div dir="ltr">
<div class="gmail_quote"><br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px
0.8ex;border-left:1px solid
rgb(204,204,204);padding-left:1ex">
What I need is constrained triangulation, so I get only
triangles in the <br>
polygons, not in between.<br>
</blockquote>
<div><br>
</div>
<div>This is cool. There's a hidden function in SFCGAL
that does the CDT: <a
href="https://trac.osgeo.org/postgis/ticket/4198"
moz-do-not-send="true">https://trac.osgeo.org/postgis/ticket/4198</a>
- but in the end it's the same algo as Tesselate?</div>
</div>
</div>
</div>
</div>
</blockquote>
<p>I don't know. I just guess that SFCGAL Tesselate is written for
handling 3D which might be the reason this new code is almost 1000
times faster for larger polygons.<br>
</p>
<p><br>
</p>
<blockquote type="cite"
cite="mid:CAC8Q8tJLjoz61iczMRVT-nO+Ba-N=N-hMwjMzOQxQuNG+VtJMA@mail.gmail.com">
<div dir="ltr">
<div dir="ltr">
<div dir="ltr">
<div class="gmail_quote">
<div><br>
</div>
<div>CDT is needed for properly generating isochrones: <a
href="https://www.patreon.com/posts/isochrones-are-20933638"
moz-do-not-send="true">https://www.patreon.com/posts/isochrones-are-20933638</a>
- so I would love to see CDT in core replacing
ST_DelaunayTriangles and helping to iron the issues!</div>
<div><br>
</div>
<div>CDT will also help replacing ST_ConcaveHull with a
lot faster thing. <br>
</div>
</div>
</div>
</div>
</div>
</blockquote>
<p>Please give it a try :-) It is prepared as a postgis extension.
Just compile and run, but be aware about lacking error handling so
it might crash hard<br>
</p>
<br>
<blockquote type="cite"
cite="mid:CAC8Q8tJLjoz61iczMRVT-nO+Ba-N=N-hMwjMzOQxQuNG+VtJMA@mail.gmail.com">
<div dir="ltr">
<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">
Anyway, what I need is also the possibility to get the
result as indexes <br>
into the original point arrays. That is what the GPU
wants. I haven't <br>
implemented that yet, just because I couldn't wrap my
head around how to <br>
create arrays in PostgreSQL.<br>
</blockquote>
<div><br>
</div>
<div>I believe this is also useful for compressed versions
of TINs, that should be stored as half edges.</div>
</div>
</div>
</div>
</div>
</blockquote>
<p>Not sure what it means<br>
</p>
<p><br>
</p>
<blockquote type="cite"
cite="mid:CAC8Q8tJLjoz61iczMRVT-nO+Ba-N=N-hMwjMzOQxQuNG+VtJMA@mail.gmail.com">
<div dir="ltr">
<div dir="ltr">
<div dir="ltr">
<div class="gmail_quote">
<div> </div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px
0.8ex;border-left:1px solid
rgb(204,204,204);padding-left:1ex">I also have a plan to
suggest an extension to the twkb-format so the <br>
triangel indexes can be a part of a special
geometry-type.<br>
</blockquote>
<div><br>
</div>
<div>TRIANGLE is already part of geometry. What if it was
just supported in serialization as is?</div>
</div>
</div>
</div>
</div>
</blockquote>
<p>Yes, as uint32_t arrays<br>
</p>
<br>
<blockquote type="cite"
cite="mid:CAC8Q8tJLjoz61iczMRVT-nO+Ba-N=N-hMwjMzOQxQuNG+VtJMA@mail.gmail.com">
<div dir="ltr">
<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>
The new code now handles some invalidities. There are
also possibilities <br>
to handle more.<br>
</blockquote>
<div><br>
</div>
<div>What do you use for inCircle predicate?</div>
<div><br>
</div>
</div>
</div>
</div>
</div>
</blockquote>
<p>Not sure what you mean.</p>
<p>What it can handle is all valid polygons I have found so far.</p>
<p>And it also handles the situation when the boundary is touching
itseld and constructing a hole, without proper inner rings.</p>
<p>It can also detect a crossing like an eight figure. Both when
there is a point in the crossing and when it is not.</p>
<p>But those two last cases isn't handled. They are just detected.
But at least for the case with crossing through a point it should
be fairly easy to handle. <br>
</p>
<p>Then it is just a matter of keeping the state of clockwise or
counter clockwise and swapping that when crossing.</p>
<p>For the case without a point it is a bit harder. If adding a
point it will break the indexes into the boundary, if not a new
point array with the new point included is delivered too.</p>
<p>If not adding a point we have to change what the polygon will
look like. But I anyway think that is the base. To connect the
triangles to the closest of the existing vertex points in the
crossing. <br>
</p>
<p>If the result is only for rendering that will in most cases be
acceptable. If it is not acceptable the original polygon should be
fixed. MapBox earcut claims to fix those situations without adding
any new point.</p>
<p>I guess they are doing something like described above.</p>
<p>BTW, I am not sure, but some early tests seems to show that this
code out performs MapBox earcut.hpp :-) <br>
</p>
<p>At least for bigger polygons. And I think it produces nicer
triangles than the earcut algo (less sharp triangles).<br>
</p>
<p><br>
</p>
<blockquote type="cite"
cite="mid:CAC8Q8tJLjoz61iczMRVT-nO+Ba-N=N-hMwjMzOQxQuNG+VtJMA@mail.gmail.com">
<div dir="ltr">
<div dir="ltr">
<div dir="ltr">
<div class="gmail_quote">
<div> </div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px
0.8ex;border-left:1px solid
rgb(204,204,204);padding-left:1ex">
<br>
Right now the code doesn't always stop gracefully if you
find a polygon <br>
it cannot handle.<br>
<br>
I have even had the code unstoppable, so I had to shut
down the machine.<br>
<br>
So, be warned if yo want to test the code, it is a lot
of error handling <br>
to do.<br>
</blockquote>
<div><br>
</div>
<div>Would be cool if it can be made a part of PostGIS.
Then we can utilize the coverage infrastructure making
sure we can generate tests.</div>
</div>
</div>
</div>
</div>
</blockquote>
<p><br>
</p>
<p>Yes it would be very nice.</p>
<blockquote type="cite"
cite="mid:CAC8Q8tJLjoz61iczMRVT-nO+Ba-N=N-hMwjMzOQxQuNG+VtJMA@mail.gmail.com">
<div dir="ltr">
<div dir="ltr">
<div dir="ltr">
<div class="gmail_quote">
<div><br>
</div>
<div>Also, it is a single-geometry-input thing? Then we
can make a fuzzer for it and let Fuzzie look for the
crashers. <br>
</div>
</div>
</div>
</div>
</div>
</blockquote>
<p>It handles polygons and multi polygons. <br>
</p>
<p><br>
</p>
<p>I will change the license, and I will try to get time to do some
cleanup and proper commenting so it is easier to follow what is
happening, so we can get most ugly bugs squeezed away before I add
it to core, if we agree on doing that.</p>
<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>
<p>To understand what is happening here I think it is crucial to
follow the paper I linked. It is a very nice algorithm S.W. Sloan
designed back then. All credit to him.</p>
<p><br>
</p>
<p>Thanks</p>
<p>Nicklas<br>
</p>
<p><br>
</p>
<p><br>
</p>
<p><br>
</p>
<p><br>
</p>
<p><br>
</p>
</body>
</html>