From: Michael Bedward <michael.bedward@gm...>  20131203 00:21:26

Hi Martin, The following is a general algorithm query rather than a specific JTS question  hope that's ok. I have a set of polygons which represent urban areas within a fireprone landscape. There are about 5000 polygons varying widely in area, spatial extent, number of vertices and boundary complexity. I have the task of creating a regular grid of sample points within the surrounding landscape and, for each point, determining the distance to the nearest polygon within each of eight compass segments (ie. N to NE, NE to E...). The results only need to be expressed as categorized values based on a small number of distance cutpoints. I've been trying to nut out something other than a brute force approach to this without much success so far. One of the possibly less brutish approaches I've thought of involves the following: 1. Split up the urban polygons by intersecting them with a regular lattice, create PreparedGeometry objects for the resulting parts and put them into an STRtree. 2. Construct a sampling template made up of polygons representing the compass segments, each split according to the distance cutpoints (looking a bit like a dart board), possibly using a custom CoordinateSequence to have vertex coordinates calculated on the fly based on the centre coordinate. 3. For each sample point location: For each compass segment: For inner to outer segment part: Query the spatial index with the segment part envelope and, if any urban polygons are returned, test for intersection. I'm sure there must be a better way. Any suggestions or comments will be gratefully accepted. Michael 
From: Martin Davis <mtnclimb@gm...>  20131203 01:26:05
Attachments:
Message as HTML

A fascinating problem, Michael. How's this for a idea: use a directionconstrained nearest neighbour search. (Don't bother googling this  I just made it up!). The STRtree in JTS provides a nearestneighbour search made efficient by walking the Rtree node hierarchy. It should be possible to add some further logic to the search algorithm to reject candidates which do not lie in the compass direction of interest. (It seems like it will be straightforward to compute whether a candidate lies with the compass slice). You'll have to open up the STRtree nearest neighbour code and add provision for a custom filter to be run on each candidate as they are added to the current search list. This should be built using a filter function interface, to make it reusable. On Mon, Dec 2, 2013 at 4:21 PM, Michael Bedward <michael.bedward@...>wrote: > Hi Martin, > > The following is a general algorithm query rather than a specific JTS > question  hope that's ok. > > I have a set of polygons which represent urban areas within a > fireprone landscape. There are about 5000 polygons varying widely in > area, spatial extent, number of vertices and boundary complexity. > > I have the task of creating a regular grid of sample points within the > surrounding landscape and, for each point, determining the distance to > the nearest polygon within each of eight compass segments (ie. N to > NE, NE to E...). The results only need to be expressed as categorized > values based on a small number of distance cutpoints. > > I've been trying to nut out something other than a brute force > approach to this without much success so far. One of the possibly less > brutish approaches I've thought of involves the following: > > 1. Split up the urban polygons by intersecting them with a regular > lattice, create PreparedGeometry objects for the resulting parts and > put them into an STRtree. > > 2. Construct a sampling template made up of polygons representing the > compass segments, each split according to the distance cutpoints > (looking a bit like a dart board), possibly using a custom > CoordinateSequence to have vertex coordinates calculated on the fly > based on the centre coordinate. > > 3. For each sample point location: > For each compass segment: > For inner to outer segment part: > Query the spatial index with the segment part envelope > and, if any urban polygons are returned, test for > intersection. > > I'm sure there must be a better way. Any suggestions or comments will > be gratefully accepted. > > Michael > > >  > Rapidly troubleshoot problems before they affect your business. Most IT > organizations don't have a clear picture of how application performance > affects their revenue. With AppDynamics, you get 100% visibility into your > Java,.NET, & PHP application. Start your 15day FREE TRIAL of AppDynamics > Pro! > http://pubads.g.doubleclick.net/gampad/clk?id=84349351&iu=/4140/ostg.clktrk > _______________________________________________ > Jtstoposuiteuser mailing list > Jtstoposuiteuser@... > https://lists.sourceforge.net/lists/listinfo/jtstoposuiteuser > 
From: Martin Davis <mtnclimb@gm...>  20131203 01:36:37
Attachments:
Message as HTML

