python - Sorting points on multiple lines -

python - Sorting points on multiple lines -

given have 2 lines on graph (i noticed inverted numbers on y axis, mistake, should go 11-1)

and care whole number x axis intersections

we need order these points highest y value lowest y value regardless of position on x axis (note did these pictures hand may not line perfectly).

i have couple of questions:

1) have assume known problem, have particular name?

2) there known optimal solution when dealing tens of billions (or hundreds of millions) of lines? our current process of manually calculating each point , comparing giant list requires hours of processing. though may have hundred 1000000 lines typically want top 100 or 50,000 results of them far "below" other lines calculating points unnecessary.

your info construction set of tuples

lines = {(y0, Δy0), (y1, Δy1), ...}

you need ntop points, hence build set containing top ntop yi values, single pass on data

top_points = choose(lines, ntop)

edit --- take ntop had maintain track of smallest one, , interesting info, let's homecoming value choose, need initialize decremented

top_points, smallest = choose(lines, ntop) decremented = top_points

and start loop...

while true:

generate set of decremented values

decremented = {(y-Δy, Δy) y, Δy in top_points}

decremented = {(y-Δy, Δy) y, Δy in decremented if y>smallest} if decremented == {}: break

generate set of candidates

candidates = top_lines.union(decremented)

generate new set of top points

new_top_points, smallest = choose(candidates, ntop)

the next no more necessary

check if new_top_points == top_points

if new_top_points == top_points: break top_points = new_top_points</strike>

of course of study in loop...

the hard part choose function, think this answer question how can sort 1 1000000 numbers, , print top 10 in python? help you.

python math