Creating all possible line segments between all points using QGIS

Question

I want to connect all points in a point feature with every possible line segment using QGIS.

For example, how a pentagon has five points with ten line segments connecting them all to form a pentagram inside.

Alternatively phrased: How do I make spokes when all the points are hubs?

I don't care about the order, I just want every connection between two points as one line each. Is there a tool or script that can do this in QGIS?

This topic (How to generate line segments between all points) is the closest to what I want but the plugins are no longer supported.

Answer 1

You can achieve your goal using the Field Calculator.

Using the Geometry Generator, with Linestring geometry type, use this expression:

 collect_geometries( 
   array_foreach(
     aggregate('point_layer','array_agg',$geometry),
       make_line($geometry,@element)
   )
 )

It will create an array of lines that connect any point with all the other points on the same layer.

You can create a new layer using the same expression in the Processing tool Vector Geometry > Geometry by expression.

Here is a screenshot that shows the result using the expression in the Geometry Generator:

Answer 2

You can make use of the virtual layers.

Go to Layer/ Add layer/ add-edit virtual layer and enter the following query. Feel free to add as many field as you want. The trick is to do a cross-join on the same table, generating every combination between the two layers.

select a.id, b.id, makeline(a.geometry, b.geometry) as geometry
from myLayer a, myLayer b
where a.id <> b.id

Answer 3

Let's assume there is a point layer called 'Layer' with its corresponding attribute table accordingly, see image below. Besides, a new attribute might be created that will group points together, e.g. "id" on the icon below.

Step 1. Duplicate your initial point layer with 'RMC > Duplicate Layer...'.

Step 2. Make use of "Join by lines (hub lines)" ('Spoke ID field' is "id"). Afterward, the application of "Fix geometries" and "Remove null geometries" is essential.

Step 3. If lines should be unique (only one connection between two points), then proceed additionally with "Delete duplicate geometries".

---

To check whether the result is correct, use the initial number of points, e.g. n.

• when lines are doubled
• when lines are unique

Answer 4

I made a custom processing tool for this purpose. You can use the same layer as source and target or use two different layers. A unique attribute is required to run it.

The script returns lines connecting all points including the unique attributes of both layers, or the unique attribute of the only layer. Also, the line length is added as an attribute.

The advantage of this method is, that it can easily be used within graphical modeler.

from PyQt5.QtCore import QCoreApplication, QVariant
from qgis.core import (QgsField, QgsFeature, QgsProcessing, QgsExpression, QgsGeometry, QgsPoint, QgsFields, QgsWkbTypes,
                       QgsFeatureSink, QgsFeatureRequest, QgsProcessingAlgorithm,
                       QgsProcessingParameterFeatureSink, QgsProcessingParameterField, QgsProcessingParameterFeatureSource, QgsProcessingParameterEnum)
class ConnectAllPointsByLines(QgsProcessingAlgorithm):
    POSSIBILITY_LYR = 'POSSIBILITY_LYR'
    POSSIBILITY_IDFIELD = 'POSSIBILITY_IDFIELD'
    STOP_LYR = 'STOP_LYR'
    STOP_IDFIELD = 'STOP_IDFIELD'
    OUTPUT = 'OUTPUT'
def initAlgorithm(self, config=None):

    self.addParameter(
        QgsProcessingParameterFeatureSource(
            self.STOP_LYR, self.tr('Source Points'), [QgsProcessing.TypeVectorPoint]))
    self.addParameter(
        QgsProcessingParameterField(
            self.STOP_IDFIELD, self.tr('Unique ID Field of Source Layer (Any Datatype)'),'ANY','STOP_LYR'))        
    self.addParameter(
        QgsProcessingParameterFeatureSource(
            self.POSSIBILITY_LYR, self.tr('Target Points'), [QgsProcessing.TypeVectorPoint]))
    self.addParameter(
        QgsProcessingParameterField(
            self.POSSIBILITY_IDFIELD, self.tr('Unique Target ID Field (Any Datatype, should have a different name than Source ID field)'),'ANY','POSSIBILITY_LYR'))
    self.addParameter(
        QgsProcessingParameterFeatureSink(
            self.OUTPUT, self.tr('Line Connections'), QgsProcessing.TypeVectorLine))

