ait-energy / qgis-edge-bundling Goto Github PK
View Code? Open in Web Editor NEWLicense: GNU General Public License v2.0
License: GNU General Public License v2.0
Hi Anita
I am trying to get the scripts to work, but currently without success. I have tried with and without clustering, but always get errors:
Might you have an idea of how to get to the bottom of this?
QGIS version: 2.18
Python version: 2.7.5
CRS of data: EPSG 4326
number of lines: 301
Best regards
Hi Anita
I keep getting the following error, regardless if I run the bundle edges script in Windows or Linux. Do you have any idea how to remedy it? I have some really great use cases for this bundling script, but I don't understand how to correct this issue.
2017-10-20T16:03:36 1 Cannot find variable: staticmethod
2017-10-20T16:03:37 2 Uncaught error while executing algorithm
Traceback (most recent call last):
File "C:/OSGEO4~1/apps/qgis/./python/plugins\processing\core\GeoAlgorithm.py", line 203, in execute
self.processAlgorithm(progress)
File "C:/OSGEO4~1/apps/qgis/./python/plugins\processing\script\ScriptAlgorithm.py", line 378, in processAlgorithm
exec((script), ns)
File "<string>", line 313, in <module>
File "<string>", line 164, in force_directed_eb
File "<string>", line 103, in compute_compatibilty_matrix
Exception: unknown
Hi Anita,
I had a quick look over the 3.0 port to see if there was any improvements I could suggest, since a lot of people will use this as a model for their ports. Here's a couple of small suggestions:
Line 160:
features = source.getFeatures(QgsFeatureRequest(), QgsProcessingFeatureSource.FlagSkipGeometryValidityChecks
The skip geometry validity check flag isn't required here - I think it's been copied from an algorithm which HAS to keep invalid geometries (e.g. a repair geometry alg). You probably want to remove the flag so that users are warned if their geometries are invalid.
Line 169:
for current, feat in enumerate(features):
Might be nice to check if the feedback is cancelled in this loop to allow responsive cancellation on big layers. (Could also potentially add a progress report here too)
Line 179:
print(labels)
I'd suggest changing this to feedback.pushDebugInfo(...). It'll be shown in the processing log (and in future release recorded to a semi permanent history log)
Line 200
I'd suggest a cancel check in this loop too (they are very cheap)
Otherwise a perfect 3.0 port!
Also keen to hear if you see memory leaks while running this alg? (Unrelated to this particular script, but a bigger issue in 3.0)
In the article Untangling Origin-Destination Flows in Geographic Information Systems, you mention that the QGIS edge bundling script is developed for Python 2.7. Is this still the case? What are some considerations related to Python 3 compatibility with these scripts?
Thanks for the helpful project!
I spent a few minutes making a quick and ugly update for usage outside of qgis using shapely. I am not sure it makes sense to put into this repo, but I wanted to share in case it could be a helpful starting point for a more rigorous effort.
Here is another project that implements Force-Directed Edge Bundling (very fast with Numba acceleration): https://github.com/verasativa/python.ForceBundle
Also worth mentioning, holoviews includes bundle_graph
, which is based on the datashader function hammer_bundle
.
import math
import numpy as np
from datetime import datetime
from shapely.geometry import Point, LineString
idc = 0.6666667 # For decreasing iterations
sdc = 0.5 # For decreasing the step-size
K = 0.1
eps = 0.000001
def forcecalcx(x, y, d) :
if abs(x) > eps and abs(y) > eps :
x *= 1.0 / d
else :
x = 0.0
return x
def forcecalcy(x, y, d) :
if abs(x) > eps and abs(y) > eps :
y *= 1.0 / d
else :
y = 0.0
return y
def norm(line):
a = np.array(line)
b = a[1] - a[0]
return b / np.linalg.norm(b)
# ------------------------------------ MISC ------------------------------------ #
class MiscUtils:
@staticmethod
def project_point_on_line(pt, line):
""" Projects point onto line, needed for compatibility computation """
a = np.array(line)
v0 = Point(a[0])
v1 = Point(a[1])
length = max(line.length, 10**(-6))
r = ((v0.y - pt.y) * (v0.y - v1.y) -
(v0.x - pt.x) * (v1.x - v0.x)) / (length**2)
return Point(v0.x + r * (v1.x - v0.x), v0.y + r * (v1.y - v0.y))
# ------------------------------------ EDGE-CLUSTER ------------------------------------ #
class EdgeCluster():
def __init__(self, edges, initial_step_size, iterations, cycles, compatibility):
self.S = initial_step_size # Weighting factor (needs to be cached, because will be decreased in every cycle)
self.I = iterations # Number of iterations per cycle (needs to be cached, because will be decreased in every cycle)
self.edges = edges # Edges to bundle in this cluster
self.edge_lengths = [] # Array to cache edge lenghts
self.E = len(edges) # Number of edges
self.EP = 2 # Current number of edge points
self.SP = 0 # Current number of subdivision points
self.compatibility = compatibility
self.cycles = cycles
self.compatibility_matrix = np.zeros(shape=(self.E,self.E)) # Compatibility matrix
self.direction_matrix = np.zeros(shape=(self.E,self.E)) # Encodes direction of edge pairs
self.N = (2**cycles ) + 1 # Maximum number of points per edge
self.epm_x = np.zeros(shape=(self.E,self.N)) # Bundles edges (x-values)
self.epm_y = np.zeros(shape=(self.E,self.N)) # Bundles edges (y-values)
def compute_compatibilty_matrix(self):
"""
Compatibility is stored in a matrix (rows = edges, columns = edges).
Every coordinate in the matrix tells whether the two edges (r,c)/(c,r)
are compatible, or not. The diagonal is always zero, and the other fields
are filled with either -1 (not compatible) or 1 (compatible).
The matrix is symmetric.
"""
edges_as_geom = list(self.edges)
edges_as_array = list(map(np.array, self.edges))
edges_as_vect = []
for e_idx, edge in enumerate(self.edges):
a = np.array(edge)
edges_as_vect.append(a[1] - a[0])
self.edge_lengths.append(edge.length)
progress = 0
for i in range(self.E-1):
for j in range(i+1, self.E):
# Parameters
lavg = (self.edge_lengths[i] + self.edge_lengths[j]) / 2.0
dot = norm(edges_as_geom[i]).dot(norm(edges_as_geom[j]))
# Angle compatibility
angle_comp = abs(dot)
# Scale compatibility
scale_comp = 2.0 / (lavg / min(self.edge_lengths[i],
self.edge_lengths[j]) + max(self.edge_lengths[i],
self.edge_lengths[j]) / lavg)
# Position compatibility
i0 = Point(edges_as_array[i][0])
i1 = Point(edges_as_array[i][1])
j0 = Point(edges_as_array[j][0])
j1 = Point(edges_as_array[j][1])
e1_mid = edges_as_geom[i].centroid
e2_mid = edges_as_geom[j].centroid
diff = LineString([Point(0,0), Point(e2_mid.x - e1_mid.x, e2_mid.y - e1_mid.y)])
pos_comp = lavg / (lavg + diff.length)
# Visibility compatibility
mid_E1 = edges_as_geom[i].centroid
mid_E2 = edges_as_geom[j].centroid
#dist = mid_E1.distance(mid_E2)
I0 = MiscUtils.project_point_on_line(j0, edges_as_geom[i])
I1 = MiscUtils.project_point_on_line(j1, edges_as_geom[i])
mid_I = LineString([I0, I1]).centroid
dist_I = I0.distance(I1)
if dist_I == 0.0:
visibility1 = 0.0
else:
visibility1 = max(0, 1 - ((2 * mid_E1.distance(mid_I)) / dist_I))
J0 = MiscUtils.project_point_on_line(i0, edges_as_geom[j])
J1 = MiscUtils.project_point_on_line(i1, edges_as_geom[j])
mid_J = LineString([J0, J1]).centroid
dist_J = J0.distance(J1)
if dist_J == 0.0:
visibility2 = 0.0
else:
visibility2 = max(0, 1 - ((2 * mid_E2.distance(mid_J)) / dist_J))
visibility_comp = min(visibility1, visibility2)
# Compatibility score
comp_score = angle_comp * scale_comp * pos_comp * visibility_comp
# Fill values into the matrix (1 = yes, -1 = no) and use matrix symmetry (i/j = j/i)
if comp_score >= self.compatibility:
self.compatibility_matrix[i, j] = 1
self.compatibility_matrix[j, i] = 1
else:
self.compatibility_matrix[i, j] = -1
self.compatibility_matrix[j, i] = -1
# Store direction
distStart1 = j0.distance(i0)
distStart2 = j1.distance(i0)
if distStart1 > distStart2:
self.direction_matrix[i, j] = -1
self.direction_matrix[j, i] = -1
else:
self.direction_matrix[i, j] = 1
self.direction_matrix[j, i] = 1
def force_directed_eb(self):
""" Force-directed edge bundling """
# Create compatibility matrix
self.compute_compatibilty_matrix()
print("Begin bundling.")
for e_idx, edge in enumerate(self.edges):
vertices = edge.boundary
self.epm_x[e_idx, 0] = vertices[0].x
self.epm_y[e_idx, 0] = vertices[0].y
self.epm_x[e_idx, self.N-1] = vertices[1].x
self.epm_y[e_idx, self.N-1] = vertices[1].y
# For each cycle
for c in range(self.cycles):
#print 'Cycle {0}'.format(c)
# New number of subdivision points
current_num = self.EP
currentindeces = []
for i in range(current_num):
idx = int((float(i) / float(current_num - 1)) * float(self.N - 1))
currentindeces.append(idx)
self.SP += 2 ** c
self.EP = self.SP + 2
edgeindeces = []
newindeces = []
for i in range(self.EP):
idx = int((float(i) / float(self.EP - 1)) * float(self.N - 1))
edgeindeces.append(idx)
if idx not in currentindeces:
newindeces.append(idx)
pointindeces = edgeindeces[1:self.EP-1]
# Calculate position of new points
for idx in newindeces:
i = int((float(idx) / float(self.N - 1)) * float(self.EP - 1))
left = i - 1
leftidx = int((float(left) / float(self.EP - 1)) * float(self.N - 1))
right = i + 1
rightidx = int((float(right) / float(self.EP - 1)) * float(self.N - 1))
self.epm_x[:, idx] = ( self.epm_x[:, leftidx] + self.epm_x[:, rightidx] ) / 2.0
self.epm_y[:, idx] = ( self.epm_y[:, leftidx] + self.epm_y[:, rightidx] ) / 2.0
# Needed for spring forces
KP0 = np.zeros(shape=(self.E,1))
KP0[:,0] = np.asarray(self.edge_lengths)
KP = K / (KP0 * (self.EP - 1))
# For all iterations (number decreased in every cycle)
for iteration in range(self.I):
# Spring forces
middlepoints_x = self.epm_x[:, pointindeces]
middlepoints_y = self.epm_y[:, pointindeces]
neighbours_left_x = self.epm_x[:, edgeindeces[0:self.EP-2]]
neighbours_left_y = self.epm_y[:, edgeindeces[0:self.EP-2]]
neighbours_right_x = self.epm_x[:, edgeindeces[2:self.EP]]
neighbours_right_y = self.epm_y[:, edgeindeces[2:self.EP]]
springforces_x = (neighbours_left_x - middlepoints_x + neighbours_right_x - middlepoints_x) * KP
springforces_y = (neighbours_left_y - middlepoints_y + neighbours_right_y - middlepoints_y) * KP
# Electrostatic forces
electrostaticforces_x = np.zeros(shape=(self.E, self.SP))
electrostaticforces_y = np.zeros(shape=(self.E, self.SP))
# Loop through all edges
for e_idx, edge in enumerate(self.edges):
# Loop through compatible edges
comp_list = np.where(self.compatibility_matrix[:,e_idx] > 0)
for other_idx in np.nditer(comp_list, ['zerosize_ok']):
otherindeces = pointindeces[:]
if self.direction_matrix[e_idx,other_idx] < 0:
otherindeces.reverse()
# Distance between points
subtr_x = self.epm_x[other_idx, otherindeces] - self.epm_x[e_idx, pointindeces]
subtr_y = self.epm_y[other_idx, otherindeces] - self.epm_y[e_idx, pointindeces]
distance = np.sqrt( np.add( np.multiply(subtr_x, subtr_x), np.multiply(subtr_y, subtr_y)))
flocal_x = map(forcecalcx, subtr_x, subtr_y, distance)
flocal_y = map(forcecalcy, subtr_x, subtr_y, distance)
# Sum of forces
electrostaticforces_x[e_idx, :] += np.array(list(flocal_x))
electrostaticforces_y[e_idx, :] += np.array(list(flocal_y))
# Compute total forces
force_x = (springforces_x + electrostaticforces_x) * self.S
force_y = (springforces_y + electrostaticforces_y) * self.S
# Compute new point positions
self.epm_x[:, pointindeces] += force_x
self.epm_y[:, pointindeces] += force_y
# Adjustments for next cycle
self.S = self.S * sdc # Decrease weighting factor
self.I = int(round(self.I * idc)) # Decrease iterations
new_edges = []
for e_idx in range(self.E):
# Create a new polyline out of the line array
line = map(lambda p,q: Point(p,q), self.epm_x[e_idx], self.epm_y[e_idx])
new_edges.append(LineString(line))
return new_edges
I tried to import the scripts in QGIS 3.6 but they are in Python 2 (see print statements) while QGIS 3.6 is using Python 3.x.
So I changed the print statement to print() functions and imported the scripts using the toolbox. But they don't show up in the toolbox (although they are automatically copied to the scripts folder).
I copied the plugin to the QGIS 3.6 plugin folder.
Now I absolutely don't know what to do next or where to find the scripts and plugins so that I can apply them to my origin -> destination data.
Help greatly appreciated :-).
Kepler.gl has both arc and line visualizations that allow line width to be set by a data attribute. How might edge bundling be used to create a CSV or JSON data set with origin/destination points and attribute containing weight or count, so it could be rendered in kepler.gl?
Hello! This package has aged well since I'm trying to set it up on Python version: 3.7.0 / QGIS version: 3.8.0-Zanzibar Zanzibar. Do you know if this could work?
So far I have tried opening/importing the .py scripts via the Processing Toolbox. This raises various syntax errors.
I'm also aware of this post , which makes me wonder if I'm doing something wrong:
Originally posted by @Bonnie-Buyuklieva in #5 (comment)
This is the bundle edges parameter page at QGIS 2.18. kmeans_sample is an edge data file with selected samples from running the cluster_line_kmeans tool. The unit of the projection (conic) is meter, so I set the step size to be very large.
This is the error I received when hitting the "Run"
The error message seems to mean that the algorithm wants the parameter values to be integers rather than floats. But I had made sure that initial_step_size, compatibility, cycles, and iterations are all integers. The tool window forces my number to be in the format of floats โโ even if I typed in "1", the tool will "floated" it to "1.000000".
I compared carefully the numbers I have with the numbers you put in the blog post. I even tried the exact same numbers but still received the same error message. I also checked the python version in the QGIS console: it can run Python2 syntax perfectly (which is what your script is written in). I wonder if you have any clues that what may cause the issue.
Thank you very much!
Hi Anita,
First of all, congrats on all your super interesting work in the field of OS GIS software, really impressive!
I have been trying out the edge-bundeling for QGIS 3.0 and already have some very interesting results. I saw from your blog and in the repo that for QGIS2 you also have two additional tools, the clustering pre-processing and the summarize. Are you planning or anybody else on porting those as well to QGIS3.0?
I also tried to use the standard k-means clustering in QGIS3.0 prior to the edge-bundeling which seemed to work as well. What is the difference between the standard and your custom k-means clustering?
Best,
Lucas
It would be nice to have the option to ignore the clusters when running the summarize tool. This would be beneficial for situations like that shown below, where two bundles intersect at a shallow angle.
Ignoring the cluster in this case and just using the geometrical similarity of the line segments for summarizing the weights would allow the area around the intersection to show a larger summarized flow, which may be desired behavior in some use cases.
Note: This is mainly for discussion about an idea that was suggested to me by our UX designer.
QGIS edge bundling currently produces a static image. While informative of overall movement patterns, it may obscure movement trends over time (e.g. morning/afternoon, weekday/weekend, etc).
The idea was suggested to create a movie or animation showing movement trends over time. E.g. the movie could cycle through renderings of movement data binned into hourly, daily, weekly, etc. periods. It may also be desirable to have some transition, such as an alpha blend, to give the appearance of continuity (such as the difference between a bar and line chart).
What are some possible approaches to create a time-series animation of bundled origin-destination data? What tools exist in the QGIS ecosystem, such as TimeManager, and how might they be used/improved in conjunction with this edge bundling plugin to produce the desired animation?
I have read through the blog post describing this package, but have been scratching my head for a couple of hours trying to get things to work properly. Is there a step-by-step tutorial/recipe that shows how to use the edge bundling plugin?
How can I install this, so it is accessible in my processing toolbox? I am using Ubuntu Linux, but installation instructions for other platforms might also be helpful.
I used a layer which contained 549 lines, none of which have length 0. Also every one of them is a linestring with two points,.
When running with default settings and no clustering field i get an error.
Traceback (most recent call last):
File "C:/Users/Patu/AppData/Roaming/QGIS/QGIS3\profiles\default/python/plugins\processing_edgebundling\edgebundling.py", line 202, in processAlgorithm
cl.force_directed_eb(feedback)
File "C:/Users/Patu/AppData/Roaming/QGIS/QGIS3\profiles\default/python/plugins\processing_edgebundling\edgebundlingUtils.py", line 190, in force_directed_eb
self.epm_x[e_idx, 0] = vertices[0].x()
IndexError: list index out of range
How should i proceed?
Dear Anita,
When i tried edge bundling process at my own dataset, it failed and threw an issue as below:
UnboundLocalError: local variable 'visibility1' referenced before assignment
Is there any solution for this problem??
Enclosed file is my dataset
I'm having difficulty installing the plugins from the ZIP file from the 'Install from ZIP' function. Below is the error message I'm receiving. I'm relatively new to QGIS and especially new to Python, so I'm probably oblivious to the core issue, but is this something I can fix on my own?
Thanks!
...
An error occurred during execution of following code:
pyplugin_installer.instance().installFromZipFile(r'C:\Users\User\Downloads\qgis-edge-bundling-master.zip')
Traceback (most recent call last):
File "C:/OSGEO4~1/apps/qgis/./python\qgis\utils.py", line 334, in _startPlugin
plugins[packageName] = package.classFactory(iface)
AttributeError: module 'qgis-edge-bundling-master' has no attribute 'classFactory'
During handling of the above exception, another exception occurred:
Traceback (most recent call last):
File "", line 1, in
File "C:/OSGEO41/apps/qgis/./python\pyplugin_installer\installer.py", line 624, in installFromZipFile1/apps/qgis/./python\qgis\utils.py", line 354, in startPlugin
if startPlugin(pluginName):
File "C:/OSGEO4
if not _startPlugin(packageName):
File "C:/OSGEO41/apps/qgis/./python\qgis\utils.py", line 336, in _startPlugin1/apps/qgis/./python\qgis\utils.py", line 448, in _unloadPluginModules
_unloadPluginModules(packageName)
File "C:/OSGEO4
mods = _plugin_modules[packageName]
KeyError: 'qgis-edge-bundling-master'
Python version:
3.7.0 (v3.7.0:1bf9cc5093, Jun 27 2018, 04:59:51) [MSC v.1914 64 bit (AMD64)]
QGIS version:
3.8.0-Zanzibar 'Zanzibar', 11aff65f10
Python path:
['C:/OSGEO41/apps/qgis/./python', 'C:/Users/User/AppData/Roaming/QGIS/QGIS3\profiles\default/python', 'C:/Users/User/AppData/Roaming/QGIS/QGIS3\profiles\default/python/plugins', 'C:/OSGEO41/apps/qgis/./python/plugins', 'C:\OSGeo4W64\bin\python37.zip', 'C:\OSGEO41\apps\Python37\DLLs', 'C:\OSGEO41\apps\Python37\lib', 'C:\OSGeo4W64\bin', 'C:\OSGEO41\apps\Python37', 'C:\OSGEO41\apps\Python37\lib\site-packages', 'C:\OSGEO41\apps\Python37\lib\site-packages\win32', 'C:\OSGEO41\apps\Python37\lib\site-packages\win32\lib', 'C:\OSGEO4~1\apps\Python37\lib\site-packages\Pythonwin', 'C:/Users/User/AppData/Roaming/QGIS/QGIS3\profiles\default/python', 'C:\Users\User\AppData\Roaming\QGIS\QGIS3\profiles\default\python\plugins\mmqgis/forms', 'C:/Users/User/Desktop']
...
Currently, the script documentation only contains a brief description for each module. This leaves the user to guess as to how to use each script option. E.g. what is a good value for default step size?
Add documentation for each script parameter. Consider also adding useful notes about common use patterns (e.g. default step size of 100 is going to cause problems for geographic coordinates).
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.