Skip to content

Commit 1cf0a20

Browse files
committedFeb 22, 2017
[FEATURE][processing] New algorithm for topological coloring of polygons
This ports to old (pre 2.0!!) topocolor plugin to processing. It's based off my beta 2.x fork (never publicly released) which implemented a bunch of improvements to the algorithm allowing for minimal number of required colors and also balanced counts of features assigned each individual color. ** Pretty sure this plugin was highlighted in Victor's presentation about plugins-which-shouldn't-be-plugins-and-should-be-processing-algs instead. It's a prime example of a plugin where the amount of code required for gui+setup exceeded the actual "guts" of the plugin by a huge factor, and which is much more useful when it can be integrated into a larger processing model.
1 parent bde4ff9 commit 1cf0a20

File tree

8 files changed

+582
-1
lines changed

8 files changed

+582
-1
lines changed
 

‎python/plugins/processing/algs/help/qgis.yaml

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -544,6 +544,13 @@ qgis:symmetricaldifference: >
544544
qgis:texttofloat: >
545545
This algorithm modifies the type of a given attribute in a vector layer, converting a text attribute containing numeric strings into a numeric attribute.
546546

547+
qgis:topologicalcoloring: >
548+
This algorithm assigns a color index to polygon features in such a way that no adjacent polygons share the same color index.
549+
550+
The algorithm attempts to assign colors so that the total number of colors required is minimized, whilst keeping the count of features assigned to each individual color index balanced.
551+
552+
The color index is saved to a new attribute named color_idx.
553+
547554
qgis:translate: >
548555
This algorithm moves the geometries within a layer, by offsetting them with a specified x and y displacement.
549556

@@ -595,3 +602,4 @@ qgis:fixgeometries: >
595602
This algorithm attempts to create a valid representation of a given invalid geometry without losing any of the input vertices. Already-valid geometries are returned without further intervention. Always outputs multi-geometry layer.
596603

597604
NOTE: M values will be dropped from the output.
605+

‎python/plugins/processing/algs/qgis/QGISAlgorithmProvider.py

100644100755
Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -186,6 +186,7 @@
186186
from .FixGeometry import FixGeometry
187187
from .ExecuteSQL import ExecuteSQL
188188
from .FindProjection import FindProjection
189+
from .TopoColors import TopoColor
189190

190191
pluginPath = os.path.normpath(os.path.join(
191192
os.path.split(os.path.dirname(__file__))[0], os.pardir))
@@ -255,7 +256,8 @@ def __init__(self):
255256
ShortestPathPointToPoint(), ShortestPathPointToLayer(),
256257
ShortestPathLayerToPoint(), ServiceAreaFromPoint(),
257258
ServiceAreaFromLayer(), TruncateTable(), Polygonize(),
258-
FixGeometry(), ExecuteSQL(), FindProjection()
259+
FixGeometry(), ExecuteSQL(), FindProjection(),
260+
TopoColor()
259261
]
260262

