Re: [Jts-topo-suite-user] union of very large number of complex, shared edge 2d polygons

[Martin D. <mtn...@gm...>]

So in other words your algorithm would first find the connected sets of
filters LSOA polygons, and then do the dissolve-union on them.   Makes
sense.

Another way to find connected sets would be to build a fully linked
topological structure of Edges and Faces.  The Edges are 2-point line
segments.  They have links to the Face on either side.  The Faces have a
reference to their source Polygon, and a list of their surrounding Edges.
 Edges could be loaded into a Map for fast lookup.  Then you can run a
graph traversal algorithm marking the groups of connected Faces.

This is more code, but may be faster (since the step of detecting
neighbours in the STRtree algorithm may be a bit slow, unless you create
edge indexes for each polygon).


Another way: run the Dissolve-Polygonize algorithm on the entire set of
filtered polygons, and then for each result polygon in the output test
whether it covers an input polygon (via a point-in-polygon query against an
STRtree of the input polygons).

Hard to say a priori which approach will be fastest.


On Thu, Apr 25, 2013 at 9:14 AM, David Prime <da...@pr...> wrote:

> Ah, I should have made it clear that there will tend to be lots of
> discontinuities in the output . The input set is hole-free, but the
> filtered set is definitely not.
>
> To get around that, I'm thinking something like, given the islands of the
> output:
>
> -iterate on each polygon result and find its neighbours using a spatial
> proximity index (STRTree with a bbox slightly large than the rectangle
> required for the initial poly should do it), removing neighbours from the
> main list as they are found
> -find the directly connected neighbours and group each connected set
> together
> -proceed with your algorithm on the resultant sets
>
> Sound sensible?
>
> What I'd really love to do would be to reduce the resolution of the
> polygon boundaries but that would destroy the exact shared boundaries and
> introduce tiny holes and overlaps everywhere.
>
>
> On Thu, Apr 25, 2013 at 4:49 PM, Martin Davis <mtn...@gm...> wrote:
>
>> Always happy to hear insane performance questions.
>>
>> You're right about being able to use the constrained nature of the
>> problem to get better performance for union, I think.  I haven't tried this
>> yet, but I think the following algorithm should work:
>>
>> - Extract all the line segments of the input polygons as LineSegments
>> - Dissolve them (discard any that appear twice).  One way to do this is
>> to use a HashSet, and when inserting an edge that is already in the set,
>> remove the one in the set as well
>> - Polygonize the result.  (You can use the JTS Polygonizer to do this, if
>> you convert the LineSegments to two-point LineStrings.  There's probably
>> other slightly more efficient ways of doing this as well, but they involve
>> a lot more coding)
>> - You said there should be no holes and the output should be connected,
>> so there should be only a single Polygon created by the Polygonize step.
>>  That is the required union.
>> - If there *is* more than one output Polygon, that probably indicates
>> that holes were found for some reason. Be worth looking into why the
>> initial assumption did not hold. Or, you could just keep the output polygon
>> whose envelope is largest (but this won't work if there are islands)
>>
>> I'd be interested to hear if this provides a performance improvement.
>>  And if the code is simple enough it would be nice to share it.
>>
>>
>>  On Thu, Apr 25, 2013 at 12:58 AM, David Prime <da...@pr...>wrote:
>>
>>>  Morning All,
>>>
>>> Back with yet more insane performance questions :)
>>>
>>> So I'm developing a system for locatable.com that will allow you to
>>> filter all of the UK by various metrics (like average house price or
>>> crime). For this purpose, I use the ONS' system of LSOAs which are approx
>>> 34,000 small regions covering the entire mainland england+wales.
>>>
>>> To the interesting bit: when I do my search, I end up with a qualifying
>>> group of these LSOAs, for which I have very precise polygons. They share
>>> exact borders with each other and leave no gaps (except at the coastline
>>> and Scottish Border). I'm using the cascading union to merge the qualifying
>>> regions (on average, 17,000 of them, each with hundreds or thousands of
>>> coordinates). I'm wondering if there's any optimisations I might make use
>>> of that require these very conditions, ie lots of shared boundaries and a
>>> guarantee of no overlap?
>>>
>>> Cheers,
>>> David
>>>
>>>
>>> ------------------------------------------------------------------------------
>>> Try New Relic Now & We'll Send You this Cool Shirt
>>> New Relic is the only SaaS-based application performance monitoring
>>> service
>>> that delivers powerful full stack analytics. Optimize and monitor your
>>> browser, app, & servers with just a few lines of code. Try New Relic
>>> and get this awesome Nerd Life shirt!
>>> http://p.sf.net/sfu/newrelic_d2d_apr
>>> _______________________________________________
>>> Jts-topo-suite-user mailing list
>>> Jts...@li...
>>> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
>>>
>>>
>>
>>
>> ------------------------------------------------------------------------------
>> Try New Relic Now & We'll Send You this Cool Shirt
>> New Relic is the only SaaS-based application performance monitoring
>> service
>> that delivers powerful full stack analytics. Optimize and monitor your
>> browser, app, & servers with just a few lines of code. Try New Relic
>> and get this awesome Nerd Life shirt!
>> http://p.sf.net/sfu/newrelic_d2d_apr
>> _______________________________________________
>> Jts-topo-suite-user mailing list
>> Jts...@li...
>> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
>>
>>
>
>
> ------------------------------------------------------------------------------
> Try New Relic Now & We'll Send You this Cool Shirt
> New Relic is the only SaaS-based application performance monitoring service
> that delivers powerful full stack analytics. Optimize and monitor your
> browser, app, & servers with just a few lines of code. Try New Relic
> and get this awesome Nerd Life shirt! http://p.sf.net/sfu/newrelic_d2d_apr
> _______________________________________________
> Jts-topo-suite-user mailing list
> Jts...@li...
> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
>
>