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 <Eric.Archer at noaa.gov> 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)
> eric.archer at noaa.gov
> 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 at 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.
>