[postgis-devel] new constrained delauney triangulation

[Nicklas Avén]

Hi


Thanks for feedback!

On 3/11/19 6:45 PM, Darafei "Komяpa" Praliaskouski wrote:
>
> PostGIS is GPL2, your code is GPL3. Please change before I look at it 
> so I can still do something for PostGIS in Delaunay :)

Yes, you are right. I should put GPLv2+ on it. GPLv2 is not acceptable 
since PostGIS is distributed as GPLv2+, which would break.

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.

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.

TilelessMap is now GPL v3 and that should not be a problem if I license 
this code to GPLv2+.

I will do the change.


>
>     What I need is constrained triangulation, so I get only triangles
>     in the
>     polygons, not in between.
>
>
> This is cool. There's a hidden function in SFCGAL that does the CDT: 
> https://trac.osgeo.org/postgis/ticket/4198 - but in the end it's the 
> same algo as Tesselate?

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.


>
> CDT is needed for properly generating isochrones: 
> https://www.patreon.com/posts/isochrones-are-20933638 - so I would 
> love to see CDT in core replacing ST_DelaunayTriangles and helping to 
> iron the issues!
>
> CDT will also help replacing ST_ConcaveHull with a lot faster thing.

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


>     Anyway, what I need is also the possibility to get the result as
>     indexes
>     into the original point arrays. That is what the GPU wants. I haven't
>     implemented that yet, just because I couldn't wrap my head around
>     how to
>     create arrays in PostgreSQL.
>
>
> I believe this is also useful for compressed versions of TINs, that 
> should be stored as half edges.

Not sure what it means


>     I also have a plan to suggest an extension to the twkb-format so the
>     triangel indexes can be a part of a special geometry-type.
>
>
> TRIANGLE is already part of geometry. What if it was just supported in 
> serialization as is?

Yes, as uint32_t arrays


>
>     The new code now handles some invalidities. There are also
>     possibilities
>     to handle more.
>
>
> What do you use for inCircle predicate?
>
Not sure what you mean.

What it can handle is all valid polygons I have found so far.

And it also handles the situation when the boundary is touching itseld 
and constructing a hole, without proper inner rings.

It can also detect a crossing like an eight figure. Both when there is a 
point in the crossing and when it is not.

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.

Then it is just a matter of keeping the state of clockwise or counter 
clockwise and swapping that when crossing.

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.

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.

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.

I guess they are doing something like described above.

BTW, I am not sure, but some early tests seems to show that this code 
out performs MapBox earcut.hpp :-)

At least for bigger polygons. And I think it produces nicer triangles 
than the earcut algo (less sharp triangles).


>
>     Right now the code doesn't always stop gracefully if you find a
>     polygon
>     it cannot handle.
>
>     I have even had the code unstoppable, so I had to shut down the
>     machine.
>
>     So, be warned if yo want to test the code, it is a lot of error
>     handling
>     to do.
>
>
> 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.


Yes it would be very nice.

>
> Also, it is a single-geometry-input thing? Then we can make a fuzzer 
> for it and let Fuzzie look for the crashers.

It handles polygons and multi polygons.


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.

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

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.


Thanks

Nicklas






-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/postgis-devel/attachments/20190311/8d094ac1/attachment.html>