Random line through a polygon

Question

The problem:

I have trouble generating a random line that cuts through a polygon (not necessary convex). The lines should have the same distribution as completely random lines (random position, random angle), disregarding those that miss the polygon entirely.

My thoughts so far:

Picking a random point inside the polygon (I have that algorithm already) and picking a random angle won't do, because a hammer shaped object would be cut more often through the head (it has a larger area than the handle), where a completely random line would be more likely to cut through the handle. Also the angle would defenitely not be uniformly distributed.

For the same reasons it's not possible picking two points inside or on the surface and generating a line that goes through both points or any similar methods.

Edit: I have two methods that I can use but I'm not perfectly satisfied with either of them.

1. Find a circle that contains the polygon. Pick random lines through the circle until you find one that also cuts through the polygon. This basically the definition that I wrote above only with a higher chance of hitting the polygon.

2. Project the polygon in n directions (e.g. 0°, 10°, 20° etc.). The size of the projection is proportional to the likelyhood of getting hit from this direction. Then I pick a direction (using the projection-size as weighted probabilies). Finally, I can add a 360/n° jitter the the angle. This should approximate the distribution well enough but I wonder if there is a better way of doing it.

Edit2: -deleted-
I had written quite a lot but after thinking some more about it and discovering some mistakes I realized that this is getting over my head. The idea was to project a convex hull of the polygon in just a few, certain directions and finding a function that gives us all the other projections by blending between the known ones. But the details turned out to be quite convoluted and just too much for me at the moment.

Answer 1

The notion of random line intersecting with a figure is surprisingly awkward to define rigorously: see Bertrand's paradox for a well-known example of the ambiguity in this kind of idea. Even a random line in the plane is not easy to define: you might try something like "a line passing at a random angle through a random point", but how do you choose a random point? There's no uniform distribution over points in the plane.

Here's a way to precisely define random line intersecting with a figure F. Let w(θ) be the width of the figure F perpendicular to the angle θ:

When F is a polygon, then w(θ) is made out of piecewise sine functions, with as many pieces as the convex hull of the polygon has antipodal pairs of vertices.

Now, choose an angle θ using p(θ) as the probability density function, where

p(θ) = w(θ) / ∫ w(θ) dθ

and then choose the position of the line uniformly on the interval [0, w(θ)].

(Your method #2 tries to approximate p(θ) by sampling a small number of values of θ and constructing a piecewise-constant distribution. But we can get an exact result without too much extra difficulty.)

To compute the integral ∫ w(θ) dθ (and thus p(θ)), first find the convex hull of your polygon, and then use the rotating calipers method to find the antipodal pairs of vertices. Between adjacent antipodal pairs, the calipers move from θ₀ to θ₁, say, and in this range w(θ) is given by

w(θ) = d sin(θ − φ)

where φ is the angle of the line between the antipodal vertices d is its length, as shown in the two figures below:

Now over the range θ₀ to θ₁, the indefinite integral is:

∫ w(θ) dθ = ∫ d sin(θ − φ) dθ = − d cos(θ − φ)

and so the definite integral of w(θ) for the range [θ₀, θ₁] is

d (cos(θ₀ − φ) − cos(θ₁ − φ))

Sum this up over all pairs of antipodal points and you've computed the whole integral.