261263
if hasPlotly:
Lines changed: 218 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,218 @@
1+
# -*- coding: utf-8 -*-
2+
3+
"""
4+
***************************************************************************
5+
TopoColors.py
6+
--------------
7+
Date : February 2017
8+
Copyright : (C) 2017 by Nyall Dawson
9+
Email : nyall dot dawson at gmail dot com
10+
***************************************************************************
11+
* *
12+
* This program is free software; you can redistribute it and/or modify *
13+
* it under the terms of the GNU General Public License as published by *
14+
* the Free Software Foundation; either version 2 of the License, or *
15+
* (at your option) any later version. *
16+
* *
17+
***************************************************************************
18+
"""
19+
20+
__author__ = 'Nyall Dawson'
21+
__date__ = 'February 2017'
22+
__copyright__ = '(C) 2017, Nyall Dawson'
23+
24+
# This will get replaced with a git SHA1 when you do a git archive323
25+
26+
__revision__ = '$Format:%H$'
27+
28+
import os
29+
import operator
30+
from collections import defaultdict, deque
31+
32+
from qgis.core import (QgsField,
33+
QgsGeometry,
34+
QgsSpatialIndex,
35+
NULL)
36+
37+
from qgis.PyQt.QtCore import (QVariant)
38+
39+
from processing.core.GeoAlgorithm import GeoAlgorithm
40+
from processing.core.parameters import ParameterVector
41+
from processing.core.outputs import OutputVector
42+
from processing.tools import dataobjects, vector
43+
44+
pluginPath = os.path.split(os.path.split(os.path.dirname(__file__))[0])[0]
45+
46+
47+
class TopoColor(GeoAlgorithm):
48+
INPUT_LAYER = 'INPUT_LAYER'
49+
OUTPUT_LAYER = 'OUTPUT_LAYER'
50+
51+
def defineCharacteristics(self):
52+
self.name, self.i18n_name = self.trAlgorithm('Topological coloring')
53+
self.group, self.i18n_group = self.trAlgorithm('Cartographic tools')
54+
self.tags = self.tr('topocolor,colors,graph,adjacent,assign')
55+
56+
self.addParameter(ParameterVector(self.INPUT_LAYER,
57+
self.tr('Input layer'), [dataobjects.TYPE_VECTOR_POLYGON]))
58+
59+
self.addOutput(OutputVector(self.OUTPUT_LAYER, self.tr('Colored'), datatype=[dataobjects.TYPE_VECTOR_POLYGON]))
60+
61+
def processAlgorithm(self, feedback):
62+
layer = dataobjects.getObjectFromUri(
63+
self.getParameterValue(self.INPUT_LAYER))
64+
65+
fields = layer.fields()
66+
fields.append(QgsField('color_id', QVariant.Int))
67+
68+
writer = self.getOutputFromName(
69+
self.OUTPUT_LAYER).getVectorWriter(
70+
fields,
71+
layer.wkbType(),
72+
layer.crs())
73+
74+
# use a deque so we can drop features as we write them
75+
# it's a bit friendlier on memory usage
76+
features = deque(f for f in vector.features(layer))
77+
78+
topology, id_graph = self.compute_graph(features, feedback)
79+
feature_colors = ColoringAlgorithm.balanced(topology, feedback)
80+
81+
max_colors = max(feature_colors.values())
82+
feedback.pushInfo(self.tr('{} colors required').format(max_colors))
83+
84+
total = 20.0 / len(features)
85+
current = 0
86+
while features:
87+
input_feature = features.popleft()
88+
output_feature = input_feature
89+
attributes = input_feature.attributes()
90+
if input_feature.id() in feature_colors:
91+
attributes.append(feature_colors[input_feature.id()])
92+
else:
93+
attributes.append(NULL)
94+
output_feature.setAttributes(attributes)
95+
96+
writer.addFeature(output_feature)
97+
current += 1
98+
feedback.setProgress(80 + int(current * total))
99+
100+
del writer
101+
102+
@staticmethod
103+
def compute_graph(features, feedback, create_id_graph=False):
104+
""" compute topology from a layer/field """
105+
s = Graph(sort_graph=False)
106+
id_graph = None
107+
if create_id_graph:
108+
id_graph = Graph(sort_graph=True)
109+
110+
# skip features without geometry
111+
features_with_geometry = dict((f.id(), f) for f in features if f.hasGeometry())
112+
113+
total = 70.0 / len(features_with_geometry)
114+
index = QgsSpatialIndex()
115+
116+
i = 0
117+
for feature_id, f in features_with_geometry.items():
118+
engine = QgsGeometry.createGeometryEngine(f.geometry().geometry())
119+
engine.prepareGeometry()
120+
121+
feature_bounds = f.geometry().boundingBox()
122+
# grow bounds a little so we get touching features
123+
feature_bounds.grow(feature_bounds.width() * 0.01)
124+
intersections = index.intersects(feature_bounds)
125+
for l2 in intersections:
126+
f2 = features_with_geometry[l2]
127+
if engine.intersects(f2.geometry().geometry()):
128+
s.add_edge(f.id(), f2.id())
129+
s.add_edge(f2.id(), f.id())
130+
if id_graph:
131+
id_graph.add_edge(f.id(), f2.id())
132+
133+
index.insertFeature(f)
134+
i += 1
135+
feedback.setProgress(int(i * total))
136+
137+
for feature_id, f in features_with_geometry.items():
138+
if not feature_id in s.node_edge:
139+
s.add_edge(feature_id, None)
140+
141+
return s, id_graph
142+
143+
144+
class ColoringAlgorithm:
145+
146+
@staticmethod
147+
def balanced(graph, feedback):
148+
feature_colors = {}
149+
# start with 4 colors in pool
150+
color_pool = set(range(1, 5))
151+
152+
# calculate count of neighbours
153+
neighbour_count = defaultdict(int)
154+
for feature_id, neighbours in graph.node_edge.items():
155+
neighbour_count[feature_id] += len(neighbours)
156+
157+
# sort features by neighbour count - we want to handle those with more neighbours first
158+
sorted_by_count = [feature_id for feature_id in sorted(neighbour_count.items(),
159+
key=operator.itemgetter(1),
160+
reverse=True)]
161+
# counts for each color already assigned
162+
color_counts = defaultdict(int)
163+
for c in color_pool:
164+
color_counts[c] = 0
165+
166+
total = 10.0 / len(sorted_by_count)
167+
i = 0
168+
169+
for (feature_id, n) in sorted_by_count:
170+
# first work out which already assigned colors are adjacent to this feature
171+
adjacent_colors = set()
172+
for neighbour in graph.node_edge[feature_id]:
173+
if neighbour in feature_colors:
174+
adjacent_colors.add(feature_colors[neighbour])
175+
176+
# from the existing colors, work out which are available (ie non-adjacent)
177+
available_colors = color_pool.difference(adjacent_colors)
178+
179+
if len(available_colors) == 0:
180+
# no existing colors available for this feature, so add new color to pool
181+
feature_color = len(color_pool) + 1
182+
color_pool.add(feature_color)
183+
else:
184+
# choose least used available color
185+
counts = [(c, v) for c, v in color_counts.items() if c in available_colors]
186+
feature_color = sorted(counts, key=operator.itemgetter(1))[0][0]
187+
feature_colors[feature_id] = feature_color
188+
color_counts[feature_color] += 1
189+
190+
i += 1
191+
feedback.setProgress(70 + int(i * total))
192+
193+
return feature_colors
194+
195+
196+
class Graph:
197+
198+
def __init__(self, sort_graph=True):
199+
self.sort_graph = sort_graph
200+
self.node_edge = {}
201+
202+
def add_edge(self, i, j):
203+
ij = [i, j]
204+
if self.sort_graph:
205+
ij.sort()
206+
(i, j) = ij
207+
if i in self.node_edge:
208+
self.node_edge[i].add(j)
209+
else:
210+
self.node_edge[i] = {j}
211+
212+
def make_full(self):
213+
g = Graph(sort_graph=False)
214+
for k in self.node_edge.keys():
215+
for v in self.node_edge[k]:
216+
g.add_edge(v, k)
217+
g.add_edge(k, v)
218+
return g
Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
<GMLFeatureClassList>
2+
<GMLFeatureClass>
3+
<Name>adjacent_polys</Name>
4+
<ElementPath>adjacent_polys</ElementPath>
5+
<!--POLYGON-->
6+
<GeometryType>3</GeometryType>
7+
<SRSName>EPSG:4326</SRSName>
8+
<DatasetSpecificInfo>
9+
<FeatureCount>11</FeatureCount>
10+
<ExtentXMin>-0.76065</ExtentXMin>
11+
<ExtentXMax>14.23935</ExtentXMax>
12+
<ExtentYMin>-6.11331</ExtentYMin>
13+
<ExtentYMax>5.88669</ExtentYMax>
14+
</DatasetSpecificInfo>
15+
<PropertyDefn>
16+
<Name>left</Name>
17+
<ElementPath>left</ElementPath>
18+
<Type>Real</Type>
19+
</PropertyDefn>
20+
<PropertyDefn>
21+
<Name>top</Name>
22+
<ElementPath>top</ElementPath>
23+
<Type>Real</Type>
24+
</PropertyDefn>
25+
<PropertyDefn>
26+
<Name>right</Name>
27+
<ElementPath>right</ElementPath>
28+
<Type>Real</Type>
29+
</PropertyDefn>
30+
<PropertyDefn>
31+
<Name>bottom</Name>
32+
<ElementPath>bottom</ElementPath>
33+
<Type>Real</Type>
34+
</PropertyDefn>
35+
<PropertyDefn>
36+
<Name>id</Name>
37+
<ElementPath>id</ElementPath>
38+
<Type>Integer</Type>
39+
</PropertyDefn>
40+
</GMLFeatureClass>
41+
</GMLFeatureClassList>
Lines changed: 122 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,122 @@
1+
<?xml version="1.0" encoding="utf-8" ?>
2+
<ogr:FeatureCollection
3+
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
4+
xsi:schemaLocation=""
5+
xmlns:ogr="http://ogr.maptools.org/"
6+
xmlns:gml="http://www.opengis.net/gml">
7+
<gml:boundedBy>
8+
<gml:Box>
9+
<gml:coord><gml:X>-0.7606503579952282</gml:X><gml:Y>-6.113305489260142</gml:Y></gml:coord>
10+
<gml:coord><gml:X>14.23934964200477</gml:X><gml:Y>5.886694510739858</gml:Y></gml:coord>
11+
</gml:Box>
12+
</gml:boundedBy>
13+
14+
<gml:featureMember>
15+
<ogr:adjacent_polys fid="adjacent_polys.0">
16+
<ogr:geometryProperty><gml:Polygon srsName="EPSG:4326"><gml:outerBoundaryIs><gml:LinearRing><gml:coordinates>-0.760650357995228,-0.113305489260142 2.23934964200477,-0.113305489260142 2.23934964200477,-3.11330548926014 -0.760650357995228,-3.11330548926014 -0.760650357995228,-0.113305489260142</gml:coordinates></gml:LinearRing></gml:outerBoundaryIs></gml:Polygon></ogr:geometryProperty>
17+
<ogr:left>-0.76065</ogr:left>
18+
<ogr:top>-0.11331</ogr:top>
19+
<ogr:right>2.23935</ogr:right>
20+
<ogr:bottom>-3.11331</ogr:bottom>
21+
<ogr:id>3</ogr:id>
22+
</ogr:adjacent_polys>
23+
</gml:featureMember>
24+
<gml:featureMember>
25+
<ogr:adjacent_polys fid="adjacent_polys.1">
26+
<ogr:geometryProperty><gml:Polygon srsName="EPSG:4326"><gml:outerBoundaryIs><gml:LinearRing><gml:coordinates>-0.760650357995228,-3.11330548926014 2.23934964200477,-3.11330548926014 2.23934964200477,-6.11330548926014 -0.760650357995228,-6.11330548926014 -0.760650357995228,-3.11330548926014</gml:coordinates></gml:LinearRing></gml:outerBoundaryIs></gml:Polygon></ogr:geometryProperty>
27+
<ogr:left>-0.76065</ogr:left>
28+
<ogr:top>-3.11331</ogr:top>
29+
<ogr:right>2.23935</ogr:right>
30+
<ogr:bottom>-6.11331</ogr:bottom>
31+
<ogr:id>4</ogr:id>
32+
</ogr:adjacent_polys>
33+
</gml:featureMember>
34+
<gml:featureMember>
35+
<ogr:adjacent_polys fid="adjacent_polys.2">
36+
<ogr:geometryProperty><gml:Polygon srsName="EPSG:4326"><gml:outerBoundaryIs><gml:LinearRing><gml:coordinates>5.23934964200477,-0.113305489260142 8.23934964200477,-0.113305489260142 8.23934964200477,-3.11330548926014 5.23934964200477,-3.11330548926014 5.23934964200477,-0.113305489260142</gml:coordinates></gml:LinearRing></gml:outerBoundaryIs></gml:Polygon></ogr:geometryProperty>
37+
<ogr:left>5.23935</ogr:left>
38+
<ogr:top>-0.11331</ogr:top>
39+
<ogr:right>8.23935</ogr:right>
40+
<ogr:bottom>-3.11331</ogr:bottom>
41+
<ogr:id>11</ogr:id>
42+
</ogr:adjacent_polys>
43+
</gml:featureMember>
44+
<gml:featureMember>
45+
<ogr:adjacent_polys fid="adjacent_polys.3">
46+
<ogr:geometryProperty><gml:Polygon srsName="EPSG:4326"><gml:outerBoundaryIs><gml:LinearRing><gml:coordinates>5.23934964200477,-3.11330548926014 8.23934964200477,-3.11330548926014 8.23934964200477,-6.11330548926014 5.23934964200477,-6.11330548926014 5.23934964200477,-3.11330548926014</gml:coordinates></gml:LinearRing></gml:outerBoundaryIs></gml:Polygon></ogr:geometryProperty>
47+
<ogr:left>5.23935</ogr:left>
48+
<ogr:top>-3.11331</ogr:top>
49+
<ogr:right>8.23935</ogr:right>
50+
<ogr:bottom>-6.11331</ogr:bottom>
51+
<ogr:id>12</ogr:id>
52+
</ogr:adjacent_polys>
53+
</gml:featureMember>
54+
<gml:featureMember>
55+
<ogr:adjacent_polys fid="adjacent_polys.4">
56+
<ogr:geometryProperty><gml:Polygon srsName="EPSG:4326"><gml:outerBoundaryIs><gml:LinearRing><gml:coordinates>8.23934964200477,-3.11330548926014 11.2393496420048,-3.11330548926014 11.2393496420048,-6.11330548926014 8.23934964200477,-6.11330548926014 8.23934964200477,-3.11330548926014</gml:coordinates></gml:LinearRing></gml:outerBoundaryIs></gml:Polygon></ogr:geometryProperty>
57+
<ogr:left>8.23935</ogr:left>
58+
<ogr:top>-3.11331</ogr:top>
59+
<ogr:right>11.23935</ogr:right>
60+
<ogr:bottom>-6.11331</ogr:bottom>
61+
<ogr:id>16</ogr:id>
62+
</ogr:adjacent_polys>
63+
</gml:featureMember>
64+
<gml:featureMember>
65+
<ogr:adjacent_polys fid="adjacent_polys.5">
66+
<ogr:geometryProperty><gml:Polygon srsName="EPSG:4326"><gml:outerBoundaryIs><gml:LinearRing><gml:coordinates>11.2393496420048,-0.113305489260142 14.2393496420048,-0.113305489260142 14.2393496420048,-3.11330548926014 11.2393496420048,-3.11330548926014 11.2393496420048,-0.113305489260142</gml:coordinates></gml:LinearRing></gml:outerBoundaryIs></gml:Polygon></ogr:geometryProperty>
67+
<ogr:left>11.23935</ogr:left>
68+
<ogr:top>-0.11331</ogr:top>
69+
<ogr:right>14.23935</ogr:right>
70+
<ogr:bottom>-3.11331</ogr:bottom>
71+
<ogr:id>19</ogr:id>
72+
</ogr:adjacent_polys>
73+
</gml:featureMember>
74+
<gml:featureMember>
75+
<ogr:adjacent_polys fid="adjacent_polys.6">
76+
<ogr:geometryProperty><gml:Polygon srsName="EPSG:4326"><gml:outerBoundaryIs><gml:LinearRing><gml:coordinates>11.2393496420048,-3.11330548926014 14.2393496420048,-3.11330548926014 14.2393496420048,-6.11330548926014 11.2393496420048,-6.11330548926014 11.2393496420048,-3.11330548926014</gml:coordinates></gml:LinearRing></gml:outerBoundaryIs></gml:Polygon></ogr:geometryProperty>
77+
<ogr:left>11.23935</ogr:left>
78+
<ogr:top>-3.11331</ogr:top>
79+
<ogr:right>14.23935</ogr:right>
80+
<ogr:bottom>-6.11331</ogr:bottom>
81+
<ogr:id>20</ogr:id>
82+
</ogr:adjacent_polys>
83+
</gml:featureMember>
84+
<gml:featureMember>
85+
<ogr:adjacent_polys fid="adjacent_polys.7">
86+
<ogr:geometryProperty><gml:Polygon srsName="EPSG:4326"><gml:outerBoundaryIs><gml:LinearRing><gml:coordinates>2.23934964200477,5.88669451073986 5.23934964200477,5.88669451073986 5.23934964200477,2.88669451073986 2.23934964200477,2.88669451073986 2.23934964200477,-0.113305489260142 -0.760650357995228,-0.113305489260142 -0.760650357995228,2.88669451073986 -0.760650357995228,5.88669451073986 2.23934964200477,5.88669451073986</gml:coordinates></gml:LinearRing></gml:outerBoundaryIs></gml:Polygon></ogr:geometryProperty>
87+
<ogr:left>2.23935</ogr:left>
88+
<ogr:top>5.88669</ogr:top>
89+
<ogr:right>5.23935</ogr:right>
90+
<ogr:bottom>2.88669</ogr:bottom>
91+
<ogr:id>5</ogr:id>
92+
</ogr:adjacent_polys>
93+
</gml:featureMember>
94+
<gml:featureMember>
95+
<ogr:adjacent_polys fid="adjacent_polys.8">
96+
<ogr:geometryProperty><gml:Polygon srsName="EPSG:4326"><gml:outerBoundaryIs><gml:LinearRing><gml:coordinates>5.23934964200477,2.88669451073986 8.23934964200477,2.88669451073986 11.2393496420048,2.88669451073986 11.2393496420048,-0.113305489260142 11.2393496420048,-3.11330548926014 8.23934964200477,-3.11330548926014 8.23934964200477,-0.113305489260142 5.23934964200477,-0.113305489260142 5.23934964200477,2.88669451073986</gml:coordinates></gml:LinearRing></gml:outerBoundaryIs></gml:Polygon></ogr:geometryProperty>
97+
<ogr:left>5.23935</ogr:left>
98+
<ogr:top>2.88669</ogr:top>
99+
<ogr:right>8.23935</ogr:right>
100+
<ogr:id>10</ogr:id>
101+
</ogr:adjacent_polys>
102+
</gml:featureMember>
103+
<gml:featureMember>
104+
<ogr:adjacent_polys fid="adjacent_polys.9">
105+
<ogr:geometryProperty><gml:Polygon srsName="EPSG:4326"><gml:outerBoundaryIs><gml:LinearRing><gml:coordinates>2.23934964200477,2.88669451073986 5.23934964200477,2.88669451073986 5.23934964200477,-0.113305489260142 5.23934964200477,-3.11330548926014 5.23934964200477,-6.11330548926014 2.23934964200477,-6.11330548926014 2.23934964200477,-3.11330548926014 2.23934964200477,-0.113305489260142 2.23934964200477,2.88669451073986</gml:coordinates></gml:LinearRing></gml:outerBoundaryIs></gml:Polygon></ogr:geometryProperty>
106+
<ogr:left>2.23935</ogr:left>
107+
<ogr:top>2.88669</ogr:top>
108+
<ogr:right>5.23935</ogr:right>
109+
<ogr:id>6</ogr:id>
110+
</ogr:adjacent_polys>
111+
</gml:featureMember>
112+
<gml:featureMember>
113+
<ogr:adjacent_polys fid="adjacent_polys.10">
114+
<ogr:geometryProperty><gml:Polygon srsName="EPSG:4326"><gml:outerBoundaryIs><gml:LinearRing><gml:coordinates>5.23934964200477,5.88669451073986 8.23934964200477,5.88669451073986 11.2393496420048,5.88669451073986 14.2393496420048,5.88669451073986 14.2393496420048,2.88669451073986 14.2393496420048,-0.113305489260142 11.2393496420048,-0.113305489260142 11.2393496420048,2.88669451073986 8.23934964200477,2.88669451073986 5.23934964200477,2.88669451073986 5.23934964200477,5.88669451073986</gml:coordinates></gml:LinearRing></gml:outerBoundaryIs></gml:Polygon></ogr:geometryProperty>
115+
<ogr:left>5.23935</ogr:left>
116+
<ogr:top>5.88669</ogr:top>
117+
<ogr:right>8.23935</ogr:right>
118+
<ogr:bottom>2.88669</ogr:bottom>
119+
<ogr:id>9</ogr:id>
120+
</ogr:adjacent_polys>
121+
</gml:featureMember>
122+
</ogr:FeatureCollection>
Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
<GMLFeatureClassList>
2+
<GMLFeatureClass>
3+
<Name>topocolor_polys</Name>
4+
<ElementPath>topocolor_polys</ElementPath>
5+
<!--POLYGON-->
6+
<GeometryType>3</GeometryType>
7+
<SRSName>EPSG:4326</SRSName>
8+
<DatasetSpecificInfo>
9+
<FeatureCount>11</FeatureCount>
10+
<ExtentXMin>-0.76065</ExtentXMin>
11+
<ExtentXMax>14.23935</ExtentXMax>
12+
<ExtentYMin>-6.11331</ExtentYMin>
13+
<ExtentYMax>5.88669</ExtentYMax>
14+
</DatasetSpecificInfo>
15+
<PropertyDefn>
16+
<Name>left</Name>
17+
<ElementPath>left</ElementPath>
18+
<Type>Real</Type>
19+
</PropertyDefn>
20+
<PropertyDefn>
21+
<Name>top</Name>
22+
<ElementPath>top</ElementPath>
23+
<Type>Real</Type>
24+
</PropertyDefn>
25+
<PropertyDefn>
26+
<Name>right</Name>
27+
<ElementPath>right</ElementPath>
28+
<Type>Real</Type>
29+
</PropertyDefn>
30+
<PropertyDefn>
31+
<Name>bottom</Name>
32+
<ElementPath>bottom</ElementPath>
33+
<Type>Real</Type>
34+
</PropertyDefn>
35+
<PropertyDefn>
36+
<Name>id</Name>
37+
<ElementPath>id</ElementPath>
38+
<Type>Integer</Type>
39+
</PropertyDefn>
40+
<PropertyDefn>
41+
<Name>color_id</Name>
42+
<ElementPath>color_id</ElementPath>
43+
<Type>Integer</Type>
44+
</PropertyDefn>
45+
</GMLFeatureClass>
46+
</GMLFeatureClassList>
Lines changed: 133 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,133 @@
1+
<?xml version="1.0" encoding="utf-8" ?>
2+
<ogr:FeatureCollection
3+
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
4+
xsi:schemaLocation=""
5+
xmlns:ogr="http://ogr.maptools.org/"
6+
xmlns:gml="http://www.opengis.net/gml">
7+
<gml:boundedBy>
8+
<gml:Box>
9+
<gml:coord><gml:X>-0.760650357995228</gml:X><gml:Y>-6.11330548926014</gml:Y></gml:coord>
10+
<gml:coord><gml:X>14.2393496420048</gml:X><gml:Y>5.88669451073986</gml:Y></gml:coord>
11+
</gml:Box>
12+
</gml:boundedBy>
13+
14+
<gml:featureMember>
15+
<ogr:topocolor_polys fid="adjacent_polys.0">
16+
<ogr:geometryProperty><gml:Polygon srsName="EPSG:4326"><gml:outerBoundaryIs><gml:LinearRing><gml:coordinates>-0.760650357995228,-0.113305489260142 2.23934964200477,-0.113305489260142 2.23934964200477,-3.11330548926014 -0.760650357995228,-3.11330548926014 -0.760650357995228,-0.113305489260142</gml:coordinates></gml:LinearRing></gml:outerBoundaryIs></gml:Polygon></ogr:geometryProperty>
17+
<ogr:left>-0.76065</ogr:left>
18+
<ogr:top>-0.11331</ogr:top>
19+
<ogr:right>2.23935</ogr:right>
20+
<ogr:bottom>-3.11331</ogr:bottom>
21+
<ogr:id>3</ogr:id>
22+
<ogr:color_id>1</ogr:color_id>
23+
</ogr:topocolor_polys>
24+
</gml:featureMember>
25+
<gml:featureMember>
26+
<ogr:topocolor_polys fid="adjacent_polys.1">
27+
<ogr:geometryProperty><gml:Polygon srsName="EPSG:4326"><gml:outerBoundaryIs><gml:LinearRing><gml:coordinates>-0.760650357995228,-3.11330548926014 2.23934964200477,-3.11330548926014 2.23934964200477,-6.11330548926014 -0.760650357995228,-6.11330548926014 -0.760650357995228,-3.11330548926014</gml:coordinates></gml:LinearRing></gml:outerBoundaryIs></gml:Polygon></ogr:geometryProperty>
28+
<ogr:left>-0.76065</ogr:left>
29+
<ogr:top>-3.11331</ogr:top>
30+
<ogr:right>2.23935</ogr:right>
31+
<ogr:bottom>-6.11331</ogr:bottom>
32+
<ogr:id>4</ogr:id>
33+
<ogr:color_id>3</ogr:color_id>
34+
</ogr:topocolor_polys>
35+
</gml:featureMember>
36+
<gml:featureMember>
37+
<ogr:topocolor_polys fid="adjacent_polys.2">
38+
<ogr:geometryProperty><gml:Polygon srsName="EPSG:4326"><gml:outerBoundaryIs><gml:LinearRing><gml:coordinates>5.23934964200477,-0.113305489260142 8.23934964200477,-0.113305489260142 8.23934964200477,-3.11330548926014 5.23934964200477,-3.11330548926014 5.23934964200477,-0.113305489260142</gml:coordinates></gml:LinearRing></gml:outerBoundaryIs></gml:Polygon></ogr:geometryProperty>
39+
<ogr:left>5.23935</ogr:left>
40+
<ogr:top>-0.11331</ogr:top>
41+
<ogr:right>8.23935</ogr:right>
42+
<ogr:bottom>-3.11331</ogr:bottom>
43+
<ogr:id>11</ogr:id>
44+
<ogr:color_id>4</ogr:color_id>
45+
</ogr:topocolor_polys>
46+
</gml:featureMember>
47+
<gml:featureMember>
48+
<ogr:topocolor_polys fid="adjacent_polys.3">
49+
<ogr:geometryProperty><gml:Polygon srsName="EPSG:4326"><gml:outerBoundaryIs><gml:LinearRing><gml:coordinates>5.23934964200477,-3.11330548926014 8.23934964200477,-3.11330548926014 8.23934964200477,-6.11330548926014 5.23934964200477,-6.11330548926014 5.23934964200477,-3.11330548926014</gml:coordinates></gml:LinearRing></gml:outerBoundaryIs></gml:Polygon></ogr:geometryProperty>
50+
<ogr:left>5.23935</ogr:left>
51+
<ogr:top>-3.11331</ogr:top>
52+
<ogr:right>8.23935</ogr:right>
53+
<ogr:bottom>-6.11331</ogr:bottom>
54+
<ogr:id>12</ogr:id>
55+
<ogr:color_id>5</ogr:color_id>
56+
</ogr:topocolor_polys>
57+
</gml:featureMember>
58+
<gml:featureMember>
59+
<ogr:topocolor_polys fid="adjacent_polys.4">
60+
<ogr:geometryProperty><gml:Polygon srsName="EPSG:4326"><gml:outerBoundaryIs><gml:LinearRing><gml:coordinates>8.23934964200477,-3.11330548926014 11.2393496420048,-3.11330548926014 11.2393496420048,-6.11330548926014 8.23934964200477,-6.11330548926014 8.23934964200477,-3.11330548926014</gml:coordinates></gml:LinearRing></gml:outerBoundaryIs></gml:Polygon></ogr:geometryProperty>
61+
<ogr:left>8.23935</ogr:left>
62+
<ogr:top>-3.11331</ogr:top>
63+
<ogr:right>11.23935</ogr:right>
64+
<ogr:bottom>-6.11331</ogr:bottom>
65+
<ogr:id>16</ogr:id>
66+
<ogr:color_id>3</ogr:color_id>
67+
</ogr:topocolor_polys>
68+
</gml:featureMember>
69+
<gml:featureMember>
70+
<ogr:topocolor_polys fid="adjacent_polys.5">
71+
<ogr:geometryProperty><gml:Polygon srsName="EPSG:4326"><gml:outerBoundaryIs><gml:LinearRing><gml:coordinates>11.2393496420048,-0.113305489260142 14.2393496420048,-0.113305489260142 14.2393496420048,-3.11330548926014 11.2393496420048,-3.11330548926014 11.2393496420048,-0.113305489260142</gml:coordinates></gml:LinearRing></gml:outerBoundaryIs></gml:Polygon></ogr:geometryProperty>
72+
<ogr:left>11.23935</ogr:left>
73+
<ogr:top>-0.11331</ogr:top>
74+
<ogr:right>14.23935</ogr:right>
75+
<ogr:bottom>-3.11331</ogr:bottom>
76+
<ogr:id>19</ogr:id>
77+
<ogr:color_id>2</ogr:color_id>
78+
</ogr:topocolor_polys>
79+
</gml:featureMember>
80+
<gml:featureMember>
81+
<ogr:topocolor_polys fid="adjacent_polys.6">
82+
<ogr:geometryProperty><gml:Polygon srsName="EPSG:4326"><gml:outerBoundaryIs><gml:LinearRing><gml:coordinates>11.2393496420048,-3.11330548926014 14.2393496420048,-3.11330548926014 14.2393496420048,-6.11330548926014 11.2393496420048,-6.11330548926014 11.2393496420048,-3.11330548926014</gml:coordinates></gml:LinearRing></gml:outerBoundaryIs></gml:Polygon></ogr:geometryProperty>
83+
<ogr:left>11.23935</ogr:left>
84+
<ogr:top>-3.11331</ogr:top>
85+
<ogr:right>14.23935</ogr:right>
86+
<ogr:bottom>-6.11331</ogr:bottom>
87+
<ogr:id>20</ogr:id>
88+
<ogr:color_id>5</ogr:color_id>
89+
</ogr:topocolor_polys>
90+
</gml:featureMember>
91+
<gml:featureMember>
92+
<ogr:topocolor_polys fid="adjacent_polys.7">
93+
<ogr:geometryProperty><gml:Polygon srsName="EPSG:4326"><gml:outerBoundaryIs><gml:LinearRing><gml:coordinates>2.23934964200477,5.88669451073986 5.23934964200477,5.88669451073986 5.23934964200477,2.88669451073986 2.23934964200477,2.88669451073986 2.23934964200477,-0.113305489260142 -0.760650357995228,-0.113305489260142 -0.760650357995228,2.88669451073986 -0.760650357995228,5.88669451073986 2.23934964200477,5.88669451073986</gml:coordinates></gml:LinearRing></gml:outerBoundaryIs></gml:Polygon></ogr:geometryProperty>
94+
<ogr:left>2.23935</ogr:left>
95+
<ogr:top>5.88669</ogr:top>
96+
<ogr:right>5.23935</ogr:right>
97+
<ogr:bottom>2.88669</ogr:bottom>
98+
<ogr:id>5</ogr:id>
99+
<ogr:color_id>3</ogr:color_id>
100+
</ogr:topocolor_polys>
101+
</gml:featureMember>
102+
<gml:featureMember>
103+
<ogr:topocolor_polys fid="adjacent_polys.8">
104+
<ogr:geometryProperty><gml:Polygon srsName="EPSG:4326"><gml:outerBoundaryIs><gml:LinearRing><gml:coordinates>5.23934964200477,2.88669451073986 8.23934964200477,2.88669451073986 11.2393496420048,2.88669451073986 11.2393496420048,-0.113305489260142 11.2393496420048,-3.11330548926014 8.23934964200477,-3.11330548926014 8.23934964200477,-0.113305489260142 5.23934964200477,-0.113305489260142 5.23934964200477,2.88669451073986</gml:coordinates></gml:LinearRing></gml:outerBoundaryIs></gml:Polygon></ogr:geometryProperty>
105+
<ogr:left>5.23935</ogr:left>
106+
<ogr:top>2.88669</ogr:top>
107+
<ogr:right>8.23935</ogr:right>
108+
<ogr:id>10</ogr:id>
109+
<ogr:color_id>1</ogr:color_id>
110+
</ogr:topocolor_polys>
111+
</gml:featureMember>
112+
<gml:featureMember>
113+
<ogr:topocolor_polys fid="adjacent_polys.9">
114+
<ogr:geometryProperty><gml:Polygon srsName="EPSG:4326"><gml:outerBoundaryIs><gml:LinearRing><gml:coordinates>2.23934964200477,2.88669451073986 5.23934964200477,2.88669451073986 5.23934964200477,-0.113305489260142 5.23934964200477,-3.11330548926014 5.23934964200477,-6.11330548926014 2.23934964200477,-6.11330548926014 2.23934964200477,-3.11330548926014 2.23934964200477,-0.113305489260142 2.23934964200477,2.88669451073986</gml:coordinates></gml:LinearRing></gml:outerBoundaryIs></gml:Polygon></ogr:geometryProperty>
115+
<ogr:left>2.23935</ogr:left>
116+
<ogr:top>2.88669</ogr:top>
117+
<ogr:right>5.23935</ogr:right>
118+
<ogr:id>6</ogr:id>
119+
<ogr:color_id>2</ogr:color_id>
120+
</ogr:topocolor_polys>
121+
</gml:featureMember>
122+
<gml:featureMember>
123+
<ogr:topocolor_polys fid="adjacent_polys.10">
124+
<ogr:geometryProperty><gml:Polygon srsName="EPSG:4326"><gml:outerBoundaryIs><gml:LinearRing><gml:coordinates>5.23934964200477,5.88669451073986 8.23934964200477,5.88669451073986 11.2393496420048,5.88669451073986 14.2393496420048,5.88669451073986 14.2393496420048,2.88669451073986 14.2393496420048,-0.113305489260142 11.2393496420048,-0.113305489260142 11.2393496420048,2.88669451073986 8.23934964200477,2.88669451073986 5.23934964200477,2.88669451073986 5.23934964200477,5.88669451073986</gml:coordinates></gml:LinearRing></gml:outerBoundaryIs></gml:Polygon></ogr:geometryProperty>
125+
<ogr:left>5.23935</ogr:left>
126+
<ogr:top>5.88669</ogr:top>
127+
<ogr:right>8.23935</ogr:right>
128+
<ogr:bottom>2.88669</ogr:bottom>
129+
<ogr:id>9</ogr:id>
130+
<ogr:color_id>4</ogr:color_id>
131+
</ogr:topocolor_polys>
132+
</gml:featureMember>
133+
</ogr:FeatureCollection>

‎python/plugins/processing/tests/testdata/qgis_algorithm_tests.yaml

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2372,3 +2372,14 @@ tests:
23722372
OUTPUT:
23732373
name: expected/polygon_from_extent.gml
23742374
type: vector
2375+
2376+
- algorithm: qgis:topologicalcoloring
2377+
name: Topological coloring
2378+
params:
2379+
INPUT_LAYER:
2380+
name: custom/adjacent_polys.gml
2381+
type: vector
2382+
results:
2383+
OUTPUT_LAYER:
2384+
name: expected/topocolor_polys.gml
2385+
type: vector

0 commit comments

Comments
 (0)
Please sign in to comment.