Subscribe to this thread
Home - General / All posts - M9 Decomposing polygons to 'islands' efficiently
danb


1,716 post(s)
#10-Oct-19 04:47

I have a raster which I have traced in M9 to produce polygons using TileTraceAreasPar with the decomposition parameter set to true.

I want to aggregate this layer into discrete 'islands' of polygons. By 'island', I mean a group of touching polygons including those which touch only at a shared coordinate. See image below.

I attach a Manifold 8 project with some sample data and a bit more of an explanation. I hope to achieve this efficiently in M9 (as the poligonised grids may be large) but don't have the smarts to get there so any guidance would be much appreciated.

Thanks in advance

Attachments:
M8 R2V FORUM.map


Landsystems Ltd ... Know your land | www.landsystems.co.nz

jsperr63 post(s)
#10-Oct-19 14:02

Will "Bounded Areas" do what you want?

yves61
154 post(s)
#10-Oct-19 17:11

Will union the areas where the areas are adjacent do ?

-Manifold 9 : group by GeomAdjacent() then use GeomUnionAreas ()

(not tested !)

danb


1,716 post(s)
#10-Oct-19 19:47

Thanks for the suggestions. I will have a look at them today.

My feeling was that the performance of spatial functions would quickly deteriorate on a large traced grid, which is I was leaning towards an a-spatial join on something like duplicate (polygon) pixel corner coordinates. I will however have a look at the spatial options and see if I can get them to work and if so, how they stack up.

Many thanks


Landsystems Ltd ... Know your land | www.landsystems.co.nz

tjhb

8,883 post(s)
#10-Oct-19 22:17

I was hoping that GeomToShapesEsri() might help, i.e. that it would see areas touching only at one point as contiguous. Alas not.

Yves' suggestion of grouping by the result of GeomAdjacent(), and your suggestion Dan of grouping by duplicate corner pixels, are sort of useful, but can only go so far as grouping neighbouring pairs. Not neighbouring clusters. So you would need to recur an indefinite number of times.

Bounded areas is no help, since resulting areas are normalized, in the sense that they are subdivided at corners.

The only thing I have thought of so far is to do a triangulation, then join resulting lines, then discard lines that only touch one source area, then group source areas by their touching joined line. A kind of spidery approach. I haven't tried it yet and I don't know if would (a) work or (b) be fast.

What would be really nicest, of course, is a GeomToShapes() option that regarded areas meeting at a single point as contiguous. That would be very useful, quite often.

Often the question is something like "Can an animal [or water, or...] get from one area to the next, if they only touch at a single point?" And often the answer, not so much because of the geometry itself as because of what it represents, is yes, of course it can.

But it should not be the default. (Because, well, geometry. A weak reason.)

danb


1,716 post(s)
#10-Oct-19 22:28

