Zombie Door


Zombies are pretty cool.  This post describes something a little less cool, but uses zombies to explain the concept (in a shallow, transparent attempt to capture your attention!)

Zombie Door Method

Imagine we want to generate a uniformly distributed random sampling in some complex space that our random number generator does not directly support.

Let me start with an simple example.  Imagine we have a random number generator that produces a random integer between 1 and 100.  However, we actually want to generate random numbers between 41 and 50.  (I know there are better ways to do this, but stick with me for this example.)  Let’s solve this with the zombie door method.

  • Build a wall and label it 1-100 where 1 is to the far left, and 100 is to the far right.
  • Cut a door in your wall from 41 to 50.
  • Now create random zombies starting anywhere from 1 to 100 and let them walk straight towards the wall.
  • The zombies will lurch across the room and eventually hit wall, explode, and dissolve in a fizzing puddle of bloody goo … or whatever it is that zombies do when they die.
  • The zombies that are lucky enough to walk through the door survive!

For this example it would be easy to scale and offset the usually available random number generator that produces a floating point value between 0 and 1, but it illustrates the basic approach of the ‘zombie door’ method.

A More Interesting Example

Imagine we have an arbitrary polygon outline and we want to splatter it with random circles.  However, we only want circles that are completely within the polygon.  (And we want our random circles to be a true  unbiased, uniformly distributed random sample.)  This example is just like the simple ‘wall’ example except now we have gone ‘2D’.

Imagine an arbitrary polygon shape:

We would like to fill this shape with 200 random circles, making sure none of our circles straddle the boundary or lie outside the polygon.  We want an even distribution over the interior area of our polygon.

We can do this by generating random circles within the min/max range of our shape, and then testing if they lie completely inside the polygon.  We reject any outliers and keep the inliers.  It’s very simple, but very cool because … you know … zombies!  Here is a picture of how our circles turned out:

If you are at all curious as to what became of our dead zombies (all the ones that splatted against the wall) here is the picture of that:

If you the reader are concerned that I am making light of a very real pending zombie apocalypse issue then here is my best tip for protecting your residence:

Finally, here is the python script I used to generate the pictures in this posting.  I leverage the very, very, very cool GPC polygon clipping library to test if the outline polygon ‘covers’ the circle.

import random
# polygon (GPC) python package: https://pypi.python.org/pypi/Polygon2
import Polygon
import Polygon.IO
import Polygon.Shapes
# this will seed the random number generator with current time and
# force different results on each run.
# this is the bounds of the shape that will contain our splatters
outline = [ [0.5, -0.01], [1.01, -0.01], [0.5, 1.01], [-0.01, 1.01] ]
# define circle properties
num_circles = 200
min_r = 0.002
max_r = 0.02
# no closer than this to the boundary
margin = 0
#margin = 0.002
# create the polygon template (outline)
template = Polygon.Polygon(outline)
# make the shape a bit more interesting
c = Polygon.Shapes.Circle(radius=0.4, center=(1, 0.5), points=32)
template = template - c
c = Polygon.Shapes.Circle(radius=0.3, center=(0, 1), points=32)
template = template - c
# determine max/min of template
min_x = max_x = outline[0][0]
min_y = max_y = outline[0][1]
for p in outline:
 if p[0] < min_x: min_x = p[0]
 if p[0] > max_x: max_x = p[0]
 if p[1] < min_y: min_y = p[1]
 if p[1] > max_y: max_y = p[1]
print 'template bounds:', min_x, min_y, 'to', max_x, max_y
print 'radius range:', min_r, max_r
print 'margin:', margin
print 'num circles:', num_circles
# generate splats using zombie door method
circles = []
discarded = []
while len(circles) < num_circles:
 x = random.uniform(min_x, max_x)
 y = random.uniform(min_y, max_y)
 r = random.uniform(min_r, max_r)
 # make the circle
 c = Polygon.Shapes.Circle(radius=r, center=(x, y), points=32)
 # make the circle padded with extra margin
 cm = Polygon.Shapes.Circle(radius=(r+margin), center=(x, y), points=32)
 if template.covers(cm):
  # circle + margin fully contained inside the template
# assemble final polygons and write output
final = Polygon.Polygon()
for c in circles:
 final += c
Polygon.IO.writeGnuplot('in.plt', [template, final])
Polygon.IO.writeSVG('in.svg', [final], fill_color=(0,0,0))
reject = Polygon.Polygon()
for c in discarded:
 reject += c
Polygon.IO.writeGnuplot('out.plt', [template, reject])
Polygon.IO.writeSVG('out.svg', [reject], fill_color=(0,0,0))

Failure is not fatal

This post is penned during a moment of extreme frustration, beware!

Kobayashi Maru


One of the reasons I loved the original Star Trek series is because no matter what the odds, no matter how hopeless the circumstances, no matter how impossible the foe, Captain Kirk always found a way to think his way out of the mess.  He never ultimately failed or lost to an opponent, not once, not ever.  That makes a great hero and fun TV!  Fictional super heroes do things that normal human beings could never possibly do … like fly, or be stronger than steel, or always win.

