6
$\begingroup$

I don't know relevant keywords about this algorithm. I can show you visually Sort elements like circular pattern

Second image is result

Any ideas are appreciated

$\endgroup$
3
  • 3
    $\begingroup$ ("scan|sweep line" or "line|plane scan|scanning|sweep|sweeping" and "polar coordinates"?) Are you looking for terminology or algorithm? Tag accordingly! $\endgroup$
    – greybeard
    Feb 25 '20 at 9:11
  • 1
    $\begingroup$ Take a look at stackoverflow.com/questions/6989100/… $\endgroup$
    – ciamej
    Feb 25 '20 at 17:12
  • 1
    $\begingroup$ This reminds me of parts of the Jarvis March algorithm or Graham scan for convex hull calculation. Maybe these articles will give you some additional wording clues. $\endgroup$ Feb 25 '20 at 22:38
9
$\begingroup$

For each of your points in the field, calculate the red angle: enter image description here

Then sort all the (point, angle)-tuples by the angle.

$\endgroup$
2
$\begingroup$

Here's a way to sort points by angle in Swift:

let radarSortedPoints: [CGPoint] = points.sorted { pointA, pointB -> Bool in
    atan2(pointA.y, pointA.x) < atan2(pointB.y, pointB.x)
}
$\endgroup$
2
  • 4
    $\begingroup$ Just a note, the use of atan2 is not necessary, see github.com/Laakeri/contestlib/blob/master/src/geometry/… for an implementation that is exact for integers. $\endgroup$
    – Laakeri
    Feb 25 '20 at 9:55
  • $\begingroup$ @Laakeri Isyourspacekeybroken? lol why would you type def something as clear as complex<long long> to something as arbitrary and cryptic as co? $\endgroup$
    – Alexander
    Feb 25 '20 at 23:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.