[Imports] [OSM-dev] Polygon relationificator

[Iván Sánchez Ortega]

El Lunes, 14 de Septiembre de 2009, Ian Dees escribió:
> This feature could be added, but could you draw a couple pictures to
> explain what you mean? What happens with the graph edges inside the
> multipolygon? Since they aren't really polygons, do they belong in a
> multipolygon relation? Maybe I'm not correctly interpreting what you meant.

OK, let's do some crapy ASCII-art. So set your e-mail readers to a fixed-width 
font.

Suppose a .osm file containing the following polygons and nodes. Suppose that 
the polygons are originally ways.


n4-------------------------n3-------------------n2---n1
|                          |                    |    |
|                          |                    | P1 |
|                          |                    |    |
|                          |                    n6----n5
|                          |                    |
|                    n11--n10                   |
n19      P4           |    |         P2         |
|                     | P3 |                    n7
|                    n12---n9                   |
|                     |                         n8
|                     |                         |
n18--n17---n16-------n15---------n14------------n13
|                                               |
|                                               |
|                   P5                          |
|                                               |
n21-----------------------n20------------------n19


For every pair of connected nodes (segment i.e. graph edges), relate that 
segment to a set of one or two polygons. Any adjacent segments related to the 
same set of polygons gets converted into a way (i.e. simplified graph edges):


n4-AAAAAAAAAAAAAAAAAAAAAAAA-n3-BBBBBBBBBBBBBBBB--n2-E-n1
|                           |                    |    |
A                           H                    F P1 E
A                           H                    |    |
A                           H                    n6-E-n5
A                           |                    |
|                    n11-C-n10                   G
n19                   |     |                    |
|                     C P3  D                    n7
A         P4          |     |         P2         G
A                    n12-DD-n9                   G
A                     I                          n8
|                     I                          G
n18-J-n17-J-n16-JJJJ-n15-KKKKKKK-n14-KKKKKKKKKK-n13
|                                                |
L                                                L
L                   P5                           L
|                                                |
n21-LLLLLLLLLLLLLLLLLLLLL-n20-LLLLLLLLLLLLLLLL-n19


So this creates ways as follows:
A = n3-n4-n19-n18
B = n3-n2
C = n10-n11-n12
D = n10-n9-n12
E = n2-n1-n5-n6
F = n2-n6
G = n6-n7-n8-n13
H = n3-n10
I = n12-n15

(Please note H and I are both adjacent to both P4 and P2, but are different 
ways as they're not adjacent segments. Same goes to B and G.)

J = n18-n17-n16-n15
K = n15-n14-n13
L = n18-n21-n20-n19-n13

And then, given those, the algorithm destroys the original polygons-as-ways 
and reconstructs them as relations:

P1 = E-F
P2 = B-H-D-I-K-G-F
P3 = C-D
P4 = A-H-C-I-J
P5 = J-K-L



I think I make myself clear with those. Of course, if the inputs are 
multipolygons, the algorithm gets a little more complex, but the idea stays 
the same: *Any polygons that share at least one segment with another polygon 
should get converted into a relation of polygon edges*.


I would like to be able to convert and fix stuff properly... not to speak 
about those JOSM warnings about polygon ways sharing a segment.



P.S.: Remind me to take a course in computational geometry. I'm feeling like I 
need it.


Cheers,
-- 
----------------------------------
Iván Sánchez Ortega <ivan at sanchezortega.es>

Aviso: Este e-mail es confidencial y no debería ser usado por nadie que no sea 
el destinatario original. No se permite la reproducción mediante fotocopia, 
walkie-talkie, emisora de radioaficionado, satélite, televisión por cable, 
proyector, señales de humo, código morse, braille, lenguaje de signos, 
taquigrafía o cualquier otro medio. Bajo ningún concepto debe traducirse al 
francés este e-mail. Este e-mail no puede ser ridiculizado, parodiado, 
juzgado en una competición, o leído en voz alta con un acento gracioso 
llevando un bigote falso y/o cualquier tipo de sombrero, incluyendo pero no 
limitándose a pañuelos. No inciten ni provoquen a este e-mail. Si está 
medicándose, puede experimentar nauseas, desorientación, histeria, vómitos, 
pérdida temporal de la memoria a corto plazo y malestar general al leer este 
e-mail. Consulte a su médico o farmacéutico antes de leer este e-mail. Todas 
las modelos descritas en este e-mail son mayores de 18 años. Si ha recibido 
este e-mail por error es probablemente porque estaba borracho cuando escribí 
la dirección del destinatario.