Sign in to follow this  
csp256

Intersection of half-plane and square

Recommended Posts

csp256    157

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.

Edited by csp256

Share this post


Link to post
Share on other sites
Randy Gaul    2762

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?

Share this post


Link to post
Share on other sites
Waterlimon    4398

If performance isnt an issue, I would just grab some polygon library (such as this one that I found using google and probably can do what you want) and use that.

 

Under the assumptions that:

-You dont need it to be specifically optimized for this operation AND you know this wont be the case in the future either with high probability

-You might need to do similar things elsewhere

 

If you do need it to be perfectly optimal, I would find which edges and where are being intersected, and then handle each case separetely (4 'corner' intersections -> area of triangle, 2 'half' intersections -> area of trapezoid with only one slanted side, then handle outside/inside)

(Im not saying this is perfectly optimal though)

Share this post


Link to post
Share on other sites
csp256    157

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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this