[postgis-devel] new constrained delauney triangulation

[Nicklas Avén]

On 3/11/19 8:29 PM, Martin Davis wrote:
> This looks impressive.
>
> 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...
>
> And yes, ear-clipping can produce very ugly triangulations.  For an 
> approach to solving that see my blog post from a long time back: 
> http://lin-ear-th-inking.blogspot.com/2011/04/polygon-triangulation-via-ear-clipping.html
>
> The risk of crashing hard is a bit of a worry though. Any idea if that 
> can be fixed?


Yes it should be possible to prevent. Most cases is just me haven't 
added proper handling.

But the most annoying case is when searching the triangles I do it 
through the edges who have the triangles on both sides registered.

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.

So I have had to kill the machine or the VM (I am on Qubes so it is easy 
in my case).

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.

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.

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.

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.

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.




>
> On Mon, Mar 11, 2019 at 11:44 AM Nicklas Avén 
> <nicklas.aven at jordogskog.no <mailto:nicklas.aven at jordogskog.no>> wrote:
>
>     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 :-)
>
> I'll look forward to reviewing this, and reading through the paper.

Thanks! I will try to make it more readable, but it will take a few days 
before I get the time.



/Nicklas



>     _______________________________________________
>     postgis-devel mailing list
>     postgis-devel at lists.osgeo.org <mailto:postgis-devel at lists.osgeo.org>
>     https://lists.osgeo.org/mailman/listinfo/postgis-devel
>
>
> _______________________________________________
> postgis-devel mailing list
> postgis-devel at lists.osgeo.org
> https://lists.osgeo.org/mailman/listinfo/postgis-devel
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/postgis-devel/attachments/20190311/4701033f/attachment.html>