Vertices of triangles as indexes of original points

[dfdx]

Is it possible, given instance of DelaunayTriangle, to retrieve indexes of original points, making its vertices? For example, if we added 20 points, and first triangle is made by points (3), (5) and (11) (in order of pushing them), is it possible to get these indexes?

[dfdx]

I ended up creating my own point type with built-in indexing:

type IndexedPoint2D <: AbstractPoint2D
    _x::Float64
    _y::Float64
    _idx::Int64
    IndexedPoint2D(x, y, idx) = new(x, y, idx)
    IndexedPoint2D(x, y) = new(x, y, 0)
end

getx(p::IndexedPoint2D) = p._x
gety(p::IndexedPoint2D) = p._y
getidx(p::IndexedPoint2D) = p._idx 

This, however, is a kind of a hack and doesn't work well in all circumstances. In particular, with this approach tesselation normally includes one fake point with zero index (created by default 2 parameter constructor).

Anyway, currently I'm using following code to get list of trignales as a matrix of size (num_triangles, 3), where each row represents 3 indexes of its vertices:

# convert matrix of shape (npoints, 2) to an array of IndexedPoints-s, 
# scaling everything to allowed interval and returning scaling factor
function to_points(shape::Matrix{Float64})
    min_value, max_value = (minimum(shape), maximum(shape))
    sc = (max_value - min_value) / (max_coord - min_coord)
    sc_shape = (shape .- min_value) / sc + min_coord
    points = IndexedPoint2D[IndexedPoint2D(sc_shape[i, 1], sc_shape[i, 2], i)
                            for i in 1:size(shape, 1)]
    return (points, sc)
end


function gettriangles(shape::Shape)
    npoints = size(shape, 1)
    tess = DelaunayTessellation2D{IndexedPoint2D}(npoints)
    points, _ = to_points(shape)
    push!(tess, points)
    return collect(tess)[1:end-1]   # excluding extra point       
end

Since I don't have any more time to spend on this issue and such (hacky) fix works for me, I'm leaving it as it is, hoping that some brave mind will be able to make it stable in all circumstances.

[skariel]

This is a bug, I'll fix it- your solution should work just fine, And there shouldn't be a fake point with an index of zero.

So I'll fix it, remember to change your code when you upgrade (so you don't miss a real point)

[dfdx]

Great, thank you!

[skariel]

The problem is that the user tessellation is built inside a preexisting tessellation of 4 points at (1,1),(1,2),(2,1) and (2,2). These are "virtual" points and need to be removed and currently this library does not remove these correctly.

I'm fixing this but it will take a bit more time since its not a trivial fix -- there should be a post-processing pass.

On the good side, I've improved performance by a bout 15% by removing a few type instabilities at GeometricalPredicates. And more performance is possible when using in-place BigInt operations. I'm working on a PR for that...

[dfdx]

Any news on this issue? I'm planning to release library that uses Delaunay triangulation, so it will be nice to know status of the bug and either fix it or warn users about some "strange" behavior.

Note, it's not critical for that library, so no hurry here. It's just for keeping users informed.

[skariel]

No proper fix yet, but maybe you could just filter out those triangles containing the virtual point (those with index 0) can this solve the problem? If not, then I guess best thing as of now would be to warn the users...

[skariel]

Actually filtering these triangles would still sometimes give weird results. Another approach for a "fast" fix would be to make a dense "frame" of points and let the user add points only inside. Again, not a real solution good for all circumstances but maybe fits you need.

I do intend to fix this issue...

[dfdx]

I already have kind of a fast fix for this, so I will go with it for now and just warn users until this issue is resolved normally. Thanks for your time!

[cortner]

Can I just confirm something: when I create a tessellation and then plot it, the reason what I see is not convex are the virtual points at the corners?

[skariel]

@cortner can you attach an example plot? I think Delaunay tessellations should not be convex, and Voronoy ones just fill the whole space... so I don't know what you mean. Maybe in your case the corners so affect the shape that you expect, it's possible. Just work further away from the corners where they don't affect the result

[cortner]

@skariel i am pretty sure the Union of triangles should be the convex hull of the vertices. I can attach a figure later.

[skariel]

I know a theorem that says that a Delaunay tessellation is the convex hull of the n+1 dimensional elevation for e.g. a tessellation in 2D has points (x,y) and 3D points (x,y, x*x+y*y) in this case the projection of the convex hull of the 3D configuration is the 2D tessellation. But the 2D tessellation does not need to be convex. Imagine using just 3 points... the Delaunay tessellation would be a triangle which is of course not convex...

[cortner]

@skariel

I can only imagine that we are having a clash of terminology, you are probably referring to the set of edges, whereas I am referring to the union of the triangles (incl interior), I guess I should have said triangulation instead of tesselation?

Anyhow, checking on Wikipedia, the Delauynay triangulation triangulates the convex hull of the set of vertices.