CODEWITHSUNDEEP
algorithmcomputational-geometry
Jge
Jge

Reputation: 165

Figuring out adjacent points on the same line

Given a list of points on the same line, I need to find out the the adjacent points for each point. See the image for illustration

I know the coordinates of all the points. These points are ordered randomly in my input list.

My approach:

  1. Choose the first point in the list. Find vectors from this point to all the points.
  2. For each vector, find the anticlockwise angle.
  3. There are only two angles(a1, a2) possible. Form a list of all the points which are with angle a1, and a list of points with angle a2.
  4. Now for each list, find out the euclidean distance/vector length.
  5. Sort this list in ascending order, which can be used to establish relative ordering.

Ex: If p2 happens to be the first point in the list, then, assuming that the smaller angle is 30, the larger clockwise angle will be 210. So, p1 will lie in one list. p3,p4,p2 will lie in the other list. Now I can get the relative ordering of the points.

Is there any better solution?

Upvotes: 2

Views: 769

Answers (1)

mnistic
mnistic

Reputation: 11020

  1. Compare the Y axis of the first two points to find out if the line is vertical. (O(1))
  2. If vertical, sort by the Y axis (O(nlogn))
  3. If not vertical, sort by the X axis (O(nlogn))
  4. To find adjacent points, find point in sorted list by binary search (O(logn)) and take previous and next points.

Upvotes: 4

Related Questions