My questions are concerning this part:
std::size_t adj_start_row = row == 0? 0 : row - 1; std::size_t adj_end_row = row == rows - 1? row : row + 1; std::size_t adj_start_column = column == 0? 0 : column - 1; std::size_t adj_end_column = column == columns - 1? column : column + 1; for (std::size_t other_row = adj_start_row; other_row <= adj_end_row; ++other_row) for (std::size_t other_column = adj_start_column; other_column <= adj_end_column; ++other_column) if (other_row != row || other_column != column) { // Repulse vertices in this bucket bucket_t& other_bucket = buckets[other_row * columns + other_column]; for (v = other_bucket.begin(); v != other_bucket.end(); ++v) apply_force(*u, *v); }
In the code above, where repelling forces inside a bucket are computed, each pair of nodes is considered only once, and then apply_force(*u, *v); apply_force(*v, *u); are called. Wouldn't something like this be more efficient here, too? We have +------+------+------+ | | | | | 1 | 2 | 3 | | | | | |------|------|------| | | | | | 4 | X | 6 | | | | | |------|------|------| | | | | | 7 | 8 | 9 | | | | | +------+------+------+, where X is the bucket u resides in, and the others are the adjacent buckets considered. For every u, all nodes from all other buckets are considered. My proposal: Consider only 1, 2, 3 and 4 and do apply_force(*u, *v); apply_force(*v, *u); again 6, 7, 8 and 9 will be considered when those buckets are processed. Shouldn't this be (at least a bit) more efficient?