StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Make a map of "regions", basically, a <code>std::map<coordinates/len, std::vector<point>></code>. Add each point to it's region, and each of the 8 neighboring regions <code>O(N*logN)</code>. Run the "nieve" algorithm on each of these smaller lists (technically <code>O(N^2)</code> unless theres a maximum density, then it becomes <code>O(N*density)</code>). Finally: On your origional list, iterate through each <code>point</code>, and if it has been removed from <em>any</em> of the 8 mini-lists it was put in, remove it from the list. <code>O(n)</code></p> <p>With no limit on density, this is <code>O(N^2)</code>, and slow. But this gets faster and faster the more spread out the points are. If the points are somewhat evenly distributed in a known boundary, you can switch to a two dimensional array, making this <em>significantly</em> faster, and if there's a constant limit to the density, that <em>technically</em> makes this a <code>O(N)</code> algorithm.</p> <p>That is how you sort a list of two variables by the way. The grid/map/2dvector thing.</p> <p>[EDIT] You mentioned you were having trouble with the "nieve" method too, so here's that:</p> <pre><code>template<class iterator, class criterion> iterator RemoveCriterion(iterator begin, iterator end, criterion criter) { iterator actend = end; for(iterator L=begin; L != actend; ++L) { iterator R(L); for(++R; R != actend;) { if (criter(*L, *R) { iterator N(R); std::rotate(R, ++N, actend); --actend; } else ++R; } } return actend; } </code></pre> <p>This should work on linked lists, vectors, and similar containers, and works in reverse. Unfortunately, it's kinda slow due to not taking into account the properties of linked lists. It's possible to make <em>much</em> faster versions that only work on linked lists in a specific direction. Note that the return value is important, like with the other mutating algorithms. It can only alter contents of the container, not the container itself, so you'll have to erase all elements after the return value when it finishes.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload