Connect points of list 1 with points of list 2 with line without clashing each other

Developers
, , ,
1

I want to connect points from sublist of input IN[0] to points of sublist of input IN[1] in the way the combinations of lines generated do not clash between each other, the inputs are a list of sublists of dynamo points. I do not know how to make it work, I ran this script in python node but it eats all memory RAM 50GB and it does not finish because:

Warning: IronPythonEvaluator.EvaluateIronPythonScript operation failed. 
Traceback (most recent call last):
  File "<string>", line 43, in <module>
  File "<string>", line 33, in lines_from_points
MemoryError: Array dimensions exceeded supported range.

The code used:

import clr
clr.AddReference('ProtoGeometry')
from Autodesk.DesignScript.Geometry import Line, Point

import itertools

def lines_from_points(start_points_lists, end_points_lists):
    def is_intersecting(line1, line2):
        x1, y1, z1 = line1.StartPoint.X, line1.StartPoint.Y, line1.StartPoint.Z
        x2, y2, z2 = line1.EndPoint.X, line1.EndPoint.Y, line1.EndPoint.Z
        x3, y3, z3 = line2.StartPoint.X, line2.StartPoint.Y, line2.StartPoint.Z
        x4, y4, z4 = line2.EndPoint.X, line2.EndPoint.Y, line2.EndPoint.Z

        denom = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4)
        if denom == 0:
            return False

        t = ((x1 - x3) * (y3 - y4) - (y1 - y3) * (x3 - x4)) / denom
        u = -((x1 - x2) * (y1 - y3) - (y1 - y2) * (x1 - x3)) / denom

        if 0 < t < 1 and 0 < u < 1:
            return True
        return False

    def is_valid_combination(lines):
        for line1, line2 in itertools.combinations(lines, 2):
            if is_intersecting(line1, line2):
                return False
        return True

    valid_combinations = []
    for start_points, end_points in zip(start_points_lists, end_points_lists):
        all_combinations = list(itertools.permutations(end_points, len(start_points)))
        for end_points_combination in all_combinations:
            lines = [Line.ByStartPointEndPoint(s, e) for s, e in zip(start_points, end_points_combination)]
            if is_valid_combination(lines):
                valid_combinations.append(lines)

    return valid_combinations

start_points_lists = IN[0]
end_points_lists = IN[1]
OUT = lines_from_points(start_points_lists, end_points_lists)

image
image1115×514 56.3 KB

2

Test it with a small set of inputs, if it finishes but doesnt spin out then youre probably hitting the limit of how many elements python handles in an array for your intended size and might need to rethink your process and/or consider looking into more PC friendly language like C#.

3

Yikes!

This is an impossible problem as you can easily get into situations where there isn’t a solution. The problem gets even worse when the points aren’t defined cleanly or sorted. Grouping the closest pairing of points is likely a good start, but you can still run into an infinite calculations situation (ie: two points in each list which are colinear).

What’s the end goal, and how many points do you have?

4

sublist 1: 4 points
sublist 2: 34 points
sublist 3: 28 points

I already defined where are the end points in an input IN[1], the starts points are in IN[0], any line created from those points cannot be reused again in other line and also lines cannot clash/intersect between each other between same sublist of points, there are same number of points in both inputs and same sublists, so I am trying to find the match between points because I do not have a clue what to do to avoid clashing lines between the points

5

I’m lost by the 3 sublists - are you drawing lines from sublist 1 to sublist 2? Sublist 2 to sublist 3? Or is there list 1 with sublists 1.1,1.2 and 1.3, and list 2 with sublists 2.1, 2.2, and 2.3?

7

working with points of same sublist only, both inputs have same number of points so I am expecting a match like couples

8

So for sublist 1 you have 4 points and want to ‘connect them’ by drawing lines between any two to ensure there aren’t any crossing lines?

1 Like
9

yes, there are 4 points and I want 4 lines starting by those 4 points but the points cannot be reused in the other lines, and then the end points can be any of the other 4 points in the input IN[1] but with the condition those are not used twice and lines created do not clash with the rest generated, sounds simple but I do not get it yet after many trials, mind feels like taking drugs, probably this is a known algorithm and I am reinventing the wheel or something…

this is how it looks visually resolved, but I do not get it done for more complex situations, I represented also the lines where are contained those points of IN[1], the blue pen marks are the input IN[0] points, the blue dot is a centroid not related to inputs but I have been trying to see if I can use it for something before.

image
image721×757 11.4 KB

