Search code examples
pythonarraylistcoordinate-systems

Sorting a list of points to match an other list to create straight lines without any intersection

I write code in Python. I have two lists containing points on a plane: points1 and points2.

Given: len(points1) == len(points2) Another fact is that all the points in the list points1 are on one side and all the points in the list points2 are on the other side, which means that:

for p1 of points1:
    for p2 of points2:
        p1.X < p2.X # always true or always false

Another fact is that all the points in points2 are below each other so that:

for i of range(len(points2)-1):
    points2[i].X == points2[i+1].X # always true

Another fact is that the steps between the points in points2 are equal. I mean:

for i of range(len(points2)-2):
    points2[i+1].Y - points2[i].Y == points2[i+2].Y - points2[i+1].Y # always true

In the picture is a visual example, that the lists is: points1=[D,E,F], points2=[A,B,C] pic

I need to build a function that will rearrange the order of the points so that when I create straight lines from the lists as follows:

line0 = Line(points1[0], points2[0])
line1 = Line(points1[1], points2[1])
line2 = Line(points1[2], points2[2])

and so on, there will be no line that intersects another line. The Line function is an existing function that accepts two points and returns the straight line connecting them.

Do not change the points in the list, but only the order of the list.

I already have a function that accepts 2 straight lines and returns True if they intersect and False if they don't, called: isIntersect(line1, line2), and i can use it.

Solution

  • Thank God, here is a solution that works:

    def sortPoints(points1, points2):
    limit = 1000000
    rounds = 0
    i = 0
    while(i < len(points1) - 1):
        if rounds > limit:
            alert("Could not sort the points to be without intersections.")
            break

        line1 = Line.CreateBound(points1[i], points2[i])
        line2 = Line.CreateBound(points1[i + 1], points2[i + 1])
        if isIntersect(line1, line2):
            points1[i], points1[i + 1] = points1[i + 1], points1[i]
            i = 0
            rounds += 1
            continue

        i += 1
        rounds += 1

    for j in range(len(points1)):
            for k in range(j):
                if j != k:
                    line1 = Line.CreateBound(points1[j], points2[j])
                    line2 = Line.CreateBound(points1[k], points2[k])
                    if isIntersect(line1, line2):
                        points1[i], points1[j] = points1[j], points1[i]