<div dir="ltr">Thanks for the solution. This seems do able, but will push my learning a bit. I might select a small area using voting districts to keep the processing more manageable. <div><br></div><div>Thanks for the help,</div>

<div>Clifford</div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Sat, Aug 23, 2014 at 3:43 AM, Rémi Cura <span dir="ltr"><<a href="mailto:remi.cura@gmail.com" target="_blank">remi.cura@gmail.com</a>></span> wrote:<br>

<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><div>Hey,<br>I did something akin, I decided then for a 2 step process : find potential matches, then keep none or the better match.<br>

The problem is: given 2 tables A (old) and B(new), find a mapping between A and B,<br>
with the following limits: a building could be new, destroyed , same or changed. (Note that we exclude to track the fact that a building has been split in 2 buildings. In this case we want to get a changed building and a new building. It is a simple extension tough)<br>


This is a [0;1]<->[0;1] mapping<br>My hypothesis was that if old and new geometry where the same object, they should share some space.<br>First you find the building that haven't changed or that have changed (excluding the creation and destruction then)<br>


<br>For this you need a measure to quantify how much a building is similar to another. Basically you are looking for a function f(A.row, B.row ) -> score. <br>If you have only geometry, I would suggest the shared area (That is ST_Area(ST_Intersection(A.geom,B.geom)) ).<br>


If you have more semantic information (number of floors, admin district, whatever), you can inlcude it as well (I used name of street with fuzzy matching)<br><br>You also need a threshold T on score : if (fA.row,B.Row)< T -> they are not related building. Else these two buildings are related. <br>


(please note that you may normalize the score by for exemple LOWEST(ST_Area(A.geom), ST_Area(B.geom)) if your buildings are widely different)<br><br>Now you could already have a result but it would be extremely slow .<br>


You would simply do :<br>for every row of A . find the row of B so that f(A.row,B.row) is maximal.<br></div>(SELECT DISTINCT ON (A.id, B.id) A.id AS id_a, B.id AS id_b<br>FROM A,B<br></div>ORDER BY A.id ASC, f(A.geom,B.geom) DESC ;B.id ASC)<br>


<div><div>It would be very slow because you would do 300k * 300 k test on f().<br>The idea is then :<br>for buildings to share some area, they should be close enough (distance d). So we add a pre-step to find the building from B that are close from A.<br>


<br>The final query looks like this (I can't test it here). Please note that this is suboptimal and could be written with far less CTE (only 2) (although not as clearly).<br>Please also note that everything is symmetrical between A and B. meaning that the matching B<->A is the same result a the matching A<->B. this should be the case! <br>


<br><br>CREATE TABLE A_matching_B AS<br>WITH geometry_filtering AS ( --for every building in A, find the building in B that could be potential matches<br>    SELECT A.id AS id_a, A.geom AS geom_a, B.id AS id_b, B.geom  AS geom_b<br>


    FROM A,B<br>    WHERE ST_DWithin(1.geom,B.geom,d) =TRUE --note , can be replaced by "ST_Intersects(A.geom, B.geom)= TRUE" if you don't fear precision issues<br>    --note : this query gives pairs of building from (A,B) that are potential matching<br>


)<br>,computing_score AS ( --for each potential matching, compute the score of this pair<br>    SELECT id_a , id_b<br>        , ST_Area(ST_Intersection(geom_a,geom_b)) as score <br>             --note : can be replaced by something more subtle if you have more attributes / measure<br>


</div><div>             --note : two identical buildings would have a big score, two totally different vuilding would have a score of 0<br>        , LOWEST(ST_Area(geom_a),ST_Area(geom_b)) AS lowest_area --we keep it for latter<br>


</div><div>    FROM geometry_filtering<br>)<br>,choosing_0_or_1_match AS ( --we are going to keep at most 1 pair per building.<br>    SELECT DISTINCT ON (id_a,id_b) id_a, id_b --note that the distinct close could simply be (id_a), we keep id_b for symmetry sake.<br>


        ,score ,lowest_area<br>    FROM computing_score<br>    WHERE score > T --here we allow the possibility that a building has no match<br>    ORDER BY id_a ASC, score DESC ,id_b ASC --this is paramount. Combined with the DISTINCT, it ensure for each building of A, we get the building from B that has the highest score<br>


) <br>,has_the_building_changed AS ( --this is optional. We fabric a boolean to decide if the two matching buildings are different or not.<br>    SELECT *<br>        , CASE WHEN abs(1-score/lowests_area)>0.01 --this is to allow precision issues : some building could be identical but footprints differing very little due to rounding precision changes<br>


                THEN TRUE <br>            ELSE <br>                FALSE<br>            END AS has_the_building_changed<br>    FROM choosing_0_or_1_match<br>)<br>    SELECT gid_a , gid_b --this are the final matching pairs<br>


    FROM has_the_building_changed ;<br>    <br>    <br>Now you have a table which give you the information<br>_which building from A is the same as which building from B<br>_which building from A is the same building but has changed its footprint from which building from B<br>


<br>You still need to get the building from A that have been destroyed in B and the building from B that are not in A (they have been constructed).<br><br>You can do this the following way :<br>if a building from A is not in the A_matching_B table, it means it has been destroyed<br>


if a building from B is not in the A_matching_B table, it means it has been constructed.<br><br><br>You can round all of this in a single query :<br><br>CREATE TABLE A_full_matching_B AS <br><br>    SELECT id AS id_a, NULL::int as id_b, 'in_A_but_not_B___destroyed' AS status<br>


    FROM A<br>    WHERE NOT EXISTS (SELECT 1 FROM A_matching_B WHERE A.id= A_matching_B.id_a)<br>UNION ALL<br>    SELECT id_a , id_b,  'identical' AS status<br>    FROM A_matching_B<br>    WHERE has_the_building_changed = FALSE<br>


UNION ALL<br>    SELECT id_a , id_b,  'changed' AS status<br>    FROM A_matching_B<br>    WHERE has_the_building_changed = TRUE<br>UNION ALL<br>    SELECT NULL::int AS id_a,id_b, 'in_B_but_not_A____constructed' AS status<br>


    FROM B<br>    WHERE NOT EXISTS (SELECT 1 FROM A_matching_B WHERE B.id= A_matching_B.id_a) ;<br>    <br><br>To test this, please place a "LIMIT 1000" in the first CTE, and be sure to have indexes on id and geom from both tables (no need for id if they are primary key)<br>


I hope this has been useful and would be glad to have some timings of execution and result in your case.<br>I would expect something around 10 minutes?<br><br>Cheers,<br>Rémi-C<br></div></div></div>
<br>_______________________________________________<br>
postgis-users mailing list<br>
<a href="mailto:postgis-users@lists.osgeo.org">postgis-users@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users" target="_blank">http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users</a><br></blockquote></div><br><br clear="all"><div><br></div>-- <br><div dir="ltr">

<div>@osm_seattle<br></div><div><a href="http://osm_seattle.snowandsnow.us" target="_blank">osm_seattle.snowandsnow.us</a></div><div>OpenStreetMap: Maps with a human touch</div></div>
</div>