Searching and matching objects through tuples, list of lists

Question

after working for hours, spending too much effort on this problem, I have almost given up! Here it is:

Given:
a list containing point objects where I have point object and line object defined as:

class Point():
    def  __init__(self, x, y):
        self._x = x
        self._y = y
    def __eq__(self, other):
        return self.__dict__ == other.__dict__

and

class Line(object):
    def __init__(self,p1, p2,name):
        self.p1=p1
        self.p2=p2
        self.name=name

Problem:
I am trying to create a list of points, in the same order in which the lines are connected; upto now I can detect connections between lines e.g.

p1=Point(2.1,2.0)   
p2=Point(1.1,5.0)   
p3=Point(4.1,3.0)   
p4=Point(3.1,2.0)

and

line1=Line(p1,p2,"line.1")
line2=Line(p3,p2,"line.2")   
line3=Line(p3,p4,"line.3")   
line4=Line(p4,p1,"line.4")

- Lines and points

Normally, the points are not listed in order, and similarly the lines are also not ordered.

Upto now I can detect the spline connections in the following format (list of lists containing tuples:

connectionList=    [
[(line1, line1.p1), (line4, line4.p2)]
[(line2, line2.p1), (line3, line3.p1)]
[(line3, line3.p2), (line4, line4.p1)]
...
]

I am trying to achieve the result in format [p1, p3,p4, ..]

EDIT:

The solution to above problem (after using the answer from @marqs) embedded in an example, is below:

class Point():
    def __init__(self, x, y):
        self._x = x
        self._y = y
    def __eq__(self, other):
        return self.__dict__ == other.__dict__

class Line(object):
    def __init__(self,p1, p2,name):
        self.p1=p1
        self.p2=p2
        self.name=name

p1=Point(1,1)
p2=Point(5,2)
p3=Point(1,5)
p4=Point(2,2)
p5=Point(5,5)
p6=Point(6,1)
p7=Point(6,5)
p8=Point(2,5)


s1=Line(p1,p3,"Line1")
s2=Line(p7,p6,"Line2")
s3=Line(p1,p6,"Line3")
s4=Line(p2,p5,"Line4")
s5=Line(p4,p8,"Line5")
s6=Line(p4,p2,"Line6")
s7=Line(p5,p7,"Line7")
s8=Line(p3,p8,"Line8")


def connectivity(s,sl):
    s_L=[]
    s_L=[spl1 for spl1 in sl]
    s_L.remove(s)
    connection=[]
    for sp in s_L:
        if s.p1==sp.p1:
            connection.append([(s, s.p1), (sp, sp.p1)])
            continue
        elif s.p1==sp.p2:
            connection.append([(s, s.p1), (sp, sp.p2)])
            continue
        elif s.p2==sp.p1:
            connection.append([(s, s.p2), (sp, sp.p1)])
            continue
        elif s.p2==sp.p2:
            connection.append([(s, s.p2), (sp, sp.p2)])
            continue
        else:
            pass
    return connection


def getPoints(connectionList):
    firstConnection = connectionList[0]
    points = [firstConnection[1][1]]
    lastLine = firstConnection[1][0]

    connectionList.remove(firstConnection)

    while len(connectionList):
        for connection in list(connectionList):
            (line1, p1), (line2, p2) = connection
            if lastLine == line1 or lastLine == line2:
                points.append(p1)
                lastLine = line1 if lastLine == line2 else line2
                connectionList.remove(connection)
                break
    return points


con=[]
complete=[]
slist=[s1,s2,s3,s4,s5,s6,s7,s8]
for splineX in slist:
    con=connectivity(splineX, slist)
    prev=[temp1 for temp01 in complete for temp1 in temp01]
    if not (con[0][0] in prev or con[0][1] in prev):
        complete.append(con[0])
    if len(con)>1:
        if not (con[1][0] in prev or con[1][1] in prev):
            complete.append(con[1])

connectionList=[xyz for xyz in complete]
pointList=getPoints(connectionList)
pointcord=[]
for pnt in pointList:
    pointcord.append((pnt._x, pnt._y))

print "Ordered list of points:\n" , pointcord

The result is:

Ordered list of points: [(1, 1), (6, 1), (6, 5), (5, 5), (5, 2), (2, 2), (2, 5), (1, 5)]

What exactly is your question? How to turn the `connectionList` you presented to the format of `[p1, p3, p4, ...]`, or how to get to `connectionList` in the first place? If the former, the length introduction is not needed — Korem, Jun 16 '14 at 16:53
I already have programmed lines connectionList, I can detect which lines are connected to a certain line. What I am looking for, is a list of points which is ordered according to this connectionList of lines. Kindly see the figure in the post for elaboration. — Mubeen Shahid, Jun 16 '14 at 17:04
I'm not sure StackOverflow is the right forum to post this question. I think you might find codereview, programmers, or codegolf more useful for this. — JBCP, Jun 16 '14 at 18:00
@JBCP No, Code Review is for reviewing *working* code, and Code Golf is for programming challenges or questions about improving golfing skills, not for general programming questions. — ProgramFOX, Oct 30 '14 at 13:30
@ProgramFOX - agreed, but that wasn't clear to me when I reviewed the original question — JBCP, Oct 30 '14 at 14:25

score 1 · Answer 1 · edited May 23 '17 at 12:05

I do not speak python, but you can do as follows:

Find the center of your polygon
Sort the vertices based on the angle from the center point. You can get the angle from the center point like this: atan2(point.y - Center.y, point.x - Center.x)
If two points have the same angle, the point closest to the center comes first. For performance, you can calculate it without square root like this: abs((point.y - Center.y)*(point.y - Center.y)+(point.x - Center.x)*(point.x - Center.x))

score 1 · Accepted Answer · answered Jun 16 '14 at 21:56

I have given your problem a try. The function belows try to find the matching lines and saves the points. It assumes that connectionList is correct. If it is not, the function will probably go into an infinite loop.

def getPoints(connectionList):
    firstConnection = connectionList[0]
    points = [firstConnection[1][1]]
    lastLine = firstConnection[1][0]

    connectionList.remove(firstConnection)

    while len(connectionList):
        for connection in list(connectionList):
            (line1, p1), (line2, p2) = connection
            if lastLine == line1 or lastLine == line2:
                points.append(p1)
                lastLine = line1 if lastLine == line2 else line2
                connectionList.remove(connection)
                break
    return points

Tons of thanks!!! Truly genius, I must say. I spent many hours but removing a `connection` from the ` connectionList` always destroyed the loops. This is working perfectly fine, I have updated the question, with the results after using this function, as well as a couple of examples. — Mubeen Shahid, Jun 17 '14 at 09:41

Searching and matching objects through tuples, list of lists

2 Answers2