Stress and the Brain

I don’t have time to read stuff like the following link, especially when I’m coming up short of a promised deadline.  Maybe you do?  http://www.health.harvard.edu/staying-healthy/understanding-the-stress-response

I’m told that when we begin to get stressed, the front area of the brain that is responsible for logic and reason starts to shut down, and command functions begin to be transferred back to the “fight or flight” portion of the brain.  I think about standing up in front of a group and speaking, then sitting down and wondering what I even said?  I think about arguments that got out of hand?  Where was the front part of my brain in all of that?  I think about looming deadlines and mounting stress … and … and … and mounting stress!

Recursive Stress

My job largely amounts to puzzle solving.   I love the process and I love finding clever solutions.  But if I ask you a riddle or give you a logic problem, can you give me a specific estimate of how much time it will take you to solve it?  That’s not how puzzle solving works, it’s not a step by step recipe that leads to a solution in a known time.  Failing to solve the problem in time stresses me out!  What is needed in these situations is clear, logical, and calm thinking.  But that is the first part of the brain to turn off during stressful situations!  It’s exactly the part of the brain we desperately need the most.  I know all this, and I watch helplessly as it happens.  What does that create?  More stress of course which accelerates the process of losing the most important part of my brain!

What is the solution?

No, seriously, what is the solution???

People often say they do their best work under pressure.  I know for myself, I do my worst work under pressure.  I strive whenever possible to get a long head start on a complex and difficult task.  I strive whenever possible to identify and solve the hardest parts of the task first.  But that isn’t always possible.

So instead I sometimes see failure coming weeks away, maybe like an asteroid on a collision course with earth.  I’m very serious about the task, I do everything I possibly can, I pour in all my energy and expertise, but it’s not always enough.  Things I thought would be easy turn out to be 10x more difficult than imagined.  Things that were working break for unexpected reasons.  Things that shouldn’t take time, take way too much precious time.

Captain Kirk to the rescue?  Sadly, no … he is a fictional character.  In the real world the asteroid looms bigger and bigger, it’s trajectory is a mathematical certainty.  The physics of the impact can largely be predicted.  At some point it becomes clear my efforts will fall short and there’s nothing left to do but watch the asteroid in it’s last few hours of flight.  Then <boom>.

Is it just me that fails colossally?

It usually seems like I’m the only one that makes a miserable mess of things I try to do, the things I’ve promised I could do, things I’ve been paid to do.  Everyone else is posting about their giant success on facebook.  Everyone else’s resume is a spotless collection of triumphs.  But not me.  Maybe once or twice I got lucky and the rest of the time is a huge struggle!  Honestly though, the only reason I’m posting this is because I know it’s not just me.  Any sports fans out there?  How many teams and players succeed to win the championship every season?  What percentage of players ever win a championship in their whole career?  Political success and failure?  How many new businesses succeed versus failing?

High Profile Failures

By mentioning specific companies, I don’t mean to imply specific people or imply anything negative here.  My intent here is to show we are all in this together and we all, even the best and most successful of us, suffer set backs in our work.  I live and work in the world of drones (or small unmanned aerial systems, aka UAS’s).  This is a tough business.  For all the hype and excitement even big companies can struggle.  Gopro recently did a full recall of their new drone product.  Hopefully they’ll try again in 2017, and hopefully the process will go better for them.  Recently 3DR, the king of DIY drones announced they were cancelling all their hardware efforts to focus on a software package for managing data collected by drones.  Parrot (another big name in the small drone market) just announced layoffs.  Edit: 12 Jan, Lily just announces it is dropping out of the drone race and shutting down.  Edit: Facebook Aquila crashed on first test flight.  Edit:  Titan (google’s own high altitude effort solar powered effort) is shut down.  It’s tough, even for the big guys with enough money to hire the best engineers, best managers and do professional marketing.

There are even higher profile failures than these … Chernobyl, TIger Woods, the Titanic, Exon Valdez, the Challenger, and most Sylvester Stallone movies except for Rocky I.

The Aftermath

So the asteroid hit.  In the last moments we just threw up our hands, gave up, and just watched it come in and do it’s destruction.  The dust is settling, what happens next?  Maybe the asteroid wasn’t as big as we imagined?  Maybe the damage not as severe?  Maybe life goes on.  In a work context, maybe you take a big professional hit on your reputation?  Maybe you don’t?  Maybe it’s about survival and living to fight another day?

Failures suck.  Failures happen to everyone.  Failures are [usually] not fatal.  The sun will still rise tomorrow for most of us.

Survival – Yes?!?

If you are reading this, you are still here and still surviving.  That’s great news!  Hopefully I’m here too!  Lets all live to fight another day.  Let’s all help each other out when we can!  There is a word called “grace” which is worth looking up if you don’t know what it means.  It’s a quantity that we all need more of and we all need to give each other in big healthy doses!

“Success is not final; failure is not fatal. It is the courage to continue that counts.” — Budweiser ad, 1938.  (Not Winston Churchill)