I just realized that you don't even have to alter STRtree to support a custom filter function. STRtree already provides a method which accepts a custom ItemDistance function. This could be given an implementation which forces the distance of objects *not* in the current compass slice to be Double.MAX_VALUE. On Mon, Dec 2, 2013 at 5:25 PM, Martin Davis <mtnclimb@...> wrote: > A fascinating problem, Michael. > > How's this for a idea: use a directionconstrained nearest neighbour > search. (Don't bother googling this  I just made it up!). The STRtree in > JTS provides a nearestneighbour search made efficient by walking the > Rtree node hierarchy. It should be possible to add some further logic to > the search algorithm to reject candidates which do not lie in the compass > direction of interest. (It seems like it will be straightforward to > compute whether a candidate lies with the compass slice). > > You'll have to open up the STRtree nearest neighbour code and add > provision for a custom filter to be run on each candidate as they are added > to the current search list. This should be built using a filter function > interface, to make it reusable. > > > On Mon, Dec 2, 2013 at 4:21 PM, Michael Bedward <michael.bedward@... > > wrote: > >> Hi Martin, >> >> The following is a general algorithm query rather than a specific JTS >> question  hope that's ok. >> >> I have a set of polygons which represent urban areas within a >> fireprone landscape. There are about 5000 polygons varying widely in >> area, spatial extent, number of vertices and boundary complexity. >> >> I have the task of creating a regular grid of sample points within the >> surrounding landscape and, for each point, determining the distance to >> the nearest polygon within each of eight compass segments (ie. N to >> NE, NE to E...). The results only need to be expressed as categorized >> values based on a small number of distance cutpoints. >> >> I've been trying to nut out something other than a brute force >> approach to this without much success so far. One of the possibly less >> brutish approaches I've thought of involves the following: >> >> 1. Split up the urban polygons by intersecting them with a regular >> lattice, create PreparedGeometry objects for the resulting parts and >> put them into an STRtree. >> >> 2. Construct a sampling template made up of polygons representing the >> compass segments, each split according to the distance cutpoints >> (looking a bit like a dart board), possibly using a custom >> CoordinateSequence to have vertex coordinates calculated on the fly >> based on the centre coordinate. >> >> 3. For each sample point location: >> For each compass segment: >> For inner to outer segment part: >> Query the spatial index with the segment part envelope >> and, if any urban polygons are returned, test for >> intersection. >> >> I'm sure there must be a better way. Any suggestions or comments will >> be gratefully accepted. >> >> Michael >> >> >>  >> Rapidly troubleshoot problems before they affect your business. Most IT >> organizations don't have a clear picture of how application performance >> affects their revenue. With AppDynamics, you get 100% visibility into your >> Java,.NET, & PHP application. Start your 15day FREE TRIAL of AppDynamics >> Pro! >> >> http://pubads.g.doubleclick.net/gampad/clk?id=84349351&iu=/4140/ostg.clktrk >> _______________________________________________ >> Jtstoposuiteuser mailing list >> Jtstoposuiteuser@... >> https://lists.sourceforge.net/lists/listinfo/jtstoposuiteuser >> > > 
From: Michael Bedward <michael.bedward@gm...>  20131203 02:07:25

That sounds like it could be just the ticket Martin ! Thanks so much. I'll play with that and let you know how I get on. Michael On 3 December 2013 12:36, Martin Davis <mtnclimb@...> wrote: > I just realized that you don't even have to alter STRtree to support a > custom filter function. STRtree already provides a method which accepts a > custom ItemDistance function. This could be given an implementation which > forces the distance of objects *not* in the current compass slice to be > Double.MAX_VALUE. > > > On Mon, Dec 2, 2013 at 5:25 PM, Martin Davis <mtnclimb@...> wrote: >> >> A fascinating problem, Michael. >> >> How's this for a idea: use a directionconstrained nearest neighbour >> search. (Don't bother googling this  I just made it up!). The STRtree in >> JTS provides a nearestneighbour search made efficient by walking the Rtree >> node hierarchy. It should be possible to add some further logic to the >> search algorithm to reject candidates which do not lie in the compass >> direction of interest. (It seems like it will be straightforward to compute >> whether a candidate lies with the compass slice). >> >> You'll have to open up the STRtree nearest neighbour code and add >> provision for a custom filter to be run on each candidate as they are added >> to the current search list. This should be built using a filter function >> interface, to make it reusable. >> >> >> On Mon, Dec 2, 2013 at 4:21 PM, Michael Bedward >> <michael.bedward@...> wrote: >>> >>> Hi Martin, >>> >>> The following is a general algorithm query rather than a specific JTS >>> question  hope that's ok. >>> >>> I have a set of polygons which represent urban areas within a >>> fireprone landscape. There are about 5000 polygons varying widely in >>> area, spatial extent, number of vertices and boundary complexity. >>> >>> I have the task of creating a regular grid of sample points within the >>> surrounding landscape and, for each point, determining the distance to >>> the nearest polygon within each of eight compass segments (ie. N to >>> NE, NE to E...). The results only need to be expressed as categorized >>> values based on a small number of distance cutpoints. >>> >>> I've been trying to nut out something other than a brute force >>> approach to this without much success so far. One of the possibly less >>> brutish approaches I've thought of involves the following: >>> >>> 1. Split up the urban polygons by intersecting them with a regular >>> lattice, create PreparedGeometry objects for the resulting parts and >>> put them into an STRtree. >>> >>> 2. Construct a sampling template made up of polygons representing the >>> compass segments, each split according to the distance cutpoints >>> (looking a bit like a dart board), possibly using a custom >>> CoordinateSequence to have vertex coordinates calculated on the fly >>> based on the centre coordinate. >>> >>> 3. For each sample point location: >>> For each compass segment: >>> For inner to outer segment part: >>> Query the spatial index with the segment part envelope >>> and, if any urban polygons are returned, test for >>> intersection. >>> >>> I'm sure there must be a better way. Any suggestions or comments will >>> be gratefully accepted. >>> >>> Michael >>> >>> >>>  >>> Rapidly troubleshoot problems before they affect your business. Most IT >>> organizations don't have a clear picture of how application performance >>> affects their revenue. With AppDynamics, you get 100% visibility into >>> your >>> Java,.NET, & PHP application. Start your 15day FREE TRIAL of AppDynamics >>> Pro! >>> >>> http://pubads.g.doubleclick.net/gampad/clk?id=84349351&iu=/4140/ostg.clktrk >>> _______________________________________________ >>> Jtstoposuiteuser mailing list >>> Jtstoposuiteuser@... >>> https://lists.sourceforge.net/lists/listinfo/jtstoposuiteuser >> >> > 
From: Martin Davis <mtnclimb@gm...>  20131203 03:29:48
Attachments:
Message as HTML

