from Hacker News

Spherical Trigonometry, Circle Packing, and Lead Generation – A Journey

by shayanjm on 4/24/15, 7:58 PM with 9 comments

• by mturmon on 4/24/15, 9:05 PM

  Hmm. I think generating the centers is not so hard. All the centers for one triangular section lie along the points

    (x,y) = i * u1 + j * u2
  

  where (i,j) are nonnegative integers and the basis vectors u1 and u2 are:

    u1 = (1,0)
    u2 = (1/2, sqrt(3)/2)
  

  There is a 1:1 correspondence of (i,j) to centers, so you could generate all centers with a nested for loop.

  If you want to generate all centers in the hexagon (not just the triangle) and still preserve the 1:1 nature of the map from (i,j) to (x,y), you could just rotate 6 times by 60 degrees each time.

  Doing just this would introduce duplicates along the edges, where the triangular segments abut each other. You could eliminate those by insisting that i>0 rather than just i>=0.

  You could get the same effect as rotation by introducing a third basis vector u3, but then there would be duplicates in the map from (i,j,k) -> (x,y).

• by skadamat on 4/24/15, 8:04 PM

  The animations are incredible, more quantitative posts should have illustrations like the ones in this post!

• by lorddoig on 4/25/15, 12:31 AM

  Hexagonal packing is good but hexagonal packing into a hexagon appears to be leaving the edges of your search radius uncovered.

  The packing density is about aligning on a hexagonal lattice, the points of which are a simple function of the inner circle's radius - the points in each row are 2r apart and every other row is horizontally offset by 2r * tan(60) (I hope that's right). Could you not build a row of circles out from the center to the right edge and copy it to the rows above, offsetting as required? The length of any given row is then half of the chord it sits on i.e. sqrt(r^2 - d^2) where d is the distance from the center, in this case 2r * row-index -- with this you can then filter out which circles are outside the containing circle for that row. This fills the top-right quarter segment of the circle, and the whole thing can be filled by flipping the coordinates along x to get the bottom right, and flipping all of that along y to get the other half, then dedup the cross that forms in the middle.

  I think, in terms of coverage, this must always be at least as good as a hexagon built out from the center, but that should be a rare case and most of the time it'd be better.

  Evidently I'm not a mathematician. Am I being stupid here?

• by vitd on 4/24/15, 9:47 PM

  Very neat idea, and as others have said, cool animations! However, I'm not sure I buy the premise that "Social media signals can be used to give a rough picture of foot traffic around places of business," at least in general.

  I can believe it for restaurants, hotels and popular hang-outs. But thinking about churches, strip clubs, the urologist, etc., I wonder if there are "blind spots" or other areas of low-quality data. Or even areas of poor cell coverage?

  Maybe in most cities there are enough other places around that people frequent to cover over any blind spots? I'd be interested to know whether they've found any places like that?

• by ayylmaokai on 4/24/15, 9:20 PM

  Pretty interesting read; I also love the graphics!