Finding and Connecting Multiple Canvas Items in Python

Question

Background: I have a code which generates the cartesian coordinates of a network of regular shapes (in this case triangles), and then plots the vertices of the shapes on a Tkinter Canvas as small circles. The process is automated and requires only height and width of the network to obtain a canvas output. Each vertex has the tags 'Vertex' and the vertex's number.
Problem: I want to automatically connect the vertices of the shapes together (i.e dot to dot), I have looked into using find_closest and find_overlapping methods to do this, but as the network is composed of vertices at angles to one another, I often find find_overlapping to be unreliable (due to relying on a rectangular envelope), and find_closest appears limited to finding only one connection. As the vertices aren't necessarily connected in order, it is not possible to create a loop to simply connect vertex 1 --> vertex 2 etc.
Question: Is there a way to efficiently get all of a vertex's neighbouring vertices and then 'connect the dots' without relying on individually creating lines between points using a manual method such as self.c.create_line(vertex_coord[1], vertex_coord[0], fill='black') for each connection? And would it be possible to share a small example of such a code?

Thank you in advance for any help!

Below is an abbreviated version of the canvas components of my code.

Prototype Method:

from data_generator import * 
run_coordinate_gen=data_generator.network_coordinates()
run_coordinate_gen.generator_go()

class Network_Canvas:
  def __init__(self, canvas):
        self.canvas=canvas
        canvas.focus_set()
        self.canvas.create_oval(Vertex_Position[0],  dimensions[0],   fill='black', tags=('Vertex1', Network_Tag, Vertex_Tag))
        self.canvas.create_oval(Vertex_Position[5],  dimensions[5],   fill='black', tags=('Vertex2', Network_Tag, Vertex_Tag))
        try:
            self.canvas.create_line(Line_Position[5] ,Line_Position[0] , fill='black' tags=(Network_Tag,'Line1', Line_Tag )) #Connection Between 1 and 6 (6_1), Line 1
        except:
            pass

#Note: Line_Position, Dimensions and Vertex_Position are all lists composed of (x,y) cartesian coordinates in this case.

This is of course then replicated for each line and vertex throughout the network, but was only used for 90 vertices. The new version requires orders of magnitude more vertices and I am doing this with:
New Method:

#Import updated coordinate generator and run it as before
class Network_Canvas:
    def __init__(self, canvas):
        self.canvas=canvas
        canvas.focus_set()
        for V in range(len(vertex_coord_xy)):                                                   
            self.canvas.create_text(vertex_coord_xy[V]+Text_Distance, text=V+1, fill='black', tags=(V, 'Text'), font=('Helvetica', '9'))
            self.canvas.create_oval(vertex_coord_xy[V],vertex_coord_xy[V]+Diameter, fill='black', outline='black', tags=(V, 'Vertex'))      
    #loop to fit connections here (?) 

Answer 1

I think any kind of nearest-neighbor search is going to be waay more time-intensive than just keeping track of the vertices, and there's no "automatic" connect-the-dots method that I can think of (plus, I don't see why such a method should be any faster than drawing them with create_line). Also, how will a nearest-neighbor search algorithm distinguish between the vertices of two separate, nearby (or overlapping) shapes if you aren't keeping track? Anyhow, in my opinion you've already got the right method; there are probably ways to optimize it.

I think that since your shapes are numerous, and there are complicated things you need to do with them, I would make a class for them, like the one I implemented below. It includes the "click to see neighboring vertices" functionality. All of the following code ran without errors. Image of the output shown below.

import Tkinter as TK
import tkMessageBox

# [Credit goes to @NadiaAlramli](http://stackoverflow.com/a/1625023/1460057) for the grouping code
def group(seq, groupSize):
    return zip(*(iter(seq),) * groupSize)

Network_Tag, Vertex_Tag, Line_Tag = "network", "vertex", "line"

class Shape:
    def __init__(self, canvas, vertexCoords, vertexDiam):
        self.vertexIDs = []
        self.perimeterID = None
        self.vertexCoords = vertexCoords
        self.vertexRadius = vertexDiam/2
        self.canvas = canvas

    def deleteVertices(self):
        for ID in self.vertexIDs:
            self.canvas.delete(ID)
        self.vertexIDs = []

    def bindClickToVertices(self):
        coordsGrouped = group(self.vertexCoords, 2)
        num = len(coordsGrouped)
        for k in range(len(self.vertexIDs)):
            others = [coordsGrouped[(k-1)%num], coordsGrouped[(k+1)%num]]
            self.canvas.tag_bind(self.vertexIDs[k], '<Button-1>',
                    lambda *args:tkMessageBox.showinfo("Vertex Click", "Neighboring vertices: "+str(others)))

    def drawVertices(self):
        for x, y in group(self.vertexCoords, 2):
            self.vertexIDs.append(self.canvas.create_oval(x-self.vertexRadius, y-self.vertexRadius, x+self.vertexRadius, y+self.vertexRadius, fill='black', tags=(Network_Tag, Vertex_Tag)))
        self.bindClickToVertices()

    def updateVertices(self):
        self.deleteVertices()
        self.drawVertices()

    def deletePerimeter(self):
        if self.perimeterID is not None:
            self.canvas.delete(self.perimeterID)
        self.perimeterID = None

    def drawPerimeter(self):
        print "creating line:", (self.vertexCoords + self.vertexCoords[0:2])
        self.perimeterID = self.canvas.create_line(*(self.vertexCoords + self.vertexCoords[0:2]), fill='black', tags=(Network_Tag, Line_Tag))

    def updatePerimeter(self):
        self.deletePerimeter()
        self.drawPerimeter()

    def deleteShape(self):
        self.deleteVertices()
        self.deletePerimeter()

    def updateShape(self):
        self.updateVertices()
        self.updatePerimeter()

It can be used very simply, like this:

root = TK.Tk()

frame = TK.Frame(root)
canvas = TK.Canvas(frame, width=1000, height=1000)
frame.grid()
canvas.grid()

# create a bunch of isoceles triangles in different places:
shapes = []
for dx, dy in zip(range(0,1000, 30), range(0,1000, 30)):
    shapes.append(Shape(canvas, [0+dx, 0+dy, 10+dx, 10+dy, 20+dx, 0+dy], 5))

# draw (or redraw) the shapes:
for shape in shapes:
    shape.updateShape()

# move one of the shapes and change it to a square
shapes[10].vertexCoords = [50, 10, 60, 10, 60, 20, 50, 20]
shapes[10].updateShape()

# delete all the odd-numbered shapes, just for fun:
for k in range(len(shapes)):
    if k%2 == 1:
        shape.deleteShape()

root.mainloop()

Output: