[geos-devel] Order of results in GEOSDelaunayTriangulation

[Martin Davis]

Further thoughts on this:

- it would be nice if Vertex provided a userData field to carry references
to user node objects.  That would avoid the need to subclass Vertex.
- Would it be nice to have a method to extract all the triangles around a
given Vertex (or Coordinate)?

Also, obviously I am specifying algorithms in a Java/JTS context.
Hopefully there are obvious C++/GEOS equivalents.

On Mon, Sep 4, 2017 at 10:51 AM, Martin Davis <mtnclimb at gmail.com> wrote:

> 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/8c75253a/attachment.html>