def processAlgorithm(self, parameters, context, feedback):
    # Get Parameters
    possibility_layer = self.parameterAsSource(parameters, self.POSSIBILITY_LYR, context)
    possibility_idfield = self.parameterAsFields(parameters, self.POSSIBILITY_IDFIELD, context)
    stop_layer = self.parameterAsSource(parameters, self.STOP_LYR, context)
    stop_idfield = self.parameterAsFields(parameters, self.STOP_IDFIELD, context)

    fields = QgsFields()
    fields.append(QgsField(stop_idfield[0]))        
    fields.append(QgsField(possibility_idfield[0]))
    fields.append(QgsField("line_length", QVariant.Double, len=20, prec=5))

    (sink, dest_id) = self.parameterAsSink(parameters, self.OUTPUT, context,
                                           fields, QgsWkbTypes.LineString,
                                           possibility_layer.sourceCrs())

    # iterate over stop features
    for stop_feat in stop_layer.getFeatures():
        point1 = QgsPoint(stop_feat.geometry().asPoint())
        for source_feat in possibility_layer.getFeatures():
            point2 = QgsPoint(source_feat.geometry().asPoint())
            new_feat = QgsFeature(fields)
            new_feat.setGeometry(QgsGeometry.fromPolyline([point1, point2])) 
            new_feat[stop_idfield[0]] = stop_feat[stop_idfield[0]]                
            new_feat[possibility_idfield[0]] = source_feat[possibility_idfield[0]]
            new_feat["line_length"] = new_feat.geometry().length()                
            sink.addFeature(new_feat, QgsFeatureSink.FastInsert)

    return {self.OUTPUT: dest_id}


def tr(self, string):
    return QCoreApplication.translate('Processing', string)

def createInstance(self):
    return ConnectAllPointsByLines()

def name(self):
    return 'ConnectAllPointsByLines'

def displayName(self):
    return self.tr('Connect All Points By Lines')

def group(self):
    return self.tr('FROM GISSE')

def groupId(self):
    return 'from_gisse'

def shortHelpString(self):
    return self.tr('This Algorithm connects all points of the Source layer with all points of the Target layer with lines and adds the lines length')

Answer 5

Another PyQGIS solution. It applies the permutations() method from the itertools Python module.

Let's assume there is one point layer called 'start', with its attribute table, see the image below.

Proceed with Plugins > Python Console > Show Editor and paste the script below:

# imports
from qgis.core import QgsProject, QgsVectorLayer, QgsField, QgsGeometry, QgsFeature
from PyQt5.QtCore import QVariant
from itertools import permutations
accessing a layer with points by its name
points = QgsProject.instance().mapLayersByName("YOUR_LAYER_NAME")[0]
getting index of the reference field
indx = points.fields().indexOf("id")
creating a virtual line layer output
line_layer = QgsVectorLayer(f"LineString?crs={points.crs().authid()}&index=yes", "connections", "memory")
adding new fields "from" and "to"
provider = line_layer.dataProvider()
provider.addAttributes([
    QgsField("from", QVariant.String),
    QgsField("to", QVariant.String)
])
line_layer.updateFields()
looping over each feature from the layer and making all possible connections between them
for feat1, feat2 in permutations(points.getFeatures()):
    connect = [feat1.geometry().asPoint(), feat2.geometry().asPoint()] # connection between two points
    line = QgsGeometry.fromPolylineXY(connect) # creating a line string from connection
feat = QgsFeature() # creating a new feature
feat.setGeometry(line) # setting new geometry as a line string
feat.setAttributes([feat1[indx], feat2[indx]]) # setting new attributes as "from" and "to"
provider.addFeature(feat) # adding feature to the output layer


adding the line layer output to the map canvas
QgsProject.instance().addMapLayer(line_layer)

Change the "YOUR_LAYER_NAME" value, press Run script and get the output that will look like:

If the output line layer shall contain only unique geometries, use the combinations() method instead, see @BERA's answer for more details, otherwise adjust the above code like this:

for feat1, feat2 in combinations(points.getFeatures(), 2):
    ...

---

References:

• PyQGIS 101: Creating & editing a new vector layer

Answer 6

You can use python with itertools combinations:

from itertools import combinations as c
lyr = QgsProject.instance().mapLayersByName('Vertices')[0]
points = [f.geometry() for f in lyr.getFeatures()] #List all point geometries in the input layer
vl = QgsVectorLayer("LineString?crs={0}%index=yes".format(lyr.crs().authid()), "myLayer", "memory")
p = vl.dataProvider()
featureList = []
for x,y in c(points, 2): #For all pairwise combinations of points in the layer
    f = QgsFeature() #Create a new feature
    g = QgsLineString([x.asPoint(), y.asPoint()]) #Create a line between them
    f.setGeometry(g)
    featureList.append(f)
p.addFeatures(featureList)
print('Done')
QgsProject.instance().addMapLayer(vl)