0

How can I sort std::vector<vec2> containing vec2(x, y) coordinates based on their distance from point 0.0?

Example: I'd like to sort this:

std::vector<vec2> vec = { vec2(9,9), vec2(1,1), vec2(5,5), vec2(4,4) };

Into this:

std::vector<vec2> vec = { vec2(1,1), vec2(4,4), vec2(5,5), vec2(9,9) };
Carrot Cake
  • 57
  • 2
  • 8
  • A lot of the answers on the dupe are dated, [this one](https://stackoverflow.com/a/26295515/6564148) is probably your best bet. – George Aug 04 '18 at 08:18
  • @It'scominghome Yes, I'd also choose a lambda function to solve that problem. – πάντα ῥεῖ Aug 04 '18 at 08:35
  • It's unfortunate that this was closed already, because the predicate you need to use for sorting the vector is a bit more involved than just directly comparing two elements and it's worthy of an answer of its own that's hard to fit into just a comment. The sort predicate function has to calculate the distance from 0 of its two arguments and compare *that*. The interesting part is figuring out if it's worth precomputing the distances to avoid recalculating them a ton of times by using a [Schwartzian transform](https://en.wikipedia.org/wiki/Schwartzian_transform) or something similar. – Shawn Aug 04 '18 at 08:36
  • @Shawn `vec2` could have a simple `length()` function, and elements yould be sorted in directly comparing the results of that one. – πάντα ῥεῖ Aug 04 '18 at 08:51
  • Sorting the vector should work. Instead of `length()` I would prefer `length()`² as it can eliminate the expensive `sqrt()` (which has no added value for this comparison). Using the [Manhanttan distance](https://en.wiktionary.org/wiki/Manhattan_distance) might work as well but would be even cheaper. (This depends on context which is not provided.) However, Manhattan distance would change the order a bit. (E.g. with Eucledian distance |(1, 1) - (0, 0)| < |(2, 0) - (0, 0)| but with Manhattan distance it would be equal.) – Scheff's Cat Aug 04 '18 at 09:32
  • _Sorting the vector should work._ (Sorry, this was just the beginning of another thought.) Using a `set` or `map` instead, the `length()` wouldn't be enough (as multiple points may have same distance to (0, 0) e.g. (1, 0) and (0, 1)). If this were required, I would add an additional comparison to the predicate which provides an order of vectors with equal length (e.g. comparing x components when length (or square length) is equal). – Scheff's Cat Aug 04 '18 at 09:43

0 Answers0