Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Suppose you have <code>M</code> points already given, and <code>N</code> more need to be added. If all points were evenly spaced, then you would have gaps of <code>2*pi/(N+M)</code> between them. So, if you cut at your <code>M</code> points to give <code>M</code> segments of angle, you can certainly place points into a segment (evenly spaced from each other) until the space is less than or equal to <code>2*pi/(N+M)</code>.</p> <p>So, if the length of a segment is <code>L</code>, then you should place <code>floor(L*(N+M)/(2*pi)) - 1</code> points into it.</p> <p>Now you're going to have some points left over. Rank the segments by the spacing that you would have between points if one more point was added. Actually add the point to the segment with lowest rank. Re-insert that one into your sorted list and do this again, until you run out of points.</p> <p>Since at every time you're placing a point into a segment where the result will be points as widely spaced as possible, and space between points is not dependent on the order in which you added them, you will end up with the optimal spacing.</p> <p>(Edit: where "optimal" means "maximal minimum distance between points", i.e. avoiding the worst-case scenario of points on top of each other as best as possible.)</p> <p>(Edit: I hope it's clear that the idea is to decide how many points go into each segment, and then only at the very end, after the numbers have all been decided, do you space them out equally within each segment.)</p>
    singulars
    1. This table or related slice is empty.
    1. PODistribute points on a circle as evenly as possible
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USMatthieu M.
    1. USRex Kerr
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. CONice answer. I'd consider first transforming the problem into 'Cut M pieces N times' to remove the confounding circle-angle stuff, though.
      singulars
      1. PO
      1. USCraig Gidney
    2. COI think I understand where you're going but must admit I've lost myself. Notably I don't understand in which case the left-over points occur. It seems to me that at worst you would actually have more places available than points to place is that what you mean ?
      singulars
      1. PO
      1. USMatthieu M.
    3. CO@Matthieu M.: When you place `floor(L*(N+M)/(2*pi))-1` points into a segment of length `L`, you will almost certainly find spots for fewer points than you wanted to (i.e. less than `N`). This is by construction--this places only points that you're absolutely sure will fit, and leaves you to place the others by a method that will let you guarantee that you put them in the best spot.
      singulars
      1. PO
      1. USRex Kerr
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

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