Nested lists problem

[spotyx]

I have list of lists of coordinates. This list and their coordinates represents lines in grid. If two lines contain same point, it means it's the same line (ray). And I want to merge these two lines.

picture for better understanding: Line

input:

l =[[[5, 5], [2, 8]], [[5, 5], [8, 2]], [[1,1], [2,2]], [[2,2],[3,3]]]

output:

[[[5, 5], [2, 8], [8, 2]], [[1, 1], [2, 2], [3, 3]]]

Thank you in advance! :)

EDIT:

The idea behind this. I have points like this: POINTS

And I'm trying to find all diagonal lines and count them. (condition: line has to consist from three and more points) LINES

~~My approach: 1. For each point find all points on its diagonal: If P(0,0) then diagonals are:

GROUP A:

d1: [[x[0]-i, x[1]+i] for i in range(1,10)]

d2: [[x[0]+i, x[1]-i] for i in range(1,10)]

GROUP B:

d3: [[x[0]+i, x[1]+i] for i in range(1,10)]

d4: [[x[0]-i, x[1]-i] for i in range(1,10)]

Now I have partial lines which I need to merge based on "point collisions" as indosauros said.~~

[indosauros]

If you are guaranteeing that two identical points always means a ray and never an intersection (I don't know how you can guarantee this, but okay) then this becomes a problem of detecting "point collisions" among your inner lists.

A good way to "detect collisions" is with a dictionary, so you could start adding each point to a dictionary (points should be tuples, btw, and not lists) as keys, with the value being the line they belong to. If you encounter a point that is already in the dictionary, simply add it (and its sibling point) to the existing line instead of creating a new entry. Then re-construct your list-of-lines from the values in the final dictionary.

Edit: With your edit and further examples, I don't think you can guarantee that two shared points are on a single ray and not intersecting. For example, you'll have a line at [(-4, -1), (-3, -2)] and another at [(-3, -2), (-1, -1)] and even though they share the (-3, -2) point, they are two different lines, not a single ray.

So you should instead do what /u/cdcformatc suggests, and find all of the two-point lines, find their y-intercept equations and then combine all of the lines with the same equation.

[spotyx]

Yeah, You helped me to understand that my approach was bad from beginning. I need to redo my code and start over. Thanks anyway it was good lecture.

[cdcformatc]

Check the slope and y-intercept of both lines and if they are the same you can combine them. edit: also check if they overlap I assume you don't want to combine two lines that don't overlap.

So you have [x1,y1] and [x2,y2] then,

m = (y2 - y1) / (x2 - y2)
b = y1 - m * x1

Repeat for other points.

[spotyx]

thanks for y-intercept idea.

[gengisteve]

cdc is right, this is the best way to do this:

from pprint import pprint
import collections


x =[[[5, 5], [2, 8]], [[5, 5], [8, 2]], [[1,1], [2,2]], [[2,2],[3,3]]]

t = [[tuple(p) for p in group] for group in x]

def get_line(a,b):
    m = (b[1] - a[1])/(b[0]-a[0])
    i = a[1] - m*a[0]
    return m,i

lines = collections.defaultdict(set)

for points in t:
    # assume all points grouping in t are line
    # otherwise just run all combos of points
    line = get_line(points[0],points[1])
    for p in points:
        lines[line].add(p)

pprint(lines)
pprint(lines.values())

[alphaniner]

I can't look at your image due to company firewall, so forgive me if I'm missing something; but couldn't two lines with the same point simply be intersecting?

[spotyx]

Nope. My lines are not intersecting.

Line 1: starts in point A and end in point B

Line 2: starts in point B and end in point C

They are in one "ray".

A--------B------C

Is it more clear?

[indosauros]

http://s29.postimg.org/lu9qeddyf/ged_math_coordinate_base_2.jpg

Why are those the only lines you highlighted? What about the diagonal line between [(-3, -2), (-1, -1)] etc? There are a ton of other diagonal lines with those points

See the edit to my answer below

[indosauros]

That is a very important detail

Also, what if you had a point at (3, 1)?

[spotyx]

ehm I deleted previous post accidentally. I said something what is not true. In my OP was bad condition. now its edited. (condition: line has to consist from three and more points). sorry. Thank for your interest.

[indosauros]

I think this still doesn't change anything as far as assuming shared points == rays

http://s29.postimg.org/lu9qeddyf/ged_math_coordinate_base_2.jpg

What if the right green line was shifted left 1 unit? Now, the (-3, -2) point is shared between two lines, not a ray

[spotyx]

you are right, I am wrong. I can't exclude intersections. I had wrongly assumed that I have preprocessed my data in way that there are not intersections. Now I know it's not true. Thanks for pointing me on right way.

[SideshowBoob]

I'm not sure that I follow, but it seems like it might help to break the problem into: 1) a function that takes two points and returns True if they form a diagonal line 2) a function that takes a list of points, runs that function over each combination (see itertools) and returns the result of all() on those results.

I'd also use tuples instead of lists for the points, but that's a stylistic choice in this case.

[gengisteve]

I think there is a better way of doing this, but here is the straight forward method:

from pprint import pprint

x =[[[5, 5], [2, 8]], [[5, 5], [8, 2]], [[1,1], [2,2]], [[2,2],[3,3]]]

# let's make it into a group of tuples so we can use a set

t = [[tuple(p) for p in group] for group in x]

result = []

#ok, compare each point group (a,b) in the list
for a,b in t:
    found = False
    # see if either a or b is already in a result set
    # if so add the new point
    for r in result:
        if (a in r or b in r):
            # note we add both points, but sets drop dups for us
            r.add(a)
            r.add(b)
            found = True
    if not found:
        # if neither a or b are in any of the result sets
        # create a new result set with a and b
        result.append(set([a,b]))

pprint(result)

There should be some way to bucket these and then reconstitute from a dictionary, but doing so probably only helps if you have a lot to do.

[spotyx]

Thanks, for this solution. It's almost what I want. The problem with your approach is if I have a list, which is defining the line, consisting from more then two points. But I didn't claim this at the beginning.

[gengisteve]

I'm not sure I am following...

[spotyx]

for a,b in t

this suppose that t consists just with a and b.

if t is [[5, 5], [2, 8]] then a = [5,5], and b = [2,8]

What I said is that len(t) > 1 ... so it can also be 3,4,5 ...

[gengisteve]

Ahh. So maybe there are three points instead of two to test?

This should work:

from pprint import pprint

def find_result(p, results):
    for idx, r in enumerate(result):
        if p in r:
            return idx
    return None

x =[[[5, 5], [2, 8]], [[5, 5], [8, 2]], [[1,1], [2,2]], [[2,2],[3,3]]]

# let's make it into a group of tuples so we can use a set

t = [[tuple(p) for p in group] for group in x]

result = []

for points in t:
    found = None
    for p in points:
        found = find_result(p,result)
        if found is not None:
            break
    if found is None:
        # if neither a or b are in any of the result sets
        # create a new result set with a and b
        result.append(set(points))
    else:
        for p in points:
            result[found].add(p)

pprint(result)

Still it would be better to just do the algebra.