Sounds good, Michael. If this proves out it would be worth a blog post by you and/or me. (With a picture or two, of course!) On Mon, Dec 2, 2013 at 6:07 PM, Michael Bedward <michael.bedward@...>wrote: > That sounds like it could be just the ticket Martin ! > > Thanks so much. I'll play with that and let you know how I get on. > > Michael > > > On 3 December 2013 12:36, Martin Davis <mtnclimb@...> wrote: > > I just realized that you don't even have to alter STRtree to support a > > custom filter function. STRtree already provides a method which accepts > a > > custom ItemDistance function. This could be given an implementation > which > > forces the distance of objects *not* in the current compass slice to be > > Double.MAX_VALUE. > > > > > > On Mon, Dec 2, 2013 at 5:25 PM, Martin Davis <mtnclimb@...> wrote: > >> > >> A fascinating problem, Michael. > >> > >> How's this for a idea: use a directionconstrained nearest neighbour > >> search. (Don't bother googling this  I just made it up!). The STRtree > in > >> JTS provides a nearestneighbour search made efficient by walking the > Rtree > >> node hierarchy. It should be possible to add some further logic to the > >> search algorithm to reject candidates which do not lie in the compass > >> direction of interest. (It seems like it will be straightforward to > compute > >> whether a candidate lies with the compass slice). > >> > >> You'll have to open up the STRtree nearest neighbour code and add > >> provision for a custom filter to be run on each candidate as they are > added > >> to the current search list. This should be built using a filter > function > >> interface, to make it reusable. > >> > >> > >> On Mon, Dec 2, 2013 at 4:21 PM, Michael Bedward > >> <michael.bedward@...> wrote: > >>> > >>> Hi Martin, > >>> > >>> The following is a general algorithm query rather than a specific JTS > >>> question  hope that's ok. > >>> > >>> I have a set of polygons which represent urban areas within a > >>> fireprone landscape. There are about 5000 polygons varying widely in > >>> area, spatial extent, number of vertices and boundary complexity. > >>> > >>> I have the task of creating a regular grid of sample points within the > >>> surrounding landscape and, for each point, determining the distance to > >>> the nearest polygon within each of eight compass segments (ie. N to > >>> NE, NE to E...). The results only need to be expressed as categorized > >>> values based on a small number of distance cutpoints. > >>> > >>> I've been trying to nut out something other than a brute force > >>> approach to this without much success so far. One of the possibly less > >>> brutish approaches I've thought of involves the following: > >>> > >>> 1. Split up the urban polygons by intersecting them with a regular > >>> lattice, create PreparedGeometry objects for the resulting parts and > >>> put them into an STRtree. > >>> > >>> 2. Construct a sampling template made up of polygons representing the > >>> compass segments, each split according to the distance cutpoints > >>> (looking a bit like a dart board), possibly using a custom > >>> CoordinateSequence to have vertex coordinates calculated on the fly > >>> based on the centre coordinate. > >>> > >>> 3. For each sample point location: > >>> For each compass segment: > >>> For inner to outer segment part: > >>> Query the spatial index with the segment part envelope > >>> and, if any urban polygons are returned, test for > >>> intersection. > >>> > >>> I'm sure there must be a better way. Any suggestions or comments will > >>> be gratefully accepted. > >>> > >>> Michael > >>> > >>> > >>> >  > >>> Rapidly troubleshoot problems before they affect your business. Most IT > >>> organizations don't have a clear picture of how application performance > >>> affects their revenue. With AppDynamics, you get 100% visibility into > >>> your > >>> Java,.NET, & PHP application. Start your 15day FREE TRIAL of > AppDynamics > >>> Pro! > >>> > >>> > http://pubads.g.doubleclick.net/gampad/clk?id=84349351&iu=/4140/ostg.clktrk > >>> _______________________________________________ > >>> Jtstoposuiteuser mailing list > >>> Jtstoposuiteuser@... > >>> https://lists.sourceforge.net/lists/listinfo/jtstoposuiteuser > >> > >> > > > 
From: Michael Bedward <michael.bedward@gm...>  20131206 07:47:21