Thanks Tim, I am currently looking at my list of corner points and trying to work out what it tells me (I'm increasingly thinking very little) and had also arrived at the point of pseudo iteration, though haven't got beyond the thought yet.

I really like the option of something along the lines of GeomToShapes() as I need to do this sort of thing on an infrequent but fairly regular basis.

Its a funny one because it feels like it should be within reach, but then keeps drifting away when I try something. Anyway, thanks for having a look.


Landsystems Ltd ... Know your land | www.landsystems.co.nz

atrushwo51 post(s)
#10-Oct-19 22:31

I'm not sure if this is relevant or not, but I recall some discussion regarding grouping touching lines into clusters within this sub http://www.georeference.org/forum/t144606.12#144615. I imagine Adam's solution could be adopted in some manner to help with your current issue Dan.

tjhb

8,883 post(s)
#10-Oct-19 22:35

Yes. Adam's query+script+query fights fire with fire. I had forgotten that thread. This is good.

danb


1,716 post(s)
#10-Oct-19 22:47

That does look interesting. Many thanks I will have a look.

Edit: From a quick read, one of my lines of thought was similar to Art's, but scaling the geoms instead of buffering as I though this might be faster. I was still hoping to remove the spatial component however so had run with my duplicate coordinates thus far. Anyway onward to Adam's approach.


Landsystems Ltd ... Know your land | www.landsystems.co.nz

danb


1,716 post(s)
#12-Oct-19 23:25

Thanks very much for the pointer to this thread atrushwo. With a bit of tinkering it does exactly what I want to achieve. It is however let down performance wise by the first query (step 1a) which on my test data takes ~2 hours to run. Steps 2 and 3 take about 12 seconds.

The first query essentially builds the same lookup table as I was hoping to achieve with my polygon (pixel) duplicate corner coordinate approach i.e. a list of which polygons touch each other. As such I believe that this non-spatial approach might have some legs in expediting Adam's step 1a (spatial) query. Certainly on my test data, my M8 version builds almost the same table as Adam's step 1a query in about a minute and a half. I will keep working towards this and will also put in a suggestion for a function as suggested by Tim as this comes up with a degree of regularity for me.

Thanks again for your interest


Landsystems Ltd ... Know your land | www.landsystems.co.nz

adamw


8,696 post(s)
#14-Oct-19 10:20

Two quick notes:

The performance of detecting collisions in this particular case can be increased dramatically because we are only looking for coincident coordinates. GeomOverlayTouchingPar does not know that we are only looking for coincident coordinates, so it does a lot of things that it doesn't have to. We will consider adding a function to check specifically for coincident coordinates - because that's useful. Until we have such a function built-in, this can be done using a script function. A good way to retain the parallelism of GeomOverlayTouchingPar yet simplify the test would be to (a) create a new geom field with a spatial index on it, and populate it with bounding boxes of the geoms, (b) let GeomOverlayTouchingPar run on the boxes, then (c) filter the results of GeomOverlayTouchingPar using the script function which would take two geoms whose boxes are reported to be touching, and only report the geoms as touching if they have a coincident coordinate.

The best place to run this all 'lets-join-all-boxes-sharing-same-coordinate' thing is the tracing transform. Tracing knows that the resulting areas have coincident coordinates, so it is in the best position to run the processing. We will consider extending the decompose option from a simple boolean for decompose / don't decompose to a switch for decompose entirely (like we do now) / decompose but keep branches which are touching each other in the same geom (a new choice) / don't decompose.

danb


1,716 post(s)
#15-Oct-19 18:54

Hi Adam, Many thanks for your notes. Your point about GeomOverlayTouchingPar doing more work than necessary for this particular case was the thought that I had arrived at when I started thinking about coincident coordinates. With a little help from my friends, I replaced the first query using GeomOverlayTouchingPar with this approach to achieve this particular goal and it has reduced the process time to ~13 seconds. I then feed the result into your clusters script and I get exactly the result I am after so thank you very much for your cluster solution which is really handy.

VALUE @source_dwg TABLE = [VECTOR MASK Drawing];

CREATE TABLE [COORD]

    (

    [mfd_id] INT64,

    [XY] FLOAT64X2,

    [OID] INT32,

    --INDEX [mfd_id_x] BTREE ([mfd_id]),

    INDEX [OID_x] BTREEDUP ([OID]),

    INDEX [XY_x] BTREEDUP ([XY]) -- Speeds up grouping

    )

;

INSERT INTO [COORD] ([XY], [OID])

SELECT [XY], [mfd_id]

FROM

    (

    SELECT [mfd_id],

    SPLIT CALL GeomToCoords([Geom])

    FROM @source_dwg

    )

;

SELECT FIRST([OID]) AS [ID1], LAST([OID]) AS [ID2]

INTO [TEMP]

FROM [COORD]

GROUP BY [XY]

;

DROP TABLE [COORD]

;

CREATE TABLE [TEMP_OUT] ([ID] INT32, [IDCLUSTER] INT32, INDEX [ID_x] BTREE ([ID]))

;

With regards …

‘We will consider adding a function to check specifically for coincident coordinates - because that's useful.’

It most definitely would be as there are plenty of situations where this test alone would be sufficient. I appreciate that it can be done now, but a function would be neater and easier to understand I think.

‘We will consider extending the decompose option from a simple boolean for decompose / don't decompose to a switch for decompose entirely (like we do now) / decompose but keep branches which are touching each other in the same geom (a new choice) / don't decompose.’

I think this would really useful and a great addition. Many thanks for considering this. It is one of those things that I require on and off but am surprised how often it comes up. If it can simply be added to an existing function as a parameter then that would be a very neat solution.


Landsystems Ltd ... Know your land | www.landsystems.co.nz

adamw


8,696 post(s)
#16-Oct-19 10:05

The approach you used is pretty clever - it uses the fact that a coordinate can only belong to two different objects in SELECT First / Last ... GROUP, that does indeed hold for the results of tracing and it helps a ton.

13 seconds instead of hours is just great!

Manifold User Community Use Agreement Copyright (C) 2007-2017 Manifold Software Limited. All rights reserved.