DSeal@acorn.co.uk (10/17/89)
To determine the area of an arbitrary "polygon", the sides of which may be
straight line segments, arcs or other curves, I would suggest the following
approach:
Suppose that the vertices are (x(i),y(i)), i=1 to N, and set x(0)=x(N),
y(0)=y(N). Express the curve from (x(i-1),y(i-1)) to (x(i),y(i)) either in
non-parametric form
y=f_i(x), for x running from x(i-1) to x(i),
or in parametric form
x=g_i(t), y=h_i(t), for t running from 0 to 1,
whichever seems suitable for the type of curve. (If a non-parametric form
seems suitable, it may be necessary to split the curves at vertical tangents
to make certain the non-parametric form exists for each curve.)
The idea is to sum the signed areas of "quadrilaterals" of the following
form:
(x(i-1),y(i-1))
*
|\
| -_ (x(i),y(i))
| --__ _*
| ----______---- |
| |
| |
| |
*----------------------*
(x(i-1),0) (x(i),0)
E.g. Consider the diagram:
__-------__
A * * B
|\ /|
| \ / |
| \ / |
| \ / |
| \ / |
| C * |
| | |
| | |
| | |
D *-----*-----* E
F
The area of the polygon ABC is equal to area(ABED)-area(BCFE)-area(CADF).
(The signs are determined by whether X increases or decreases as we go along
the edge.)
The signed areas required are in fact simply integrals. In the case of a
non-parametric curve, the integral required is:
/ x(i)
|
| f_i(x)dx.
|
/ x=x(i-1)
In the case of a parametric curve, it is:
/ 1 / 1
| |
| ydx = | h_i(t)g_i'(t)dt,
| |
/ t=0 / t=0
where g_i'(t) is the derivative of g_i(t).
I can't be much more specific than this without knowing what exactly the
curves used are and how they are specified. A simple example is when the
curve is simply a straight line segment. This is most easily dealt with
using a parametric form, namely x=g_i(t)=(1-t)*x(i-1)+t*x(i),
y=h_i(t)=(1-t)*y(i-1)+t*y(i). This gives g_i'(t)=x(i)-x(i-1), and hence a
signed area of
/ 1
|
| ((1-t)*y(i-1)+t*y(i))*(x(i)-x(i-1))dt
|
/ t=0
/ 1
|
= (x(i)-x(i-1)) * | (y(i-1) + (y(i)-y(i-1))*t)dt
|
/ t=0
[ ] 1
= (x(i)-x(i-1)) * [ (y(i-1)*t + (y(i)-y(i-1))*t*t/2) ]
[ ] t=0
= (x(i)-x(i-1)) * ( y(i-1) + (y(i)-y(i-1))/2 )
= (x(i)-x(i-1)) * (y(i-1)+y(i))/2.
This gives the area of a straight-edged polygon as:
SUM (i=1..N) (x(i)-x(i-1))*(y(i)+y(i-1))/2
= SUM (i=1..N) (x(i)*y(i-1)-x(i-1)*y(i))/2
(by cancelling out the +x(i)*y(i) from each term with the
-x((i+1)-1)*y((i+1)-1) from the next term).
These are of course the formulae that various people have given before.
If the edges are more complicated curves, the mathematics becomes
correspondingly more complicated. For instance, if the edge is a Bezier
curve, g_i and h_i will both be third degree polynomials and so the function
h_i(t)g_i'(t) will be a fifth degree polynomial. This is essentially easy,
but involves more mathematics than I want to type!
I have not worked out the details of circular arcs - the best way to do the
integration may well depend on how you are specifying the arc. But the
technique above should work.
Finally, areas obtained by this technique will have the same properties as
those given by the SUM (i=1..N) (x(i)*y(i-1)-x(i-1)*y(i))/2 formula. E.g.
they are positive if the polygon is traversed clockwise, negative if
anti-clockwise; for self-intersecting polygons, they will be SUM (components
of polygon) ((area of component)*(winding number of polygon around
component)).
David Seal
Acorn Computers Ltd.,
Fulbourn Road,
Cambridge CB1 4JN,
U.K.
<insert standard disclaimers>