Hi Martin, I've now got some initial code working for directionconstrained nearestneighbour search. There is a Sector class which holds an origin location and an angular interval. This has a method which takes an Envelope and tests whether it is visible within the sector. A SectorItemDistance object takes a Sector and uses it to filter items in the STRtree search before calculating the distance to the sector origin. This part works really nicely ! I've coded it in Scala but it could easily be Javanized. Now I need to go the next step. This diagram... http://imagebin.org/280824 ...shows a search sector from north to northwest. The blue dot and line indicate the global nearest point to the sector origin on a polygon boundary  as returned by the current test code. The red dot and line indicate what I actually want: the nearest boundary point within the sector. If I take my original idea of radially stacked polygons representing the sector and test for intersection with a candidate polygon as part of the ItemDistance code, I can return a value for categorized distance (based on the sector polygon that intersects) or a nodata value. That would also deal with pesky edge cases such as the one in this example... http://imagebin.org/280825 Here the sector origin lies within the envelope of the large polygon, so that polygon would be returned as the nearest neighbour in the current test code. But the polygon itself isn't "visible" within the sector  it's the small one that we want. The intersection tests would pick that up. In the quest for efficiency, I'm splitting the input polygons with a regular grid and creating PreparedGeometry objects from the resulting parts before loading them into the STRtree. Will keep you posted :) Michael On 3 December 2013 14:29, Martin Davis <mtnclimb@...> wrote: > Sounds good, Michael. If this proves out it would be worth a blog post by > you and/or me. (With a picture or two, of course!) > > > On Mon, Dec 2, 2013 at 6:07 PM, Michael Bedward <michael.bedward@...> > wrote: >> >> That sounds like it could be just the ticket Martin ! >> >> Thanks so much. I'll play with that and let you know how I get on. >> >> Michael >> >> >> On 3 December 2013 12:36, Martin Davis <mtnclimb@...> wrote: >> > I just realized that you don't even have to alter STRtree to support a >> > custom filter function. STRtree already provides a method which accepts >> > a >> > custom ItemDistance function. This could be given an implementation >> > which >> > forces the distance of objects *not* in the current compass slice to be >> > Double.MAX_VALUE. >> > >> > >> > On Mon, Dec 2, 2013 at 5:25 PM, Martin Davis <mtnclimb@...> wrote: >> >> >> >> A fascinating problem, Michael. >> >> >> >> How's this for a idea: use a directionconstrained nearest neighbour >> >> search. (Don't bother googling this  I just made it up!). The STRtree >> >> in >> >> JTS provides a nearestneighbour search made efficient by walking the >> >> Rtree >> >> node hierarchy. It should be possible to add some further logic to the >> >> search algorithm to reject candidates which do not lie in the compass >> >> direction of interest. (It seems like it will be straightforward to >> >> compute >> >> whether a candidate lies with the compass slice). >> >> >> >> You'll have to open up the STRtree nearest neighbour code and add >> >> provision for a custom filter to be run on each candidate as they are >> >> added >> >> to the current search list. This should be built using a filter >> >> function >> >> interface, to make it reusable. >> >> >> >> >> >> On Mon, Dec 2, 2013 at 4:21 PM, Michael Bedward >> >> <michael.bedward@...> wrote: >> >>> >> >>> Hi Martin, >> >>> >> >>> The following is a general algorithm query rather than a specific JTS >> >>> question  hope that's ok. >> >>> >> >>> I have a set of polygons which represent urban areas within a >> >>> fireprone landscape. There are about 5000 polygons varying widely in >> >>> area, spatial extent, number of vertices and boundary complexity. >> >>> >> >>> I have the task of creating a regular grid of sample points within the >> >>> surrounding landscape and, for each point, determining the distance to >> >>> the nearest polygon within each of eight compass segments (ie. N to >> >>> NE, NE to E...). The results only need to be expressed as categorized >> >>> values based on a small number of distance cutpoints. >> >>> >> >>> I've been trying to nut out something other than a brute force >> >>> approach to this without much success so far. One of the possibly less >> >>> brutish approaches I've thought of involves the following: >> >>> >> >>> 1. Split up the urban polygons by intersecting them with a regular >> >>> lattice, create PreparedGeometry objects for the resulting parts and >> >>> put them into an STRtree. >> >>> >> >>> 2. Construct a sampling template made up of polygons representing the >> >>> compass segments, each split according to the distance cutpoints >> >>> (looking a bit like a dart board), possibly using a custom >> >>> CoordinateSequence to have vertex coordinates calculated on the fly >> >>> based on the centre coordinate. >> >>> >> >>> 3. For each sample point location: >> >>> For each compass segment: >> >>> For inner to outer segment part: >> >>> Query the spatial index with the segment part envelope >> >>> and, if any urban polygons are returned, test for >> >>> intersection. >> >>> >> >>> I'm sure there must be a better way. Any suggestions or comments will >> >>> be gratefully accepted. >> >>> >> >>> Michael >> >>> >> >>> >> >>> >> >>>  >> >>> Rapidly troubleshoot problems before they affect your business. Most >> >>> IT >> >>> organizations don't have a clear picture of how application >> >>> performance >> >>> affects their revenue. With AppDynamics, you get 100% visibility into >> >>> your >> >>> Java,.NET, & PHP application. Start your 15day FREE TRIAL of >> >>> AppDynamics >> >>> Pro! >> >>> >> >>> >> >>> http://pubads.g.doubleclick.net/gampad/clk?id=84349351&iu=/4140/ostg.clktrk >> >>> _______________________________________________ >> >>> Jtstoposuiteuser mailing list >> >>> Jtstoposuiteuser@... >> >>> https://lists.sourceforge.net/lists/listinfo/jtstoposuiteuser >> >> >> >> >> > > > 
From: Martin Davis <mtnclimb@gm...>  20131206 16:25:57
Attachments:
Message as HTML

