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

Spherical Trigonometry, Circle Packing, and Lead Generation – A Journey(blog.ablelending.com)

43 points by shayanjm 11 years ago | 9 comments

mturmon 11 years ago |

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).

shayanjm 11 years ago | |

That's smart - coupling this with the 'min layers' equation could lead to a 100% iterative solution. We could swap this component in and remove the recursive triangle generation :)

As mentioned in the post - deduping is cheap and easy so introducing the third basis vector u3 could potentially be a great move away from the recursive logic that currently plagues the project.

mturmon 11 years ago | | |

The above is known to be the optimal 2D packing for equal-size circles. If you want to geek out, consider an algorithm for the optimal packing for unequal-size circles. Say, if there is an importance or frequency measure associated with each plotted circle. Now you've got yourself a math problem.

skadamat 11 years ago |

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

madavidj 11 years ago | |

Seems like the animations took more time to make than the actual query sub-division. But I agree that the illustrations made the post much more easy to read.

lorddoig 11 years ago |

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?

vitd 11 years ago |

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?

shayanjm 11 years ago | |

Absolutely - this wasn't meant to be a be-all-end-all to lead generation by geographical bounds. This was more of a "I had a cool idea, wanted to test it, and here's how I went about doing that" sort of post. There are a ton of things that don't get picked up by social signals, but it's a low enough hanging fruit that I figured it was worth looking into to see if it was even a viable source of data at scale.

I think a 'real' analysis of the data at a much larger scale (probably state-wide would be a good test) would yield some interesting data on the effectiveness of this implementation in specific.

As mentioned in the post - the circle packing implementation itself is general enough to be used in other applications. The point was to show off a cool potential application for a solution to a non-intuitive problem.

ayylmaokai 11 years ago |

Pretty interesting read; I also love the graphics!