[geos-devel] Questions on noding through the C interface

[Crispin Cooper]

Hi,

I am looking to node a set of linestrings through the GEOS C interface.  
Apologies in advance for the number of questions in this email, but I 
hope together they give a good idea of my requirements.

Two caveats:  (1) I need to be able to reject individual nodes at 
predetermined locations, i.e., occasionally at my discretion allow 
linestrings to cross at points other than their endpoints; (2) I need to 
be able to work to a prespecified tolerance.

I notice that computing the union or intersection of a multilinestring 
geometry with itself, automatically splits all linestrings where they 
cross or touch.  This wasn't what I was expecting - as presumably 
returning the input unchanged would constitute a valid intersection with 
itself - so can I rely on such behaviour?

In any case that doesn't help me with (1) above, i.e. I need to not 
split at certain points.  So instead I can intersect each linestring 
individually with the entire multilinestring set, and if I get a 
multilinestring back I know it must have intersected, and can decide 
what to do with that intersection i.e. whether or not to keep it. (As an 
aside - can I guarantee in the multilinestring returned that points will 
appear in the same order as in the input linestring?)

However, does the second approach incorporate significantly greater 
computation time?  Self-intersecting the entire set might be done in O(n 
log n) (is it?) but looping through individual segments is presumably 
O(n^2) at best.  How can I make it faster?

Finally how do I incorporate the tolerance parameter into the above 
algorithm?

Cheers

Crispin

-- 
Crispin Cooper
Sustainable Places Research Institute
33 Park Place, Cardiff CF10 3BA
Phone +44 (0)29 20876072