Nice! As your pictures show, using the envelope as a proxy for the polygon is not accurate when the envelope intersects the Sector. It would be possible (and I think efficient) to implement an accurate Sector.intersects(Geometry) test, using the following algorithm: IF ! Sector.intersects(Envelope) return false; where intersects(Envelope) tests if all points lie on the same side of the axisparallel ray and the 45degree ray (happily, the test for which side of a 45degree ray is straightforward) ELSE test if the polygon intersects by scanning all segments and test if any of them terminate in the sector or intersect the sector rays. (this test involves some fiddly arithmetic, but nothing too complicated) i hadn't realized that you wanted the distance *within* the sector. You can't use the regular Geometry.distance(Point) method for this, of course. I'd think about implementing a custom Sector.distance(Geometry) algorithm, which computes the distance via a scan of the polygon segments. One potential issue I just thought of is that the STRtree NN algorithm relies on the envelopeenvelope distance being a "consistent proxy" with the actual distance between the geometry and the query geometry (the point). However, I think this is still the case with the Sector distance, so that should be fine. Not sure about the idea of cutting up the polygons and then using PreparedGeometry. Cutting them up will probably speed things up, although don't you then have to "reduce" the set of distances for a single polygon to find the minimum? And if you use the specialpurpose distance and intersects tests I propose above, then I don't think that PreparedGeometry is needed? On Thu, Dec 5, 2013 at 11:47 PM, Michael Bedward <michael.bedward@...>wrote: > Hi Martin, > > I've now got some initial code working for directionconstrained > nearestneighbour search. > > There is a Sector class which holds an origin location and an angular > interval. This has a method which takes an Envelope and tests whether > it is visible within the sector. A SectorItemDistance object takes a > Sector and uses it to filter items in the STRtree search before > calculating the distance to the sector origin. This part works really > nicely ! I've coded it in Scala but it could easily be Javanized. > > Now I need to go the next step. This diagram... > > http://imagebin.org/280824 > > ...shows a search sector from north to northwest. The blue dot and > line indicate the global nearest point to the sector origin on a > polygon boundary  as returned by the current test code. The red dot > and line indicate what I actually want: the nearest boundary point > within the sector. > > If I take my original idea of radially stacked polygons representing > the sector and test for intersection with a candidate polygon as part > of the ItemDistance code, I can return a value for categorized > distance (based on the sector polygon that intersects) or a nodata > value. > > That would also deal with pesky edge cases such as the one in this > example... > > http://imagebin.org/280825 > > Here the sector origin lies within the envelope of the large polygon, > so that polygon would be returned as the nearest neighbour in the > current test code. But the polygon itself isn't "visible" within the > sector  it's the small one that we want. The intersection tests would > pick that up. > > In the quest for efficiency, I'm splitting the input polygons with a > regular grid and creating PreparedGeometry objects from the resulting > parts before loading them into the STRtree. > > Will keep you posted :) > > Michael > > > 
From: Michael Bedward <michael.bedward@gm...>  20131208 23:43:33

