Hi Martin, I've now got some initial code working for direction-constrained nearest-neighbour 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 Java-nized. Now I need to go the next step. This diagram... http://imagebin.org/280824 ...shows a search sector from north to north-west. 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 no-data 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 <[email protected]> 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 <[email protected]> > 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 <[email protected]> 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 <[email protected]> wrote: >> >> >> >> A fascinating problem, Michael. >> >> >> >> How's this for a idea: use a direction-constrained nearest neighbour >> >> search. (Don't bother googling this - I just made it up!). The STRtree >> >> in >> >> JTS provides a nearest-neighbour search made efficient by walking the >> >> R-tree >> >> 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 >> >> <[email protected]> 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 >> >>> fire-prone 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 cut-points. >> >>> >> >>> 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 cut-points >> >>> (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 15-day FREE TRIAL of >> >>> AppDynamics >> >>> Pro! >> >>> >> >>> >> >>> http://pubads.g.doubleclick.net/gampad/clk?id=84349351&iu=/4140/ostg.clktrk >> >>> _______________________________________________ >> >>> Jts-topo-suite-user mailing list >> >>> [email protected] >> >>> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user >> >> >> >> >> > > > ------------------------------------------------------------------------------ Sponsored by Intel(R) XDK Develop, test and display web and hybrid apps with a single code base. Download it for free now! http://pubads.g.doubleclick.net/gampad/clk?id=111408631&iu=/4140/ostg.clktrk _______________________________________________ Jts-topo-suite-user mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
