What algorithm use to find the intersection area b

问题:

I have map. On the top of map layer have a polygon A and circle B. They are intersected each others. Any algorithm can calculate the area of intersection C ?

回答1:

Assuming that you're willing to take an approximation of the circle (a polygon with a large number of sides...) then there are a bunch of algorithms to compute the result of polygon clipping (see here, for a short listing).

A simple implementation pretty boils down to:

1. Determining what set of polygon A's points lie within polygon B, and vice versa
2. Determining the points of intersection for line segments that cross that inside-outside boundary, and
3. Constructing a new polygon from the set of points collected. To calculate the area of that new polygon, you can just decompose it into a collection of triangles and sum their areas.

If you don't feel like going through all of that work, try JS Clipper. It will probably make your life easier.

If you're not willing to make do with an arbitrarily good approximation of your circle, I figure you have to start finding intersections between polygon line segments and the boundary of your circle, then piecewise integrating each section.

回答2:

This can be done without approximations:

1. find intersections between polygon and circle
2. compose border of region of intersection - you will have sequence of line segments and arcs
3. calculate area of the region using Green's formula: http://en.wikipedia.org/wiki/Green%27s_theorem#Area_Calculation - Integral[border](x*dy-y*dx)

For every line segment calculating this integral is trivial - it's just x0*y1-y0*x1.

For circle arc it's a bit more verbose. Final result is Cx*(y1-y0) - Cy*(x1-x0) ) + R^2*(t1-t0), where (Cx,Cy) is center of circle, (x0,y0) is start of arc, (x1,y1) is end of arc, t0 is starting angle of arc, t1 is finishing angle of arc.

Just to make possible for anyone to verify the derivation, here is it: (for sure, it can be derived from geometry, but I've did it through formulas)

Integral[arc](x*dy-y*dx)

Integral[t=t0..t1]( (Cx+R*cos t)*R*cos t - (Cy+R*sin t)*(-R*sin t) )dt

Integral[t=t0..t1]( (Cx+R*cos t)*R*cos t + (Cy+R*sin t)*R*sin t )dt

Integral[t=t0..t1]( Cx*R*cos t + R^2*cos^2 t + Cy*R*sin t + R^2*sin^2 t )dt

Integral[t=t0..t1]( Cx*R*cos t + Cy*R*sin t + R^2*sin^2 t + R^2*cos^2 t )dt

Integral[t=t0..t1]( Cx*R*cos t + Cy*R*sin t + R^2 )dt

Integral[t=t0..t1]( Cx*R*cos t + Cy*R*sin t )dt + R^2*(t1-t0)

Integral[t=t0..t1]( Cx*R*d(sin t) - Cy*R*d(cos t) ) + R^2*(t1-t0)

Cx*R*(sin t1-sin t0) - Cy*R*(cos t1-cos t0) ) + R^2*(t1-t0)

Cx*(y1-y0) - Cy*(x1-x0) ) + R^2*(t1-t0)