this is the code more far that I got working but it does not generate one line by point in input because lines are clashing for the rest of the options, in my case 50% of lines are created without clash when I prioritised create lines by proximity of input points, but there is no solution yet:

import clr
clr.AddReference('ProtoGeometry')
from Autodesk.DesignScript.Geometry import Line, Point

def is_intersecting(line1, line2):
    x1, y1, z1 = line1.StartPoint.X, line1.StartPoint.Y, line1.StartPoint.Z
    x2, y2, z2 = line1.EndPoint.X, line1.EndPoint.Y, line1.EndPoint.Z
    x3, y3, z3 = line2.StartPoint.X, line2.StartPoint.Y, line2.StartPoint.Z
    x4, y4, z4 = line2.EndPoint.X, line2.EndPoint.Y, line2.EndPoint.Z

    denom = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4)
    if denom == 0:
        return False

    t = ((x1 - x3) * (y3 - y4) - (y1 - y3) * (x3 - x4)) / denom
    u = -((x1 - x2) * (y1 - y3) - (y1 - y2) * (x1 - x3)) / denom

    if 0 < t < 1 and 0 < u < 1:
        return True
    return False

def sort_end_points_by_proximity(start_point, end_points):
    end_points_distances = [(end_point, start_point.DistanceTo(end_point)) for end_point in end_points]
    end_points_distances.sort(key=lambda x: x[1])
    return [x[0] for x in end_points_distances]

def sort_points_by_proximity(points1, points2):
    sorted_pairs = sorted([(p1, p2, p1.DistanceTo(p2)) for p1 in points1 for p2 in points2], key=lambda x: x[2])
    used_p1, used_p2 = set(), set()
    sorted_points1, sorted_points2 = [], []

    for p1, p2, _ in sorted_pairs:
        if p1 not in used_p1 and p2 not in used_p2:
            sorted_points1.append(p1)
            sorted_points2.append(p2)
            used_p1.add(p1)
            used_p2.add(p2)

    return sorted_points1, sorted_points2

def create_lines_by_proximity(start_points, end_points):
    lines = []
    used_end_points = set()

    for start_point in start_points:
        sorted_end_points = sort_end_points_by_proximity(start_point, end_points)
        for end_point in sorted_end_points:
            if end_point in used_end_points:
                continue
                
            line = Line.ByStartPointEndPoint(start_point, end_point)
            intersecting = False
            for existing_line in lines:
                if is_intersecting(line, existing_line):
                    intersecting = True
                    break
            if not intersecting:
                lines.append(line)
                used_end_points.add(end_point)
                break
                
    return lines

def lines_from_points(start_points_lists, end_points_lists):
    result = []
    for start_points, end_points in zip(start_points_lists, end_points_lists):
        sorted_start_points, sorted_end_points = sort_points_by_proximity(start_points, end_points)
        lines = create_lines_by_proximity(sorted_start_points, sorted_end_points)
        result.append(lines)
    
    return result

start_points_lists = IN[0]
end_points_lists = IN[1]
OUT = lines_from_points(start_points_lists, end_points_lists)
10

I’m more lost than I was before. You’re showing two inputs in the python code, but are indicating that you have one input in the text. Can you post a dataset and graph so I can try to wrap my head around what you’re doing?

As a start for why this is failing, you are trying to pack all permutations of a list that is 38 items long into a list as ‘all combinations’. That is an infinite number; and an incalculable dataset.

A list 4 items long has 1\*2\*3*4, or 4! or 24 permutations. A list 38 items long has 5.2302261746660111176000722410007e+44 permutations. Assuming each item in that list types of one bit (they take more than that) you’d need at least 5 with 44 zeros bits of RAM to effectively handle the dataset. For a sense of scale, if you had 1tb of memory that is 8 with 12 zeros worth of bits.

So keeping the full data set in memory isn’t an option.

You could try to test one option at a time until you get one which works instead, but even then in cases where there isn’t a solution you would be having your computer run calculations for more time then you have available. Even if the solution was 1/4 of the way though the data set you’d have to run 3.5e^39 tests. At 1000 tests per second you’d only get 3e^10 tests done over a year…

1 Like
11

I shared script above that works, it creates lines not clashing between both input lists of points, but not for all the input points in some cases, it does not find more suitable points to create lines not clashing

12

Perhaps a loop issue?

Either way I think you’ll need to revisit the initial reasoning first. Not sure why you’re connecting the dots but if you can identify some of the common sense ‘A must connect to B’ first to reduce the scope and then sort the remaining set before connecting them things will likely work out better.

13

let say what I posted can work if there are not many points, I would say this is not resolved but not interested to dig on it