StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>First we redefine term as follows: Find such distribution of N points, that the length of minimal distance between any of two point of these and M predefined is maximal. So your task is to find this maximum of minimal length. Call it <code>L</code> You have M lengths of existing segments, assume they are stored in list <code>s</code>. So if this length is <code>L</code> first of all</p> <pre><code>min(s) > L </code></pre> <p>and maximum amount of additional points is</p> <pre><code> f(L) = sum(ls/L -1 for ls in s) </code></pre> <p>So you can find optimal L using the binary search taking starting minimum L = 0 and maximum L = min(s) and checking condition if sum(ls/L -1 for ls in s) >= N. Then for each segment s[i] you can just place s[i]/L -1 of points evenly of it. I think this is optimal solution.</p> <p><strong>Updated</strong> There was flaw in <code>min(s) > L</code>. It was good enough for redefined term, but mistake for the original. I have changed this condition to <code>max(s) > L</code>. Also added skipping of segments smaller than L in binary search. Here is full <em>updated</em> code:</p> <pre><code>from math import pi,floor def distribute(angles,n): s = [angles[i] - angles[i-1] for i in xrange(len(angles))] s = [ls if ls > 0 else 2*pi+ls for ls in s] Lmin, Lmax = 0., max(s) while Lmax - Lmin >1e-9: L = (Lmax + Lmin)/2 if sum(max(floor(ls/L) -1,0) for ls in s ) < n: Lmax = L else : Lmin = L L= Lmin p = [] for i in xrange(len(s)): u = floor(s[i]/L) -1 if u <= 0:continue d = s[i]/(u+1) for j in xrange(u): p.append(angles[i-1]+d*(j+1)) return p[:n] print distribute((0, pi/4),1) print distribute((-pi,-pi/2,pi/2),2 </code></pre>

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