Convert set of Coordinates into a sorted 2D Array

user_4126814 0
Viewed 297

Suppose I have a set of n coordinates (x, y) e.g. (123, 41), (123, 50), (555, 10), (600, 10)

And I wanted to convert it into a 2D array where:

  • The amount of columns is equal to the unique number of x coordinates

  • The amount of rows is equal to the unique number of y coordinates

  • No two set of coordinates will be exactly the same and there are no constraints on what the values of x and y can be.

  • A coordinate is placed at indices relative to the x and y of all other coordinates. E.g. (555,10) has the second greatest x coordinate (x=1) and one of the smallest y coordinates (y=0) so its position will be [1][0]

    x=0 x=1 x=2
    y=0 null (555, 10) (600, 10)
    y=1 (123, 41) null null
    y=2 (123, 50) null null

(There are 3 unique x coordinates (123, 555, 666) and 3 unique y coordinates (41, 50, 10) so array is 3x3)

What algorithm can I use to generate a 2D array from a set of coordinates as described above? I've attempted to create my own but it is very slow when n is very large O(n^2).

multidimensional-array coordinates sorting algorithm
1 Answers

Here's a simple solution:

  1. Get all distinct x and y coordinates and sort them.
  2. For each point, get the position of it's x and y coordinate in the respective sorted arrays. Place the point in this position in the result array.

Something like this (in Python):

# cook your dish here
points = [(123, 41), (123, 50), (555, 10), (600, 10)]
x_coords = sorted(list(set(i[0] for i in points))) # all distinct x coordinates
y_coords = sorted(list(set(i[1] for i in points))) # all distinct y coordinates
result = [[0 for i in range(len(x_coords))] for j in range(len(y_coords))]

for i in points:
    x_final = x_coords.index(i[0])
    y_final = y_coords.index(i[1])
    result[y_final][x_final] = i
    
for i in result:
    print(i)

This gives:

[0, (555, 10), (600, 10)]
[(123, 41), 0, 0]
[(123, 50), 0, 0]
  1. You can replace the zeros with None or null as per your convenience.
  2. This method has O(NlogN) time complexity.

Edit: index() method might not be the most efficient way depending on the language/data structure used. You can use binary search to implement the same.

user_93507200
Related