Hi Martin, > i hadn't realized that you wanted the distance *within* the sector. My fault  I didn't spell it out clearly in my first post. > You > can't use the regular Geometry.distance(Point) method for this, of course. > I'd think about implementing a custom Sector.distance(Geometry) algorithm, > which computes the distance via a scan of the polygon segments. Yep, sounds good. > One potential issue I just thought of is that the STRtree NN algorithm > relies on the envelopeenvelope distance being a "consistent proxy" with the > actual distance between the geometry and the query geometry (the point). > However, I think this is still the case with the Sector distance, so that > should be fine. Hmm... but if "consistent proxy for" means something like "has the same rank order as" won't there be a problem ? > Not sure about the idea of cutting up the polygons and then using > PreparedGeometry. Cutting them up will probably speed things up, although > don't you then have to "reduce" the set of distances for a single polygon to > find the minimum? Luckily no. All I need is the minimum distance within sector from a point to any boundary. > And if you use the specialpurpose distance and > intersects tests I propose above, then I don't think that PreparedGeometry > is needed? Right  cool ! I had imagined that I'd be doing intersections as per previous messages, hence the idea of using PreparedGeometry. Michael 
From: Martin Davis <mtnclimb@gm...>  20131211 18:08:26
Attachments:
Message as HTML

On Sun, Dec 8, 2013 at 3:43 PM, Michael Bedward <michael.bedward@...>wrote: > > > > One potential issue I just thought of is that the STRtree NN algorithm > > relies on the envelopeenvelope distance being a "consistent proxy" with > the > > actual distance between the geometry and the query geometry (the point). > > However, I think this is still the case with the Sector distance, so that > > should be fine. > > Hmm... but if "consistent proxy for" means something like "has the > same rank order as" won't there be a problem ? > "Consistent proxy" means that the item distance algorithm must be bounded by the maximum and minimum Euclidean distances between the envelopes of the items. This is to allow pruning of known dead branches during the tree search. I think the actual sector distance algorithm obeys this bound (the sector distance is within the envelope distances). But I'm not sure about the idea of returning a MAX_DOUBLE distance to prune geometries fully outside the sector. It *might* work  but it might not. The first step is to set up a simple test case and try it out. If this doesn't work, then will have to think again about how to discard outofsector geometries. 
From: Michael Bedward <michael.bedward@gm...>  20140114 07:20:29

Hi Martin and all, I've now had the chance to do some test runs of the "direction constrained nearest neighbour" routine on a multicore machine and it seems to be working very well. The concurrent STRtree queries were fine. I spent a bit of time tweaking the code involved in working out which geometries a given sector can "see" and then calculating distances to them. The code to test if a geometry is seen follows the logic that you suggested last month: run through segments testing if an endpoint can be seen or, if not, testing for intersection with a sector ray. For each geometry that is visible, the routine then collects the visible segments and calculates a distance using the relevant CGAlgorithms method. I belatedly realized that a bit of caching to avoid doubling up between the "can see" and "get distance" tasks makes a big difference to the running time. Let me know if you still want to do a blog post on the algorithm Martin  I'd be happy to contribute text and/or pics. Michael 