CODEWITHSUNDEEP
algorithmdistance
Prakhar Sharma
Prakhar Sharma

Reputation: 758

How to know if two spatial points are coinciding in an array of 50000 points?

Let us say I have 50000 "3D spatial coordinates" in a 1D array. I want two know if there are two points that are coinciding. If yes, which ones, or how many pairs?

I know I can use the distance formula but that would be really costly and will create a 2D array of 50k X 50k i.e. each column for relative distance of every single point w.r.t other points.

I am looking for an efficient algorithm.

Upvotes: 0

Views: 25

Answers (1)

MBo
MBo

Reputation: 80287

The first way: use hashtable/map/dictionary. O(n) amortized complexity, O(n) memory

Put points there one-by-one. If there is no such key in dictionary yet, add pair (coordinates; value=1), otherwise increment value field.
In Python, for example, there is Counter intended for this kind of problems.

The second way: sorting. O(nlogn) usual complexity.

Sort points, using special comparator: compare X-coordinate first, in case of eqiality compare Y-coordinate, in case of equality compare Z. After that walk through sorted array, similar points will stand together.
In Python default comparator for such structures works as needed.

Upvotes: 1

Related Questions