Order of results in GEOSDelaunayTriangulation

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

Order of results in GEOSDelaunayTriangulation

Nyall Dawson
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.

Cheers,

Nyall
_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: Order of results in GEOSDelaunayTriangulation

Sandro Santilli-4
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.

--strk;
_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: Order of results in GEOSDelaunayTriangulation

Nyall Dawson
On 4 September 2017 at 17:31, Sandro Santilli <[hidden email]> 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?

E.g. if I set the user data for each point geometry being fed into a
multipoint via GEOSGeom_createCollection, could that user data be
retained and then later copied over to the output polygons from the
triangulation?

Nyall
_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: Order of results in GEOSDelaunayTriangulation

Sandro Santilli-4
On Mon, Sep 04, 2017 at 07:10:27PM +1000, Nyall Dawson wrote:

> On 4 September 2017 at 17:31, Sandro Santilli <[hidden email]> 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;
_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: Order of results in GEOSDelaunayTriangulation

Martin Davis-3
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.



On Mon, Sep 4, 2017 at 2:23 AM, Sandro Santilli <[hidden email]> wrote:
On Mon, Sep 04, 2017 at 07:10:27PM +1000, Nyall Dawson wrote:
> On 4 September 2017 at 17:31, Sandro Santilli <[hidden email]> 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;


_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: Order of results in GEOSDelaunayTriangulation

Martin Davis-3
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 <[hidden email]> 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.



On Mon, Sep 4, 2017 at 2:23 AM, Sandro Santilli <[hidden email]> wrote:
On Mon, Sep 04, 2017 at 07:10:27PM +1000, Nyall Dawson wrote:
> On 4 September 2017 at 17:31, Sandro Santilli <[hidden email]> 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;



_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: Order of results in GEOSDelaunayTriangulation

username
In reply to this post by Nyall Dawson
a possible method to determine a mapping from triangles to nodes: 
1.edit geos-3.6.1\src\triangulate\quadedge\QuadEdgeSubdivision.cpp line 588 ,add:
cellPoly->setUserData(reinterpret_cast<void*>(geomFact.createPoint(c)));
return cellPoly;
2.edit geos-3.6.1\src\triangulate\VoronoiDiagramBuilder.cpp line 136 ,moved one line:
else if(clipEnv.intersects(g->getEnvelopeInternal()))
{
result.reset( clipPoly->intersection(g) );
}
if(result.get() && !result->isEmpty() )
{result->setUserData(((Geometry*)g)->getUserData()); // moved
clipped->push_back(result.release());
}
hope this will help.

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel