I have a (non tilted) square bounded by the points (x, y) and (x+h, y+h). I would like to know the percentage (or area; doesn't matter) that intersects with a half plane. Performance is not a priority.

When I say half-plane, I mean the set of all points further away from (or closer to) the origin than a line of infinite extent. This line is internally specified by an angle theta, and a minimum distance S from the origin. (and a further boolean specifying if we include points "closer to origin" or "further away from origin")

How do I solve this problem?

First thought is to check for a line to line segment intersection for each edge of the square. Take the union of the square's vertices with all points returned from the previous check. This will give 4 to 6 vertices. I then throw away all vertices which fail the closer/further test. I am then left with a minimal set of convex bounding points (thus solving the problem in principle).

I am comfortable performing special case checks for theta = 0, pi/2, pi, and 3pi/2 radians to catch the special case where the line segment lies on the half plane border.

Is there a better way to do this? I feel like I am missing something obvious.

I'd use sutherland-hodgman clipping and then calculate the area of the leftover polygon, and divide this by the area of the original square. You can do some optimized scalar math for the clipping since you're dealing with one single plane.

Does this make sense?

Thank you for your responses!

Unfortunately using an external library is not an option because this project is a part of me teaching someone else how to program by guiding them through solving their problem (instead of just doing it myself).

I am very interested in the Sutherland-Hodgman algorithm (and computational geometry in general) but it is overkill for the moment. I have solved my problem using the method I outlined above, plus ordering the points. I accomplished this by taking arctangent of their relative vectors around their centroid: as I said, it did not need to be fast. I need to check approximately a million such intersections only once.

The line to line segment intersection had a particularly nice solution since x or y was a constant, and the line was already in normal (parametric) form, so I could find the intersection by

 x = r - tan(theta) * y

or by

y = r - cot(theta) * x

as needed.

I am treating theta=0,pi/2,pi,3pi/2 as special cases because it was important this individual function be no more complicated than necessary for pedagogical reasons.

Do you have any cool computational geometry resources for me (I know very little on the subject), outside the bounds of this project? I will soon check the appropriate forums/stickies.