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 axis-parallel ray and the 45-degree ray (happily, the test for which
side of a 45-degree 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 envelope-envelope 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 special-purpose 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
<[email protected]>wrote:
> 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
>
>
>
------------------------------------------------------------------------------
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
