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

Time:02-11

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.

CodePudding user response:

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.

  • Related