Hello, One possibility which gives an exact result and has the complexity of O(n*log(n)) where n is the number of vertices (edges) in the polygon would be to use Green's theorem. One consequence of it is that id D is a 2 dimensional region which boundary is a simple (and piecewise continuously differentiable) curve C than the area of D is the integral over C of xdy. Given a polygon and a circle, find all the intersection points and order them in a clockwise direction (this has an O(n*log(n)) complexity - everything else is O(n)). Let the points be P1,P2,...,Pk (k<= 2*n). Order the edges of the polygon in a clockwise direction and let the edge containing P1 be edge number 1 (E1) and let i1=1,i2,i3,...,ik be the indices of the edges containing points P1,P2,...,Pk. Start with P1 and check whether the circle arc between P1 and P2 is inside or outside your polygon. One way to do this is to take the middle of this arc and the circle's center and count how many edges the straight line connecting this point intersects. If the number is even the arc is inside the polygon. If it is odd it is outside. Let assume that the arc is inside. Then the first segment of the boundary of your region is the arc between P1 and P2. The second one consists of the part of edge Ei2 P2 to the vertex + edge E(i2+1),.. + part of edge E(i3) before point P3 (note that it may happen that i2 = i3). Next segment is the arc between P3 and P4, etc. Finally add the polygon edges between Pk and P1. Since the integral of xdy along a circle arc and along a straight line segment can be easily computed (analytically) you get the exact area. If the number of intersection points is 0 then either the polygon is inside the circle and the areas is the area of the polygon or the circle is inside the polygon and the area is that of the circle or they are fully separated and the area is 0 - it is not difficult to check what is your case.
Regards, Moshe. --- Eric Archer <[EMAIL PROTECTED]> wrote: > R-listers, > > Given a polygon and a circle defined by its center > coordinates and a > radius, I would like to calculate the area of > overlap. I know that I > can create a polygon from the circle and then use > available packages to > get the area of the intersection. However, because > the polygon is of a > fixed size and I will be doing this for circles of > varying sizes, I'm > concerned about maintaining the appropriate amount > of resolution with > larger circles. If there was already a package > that did the above > calculation without the creation of a circle polygon > and would thus give > an exact area, that would be preferred. I have > searched the archives > and have not found a solution to this particular > problem. Thanks! > > Cheers, > eric > > -- > > Eric Archer, Ph.D. > NOAA-SWFSC > 8604 La Jolla Shores Dr. > La Jolla, CA 92037 > 858-546-7121,7003(FAX) > [EMAIL PROTECTED] > http://swfsc.noaa.gov/prd-etp.aspx > > "Innocence about Science is the worst crime today." > - Sir Charles Percy Snow > > > "Lighthouses are more helpful than churches." > - Benjamin Franklin > > "...but I'll take a GPS over either one." > - John C. "Craig" George > > > > ______________________________________________ > R-help@r-project.org mailing list > https://stat.ethz.ch/mailman/listinfo/r-help > PLEASE do read the posting guide > http://www.R-project.org/posting-guide.html > and provide commented, minimal, self-contained, > reproducible code. > ______________________________________________ R-help@r-project.org mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code.
