[geos-devel] Order of results in GEOSDelaunayTriangulation

[Martin Davis]

There is a "logic" to the ordering of the returned triangles, but it's not
useful for associating triangles with their coordinates.  In fact, i can't
think of how a ordered list could do this, given the many-to-many
relationship between triangles and vertices.

So, there's two ways you can determine a mapping from triangles to nodes:

1. Build a TreeMap from the node Coordinate to the originating node
object.  Then the nodes can be looked up for each triangle coordinate.

2. Use the lower-level methods of QuadEdgeSubdivision:
2.1 build explicit Vertex objects from node coordinates.  You will probably
need to make your own subclass of Vertex to carry any extra information you
need (such as a reference back to your original node objects)
2.2 create a QuadEdgeSubdivision
2.3 triangulate the vertices using  IncrementalDelaunayTriangulator  (for
an example see [1] )
2.4 use QuadEdgeSubdivision#getTriangleVertices to get the triangles as
arrays of Vertex objects. ( [2] )

Some feedback to confirm whether #2 works would be welcome.

[1]
https://github.com/locationtech/jts/blob/master/modules/core/src/main/java/org/locationtech/jts/triangulate/DelaunayTriangulationBuilder.java#L144
[2]
https://github.com/locationtech/jts/blob/master/modules/core/src/main/java/org/locationtech/jts/triangulate/quadedge/QuadEdgeSubdivision.java#L746


On Mon, Sep 4, 2017 at 2:23 AM, Sandro Santilli <strk at kbt.io> wrote:

> On Mon, Sep 04, 2017 at 07:10:27PM +1000, Nyall Dawson wrote:
> > On 4 September 2017 at 17:31, Sandro Santilli <strk at kbt.io> wrote:
> > > On Mon, Sep 04, 2017 at 04:33:28PM +1000, Nyall Dawson wrote:
> > >> Hi list,
> > >>
> > >> Quick question - is there any logic to the order of geometries in the
> > >> collection returned by calling GEOSDelaunayTriangulation?
> > >>
> > >> I'm looking for a way to reliably associate the parts of the returned
> > >> collection with the original input nodes. Ideally I'd like to avoid
> > >> having to test for intersection for each of them.
> > >
> > > I don't think there's any promise about output order, so even if you
> > > find one now it won't necessarely remain.
> >
> > That's what I suspected. How about geometry user data, could that
> > potentially be used here?
>
> I'm afraid you'll have to test. And same precautions apply:
> is it documented as being supported ?
>
> I'm adding Martin Davis in Cc as that class is ported from JTS.
>
> --strk;
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/geos-devel/attachments/20170904/5a56da81/attachment-0001.html>