Timeline for Swiftly counting rooms in a floor plan
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 23, 2018 at 19:14 | comment | added | Martin R | Happy to accept :) | |
| Jul 23, 2018 at 19:13 | vote | accept | Martin R | ||
| Jul 23, 2018 at 19:12 | comment | added | Cris Luengo | @MartinR: Happy to oblige. | |
| Jul 23, 2018 at 19:12 | history | edited | Cris Luengo | CC BY-SA 4.0 |
added 1820 characters in body
|
| Jul 23, 2018 at 18:45 | comment | added | Martin R | Your above advice to "keep an array of UnionFind elements, and refer to them by their index instead" – in connection with your blog post – turned out to be essential for me to understand the algorithm better and implement it faster. Could you add that information to your answer? | |
| Jul 23, 2018 at 18:38 | comment | added | Cris Luengo | @MartinR: Yes, that is true, the array keeps growing and never shrinks, many of the elements in it are no longer used. There is a compromise there between speed and memory usage. Re-claiming memory during the running of the algorithm takes time. Note that you can determine the maximum number of elements this vector can potentially have: in your case of edge-neighbors (each element has 4 neighbors), you can have up to N/2 unique labels, with N the number of elements in the input matrix. That is not a whole lot of memory, and you can allocate such an array from the start to prevent reallocation. | |
| Jul 23, 2018 at 18:28 | comment | added | Martin R |
I just tried a new implementation based on your crisluengo.net/index.php/archives/913#more-913 blog post, and that turned out to be much faster (factor 5 to 8 for a 2500x2500 map). The only thing I wonder about is the memory consumption: In my implementation, nodes which are not referenced anymore (i.e. rooms which are not reachable anymore) are deallocated automatically. Your vector-based approach is faster, but the std::vector<int> A; only grows and never shrinks.
|
|
| Jul 23, 2018 at 17:48 | comment | added | Martin R | Indeed: I made some benchmarks with random 2500x2500 maps, and could not observe a significant difference between using rank or not. | |
| Jul 22, 2018 at 23:20 | history | answered | Cris Luengo | CC BY-SA 4.0 |