fork download 
  1. #include <cstddef>
  2. #include <list>
  3. #include <vector>
  4. #include <set>
  5. #include <algorithm>
  6. #include <iostream>
  7.  
  8. typedef std::size_t entity_id_t;
  9. typedef long entity_pos_t;
  10. typedef std::size_t entity_length_t;
  11.  
  12. struct Entity {
  13.   entity_id_t id;
  14.   entity_pos_t pos;
  15.   entity_length_t length;
  16. };
  17.  
  18. typedef std::pair<entity_id_t, entity_id_t> collision_t;
  19.  
  20. template<class EntityContainer>
  21. std::list<collision_t> collision_check(const EntityContainer& entities) {
  22.   struct Boundary {
  23.     entity_id_t id;
  24.     entity_pos_t pos;
  25.     enum {
  26.       StartBound,
  27.       EndBound
  28.     } type;
  29.   };
  30.  
  31.   const std::size_t n = entities.size();
  32.   std::vector<Boundary> boundaries(2 * n);
  33.   {
  34.     std::size_t i = 0;
  35.     for(const Entity cur : entities) {
  36.       boundaries[i] = {cur.id, cur.pos, Boundary::StartBound};
  37.       boundaries[++i] = {cur.id, entity_pos_t(cur.pos + cur.length),
  38.                          Boundary::EndBound};
  39.       ++i;
  40.     }
  41.   }
  42.   std::sort(boundaries.begin(), boundaries.end(),
  43.             [](Boundary fst, Boundary snd) {
  44.     return fst.pos < snd.pos ||
  45.            (fst.pos == snd.pos && fst.type == Boundary::EndBound &&
  46.             snd.type == Boundary::StartBound);
  47.   });
  48.   std::set<entity_id_t> unclosed;
  49.   std::list<collision_t> collisions;
  50.   for(const Boundary bound : boundaries) {
  51.     if(bound.type == Boundary::StartBound) {
  52.       for(const entity_id_t id : unclosed)
  53.         collisions.push_back({id, bound.id});
  54.       unclosed.insert(bound.id);
  55.     }
  56.     else
  57.       unclosed.erase(bound.id);
  58.   }
  59.   return collisions;
  60. }
  61.  
  62. int main() {
  63.   /* entity 0: ....____
  64.    * entity 1: ..___...
  65.    * entity 2: __......
  66.    * entity 3: .__.....
  67.    */
  68.   std::vector<Entity> entities({{0, 4, 4}, {1, 2, 3}, {2, 0, 2}, {3, 1, 2}});
  69.   const auto collisions = collision_check(entities);
  70.   for(collision_t cur : collisions)
  71.     std::cout << "entities " << cur.first << " and " << cur.second
  72.               << " collide\n";
  73. }
Success #stdin #stdout 0s 3464KB
comments (?)
stdin 
Standard input is empty
stdout 
entities 2 and 3 collide
entities 3 and 1 collide
entities 1 and 0 collide
https://ideone.com/LsyfIn
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!