I have a non regular polygon drawn in a CAD program called AutoCAD.
Can anyone tell me how I can divide this polygon into say 4 equal
areas? Is there a ready made autolisp or VB program available? If not
what steps should I follow to achieve the division. I already know the
grid method to do this and it is really tedious to do. The reason I
want to do this is we have to divide a building floor plan into equal
areas for air conditioning zones. Our current method is to make areas
approximatedly equal by separately adding up each room area. I am
curious if there is an exact mathematical method that is implementable
in AutoCAD.

---

Request for Question Clarification by mathtalk-ga on 26 Dec 2002 15:45 PST

Hi, pmathews-ga:

I'm wondering if the desired answer should emphasize the algorithm
(for subdividing the polygon into equal areas) or the programming in
AutoCAD?

There is an efficient algorithm for doing this exactly (not a "grid
method").  Naturally any exact method must allow for the possibility
of dividing at least one room into separate subregions.

regards, mathtalk-ga

---

Clarification of Question by pmathews-ga on 26 Dec 2002 23:49 PST

Hi mathtalk-ga,

Thanks for looking into the problem. I am really interested in a
simple algorithm to solve the problem. I could probably do the
programming part myself if the algorithm did not involve very high
level math concepts.

Regarding the subdividing of the room to get equal areas, I could live
with that.

Thanks once again and looking forward to reading the algorithm

---

Request for Question Clarification by mathtalk-ga on 27 Dec 2002 08:19 PST

I have one other concern, and that is that your floor plan is not a
(single) polygon.  A polygon can have only one boundary.  If your
floor plan has interior "holes" in it, then it is not strictly
speaking a polygon.

regards, mathtalk-ga

---

Clarification of Question by pmathews-ga on 28 Dec 2002 11:39 PST

Don't worry about interior holes in the polygon. But please do
remember that what I mean by a polygon may have arcs as edges. Some
buildings do have curved edges. Also my polygons can have between 20
and 30 edges.
A rough stick diagram of a very simple polygon is below. 

|----------------|   |---|
|                |   |   |
|      |------\  |---|  /
|      |       \       /
|------|        \-----/

Regards
pmathews-ga

regards
pmathews-ga

Hi, pmathews-ga:

My write-up takes the discussion farther away from AutoCAD, but at
least it grounds the algorithm in the referenced literature.  I'd be
happy to  assist you with development issues as you move forward.

Let's begin with a statement of the problem which you wished to solve.
 A simply connected plane figure Q is defined by a sequence of
vertices (N > 2):

(x_1,y_1), (x_2,y_2), . . . , (x_N,y_N)

which are connected in a simple closed "curve" surrounding Q by edges
that are either circular arcs or straight line segments:

e_1 connects (x_1,y_1) to (x_2,y_2)
e_2 connects (x_2,y_2) to (x_3,y_3)
. . .
e_N connects (x_N,y_N) to (x_1,y_1)

Let us also assume that the result of replacing these edges by all
straight line segments {f_i} connecting the corresponding vertices
produces a simple polygon P.  [This can always be arranged by suitable
introduction of extra vertices on the boundary of Q, so that the edges
e_i and f_i are uniformly and sufficiently close.]

The problem of subdividing P or even Q into a certain number k of
equal area simply connected pieces is not difficult, and in fact can
be done in linear time, O(N).  What is difficult is to do the
subdivision optimally, by which we mean so that the total length of
cuts (boundaries between subdivisions) is minimized.

The subdivision of a general polygon P into k equal area (simply
connected) pieces is the subject of this paper, presented at the 12th
Canadian Conference on Computational Geometry (CCCG 2000):

[The Area Partitioning Problem by Hannah Bast and Susan Hert]
www.cs.unb.ca/conf/cccg/eProceedings/6.ps.gz

Note: Although this file would appear to be gzipped (by the extension
.gz), in fact it is not compressed.  One can download the file, and
view it with GhostView or other Postscript viewing software once the
offending extra filename extension is removed (just "rename" the file
during or after downloading).  Let me know if you need help locating
such software.

Their conclusion (Section 2) is that the minimum cut problem for
general P, even for two pieces, is NP hard.  They further claim to
prove that even an approximate solution within some factor independent
of the shape of P is NP hard.

However they "then present a simple" O(kN)-time "algorithm that
produces non-optimal, but often quite reasonable, area partitionings
for arbitrary polygons."  (Section 3)

Minimizing the total length of boundaries between subregions has a
natural application to the problem of air temperature controls.  If a
temperature gradient between two adjacent zones were desired,
shortening the boundary length between two zones would tend to reduce
the energy cost to maintain that gradient.  See the references of the
above paper for early research that employs this criterion.  In
particular it motivates the use of straight cuts (between points on
the input polygon's boundary).

The "fast" algorithm devised by Bast and Hert is similar in outline to
the one I sketched in my comments.  One begins with a decomposition of
the polygon P into convex pieces (such as the triangulations I
mentioned).  These pieces are then merged to form an increasingly
larger connected subregion (without disconnecting the remaining
portion), until a point at which any further merger would create an
area greater than sought.  The algorithm then switches to a subgoal of
dividing a convex piece (of the overall non-convex polygon P) into
portions that will "become parts of separate partition polygons" using
a "sweep-line" procedure.

The authors implemented their algorithm using the CGAL Software
Library:

[Computational Geometry Algorithms Library]
http://www.cgal.org/

and present some intriguing illustrations of their results.

It seems to me that if the curved edges of Q are outwardly curved, so
that the triangulation of P effectively also decomposes Q into convex
pieces (using the same vertices), then the algorithm given by Bast and
Hert should apply with only minor emendation.  The area calculation of
such pieces of Q, having one or two curved boundaries, is tractable
assuming that the curves are circular one of known radius. 
Furthermore the "sweep-line" algorithm (which, as in the outline I
gave, may require subdivision of more than one convex piece) appears
to require only the ability to find endpoints along a boundary which
exactly "interpolate" a given area.  Although not as trivial as with
triangles' flat sides, the circular arcs can in principle be treated
numerically to obtain the desired area interpolation.

Additional Link of Interest

[Programming and Problem Solving: A Transcript of the Spring 1999
Class]
(Columbia Univ. educational approach, cf. Project 4: Egalitarian
Island)
http://www.cs.columbia.edu/~library/TR-repository/reports/reports-1999/cucs-018-99.pdf

regards, mathtalk-ga

Search Strategy

[Keywords: polygon "each area pieces"]
://www.google.com/search?hl=en&ie=UTF-8&oe=UTF-8&q=polygon+%22equal+area+pieces%22&btnG=Google+Search

Very detailed and carefully written answer.

Hi, pmathews-ga:

Well, I'm afraid I'll have to pass on polygons with "curved edges". 
Non-convex polygons, yes, but all edges should be line segments in my
definition.  Curves would have to be approximated by polylines.

Here's an outline of material you need to handle true polygons.  The
simplest element is calculating the area of a polygon.  You need to
have the sequence of the N vertices travelling counterclockwise around
the boundary:

(x_1,y_1),(x_2,y_2), . . . ,(x_N,y_N)

Area = (1/2) SUM y_i * (x_{i-1} - x_{i+1}) FOR i = 1 to N

where the subscripts of x_{.} are interpreted mod N as necessary.

http://www.math.niu.edu/~rusin/known-math/95/greens

Note that this formula assumes a single outer boundary, so no interior
holes are allowed (although one could easily generalize by subtracting
the areas of any interior holes from the area encompassed by the outer
boundary).

The second element I want to call your attention to is triangulation
of polygons.  This has been an area of active research in
computational geometry.  One good site is this:

[Fast Industrial Strength Triangulation (FIST)]
http://www.cosy.sbg.ac.at/~held/projects/triang/triang.html

but check out these two other sites:

[Fast Polygon Triangulation by Seidel's Algorithm]
http://www.cs.unc.edu/~dm/CODE/GEM/chapter.html

[Computational Geometery Teaching Links: Triangulation]
http://cgm.cs.mcgill.ca/~godfried/teaching/cg-web.html#triangulation

In fact you can find code for doing triangulation of a polygon in
AutoLisp:

http://xarch.tu-graz.ac.at/autocad/code/mecsolpr/triangulate.lsp

and more up to date stuff under "Geometry" here:

http://xarch.tu-graz.ac.at/autocad/ads/#geometry

So suppose we have a (simply connected) polygonal region of known
area.  Dividing it into N equal parts can be reduced to a succession
of dividing the region into two simply connected regions (one of which
has an area of 1/N times the area of the original region).  For that
reason we will focus on the problem of finding how to divide a (simply
connected) polygonal region into two parts, having a certain area for
one of the two parts (and having both subregions be simply connected).
 For example, in your original question you asked about dividing an
area into four equal parts.  One can divide the original area into two
equal parts, and then divide each of these in two parts to get
"fourths".

Let me back up and quote some properties of a "good" polygonal
triangulation from the "FIST" page cited earlier:

 - every edge of every input polygon belongs to a triangle, 
 - every edge of a triangle is shared with another triangle or belongs
to an input polygon,
 - every vertex of a triangle is a vertex of an input polygon, 
 - the adjacency graph of the triangles is connected. 

These properties allow us to classify the triangle in a triangulation
according to the number of sides (up to 3, though obviously that is a
very special case) which are edges of the polygon also.

Every side that is not a polygon edge connects two vertices on the
boundary, and thus every such "extra edge" constitutes a separation of
the original polygon into two simply connected subregions.  In the
simplest case we simply check how big these two subregions are.  If we
find a triangle with one side that is an original edge, and two sides
that are "extra" internal edges, so that one part "outside" the
triangle is not quite big enough, but adding the entire triangle makes
a subregion that is too big, then we interpolate a new dividing line
between the two internal edges to get a subregion of exactly the right
size.

The difficulty occurs when we have triangles with no sides that are
edges of original polygon.  That is a problem because in this case
removing that entire triangle would separate the rest of the polygon
into three, rather than two, subregions.  Consider this example, a "Y"
shaped polygon that we would like to divide into two equal pieces:

 ------     ------
 \     \   /     /
  \     \ /     /
   \     V     /
    \         /
     \       /
      |     |
      |     |
      |     |
      |     |
      -------

Let us say, for the sake of argument, that each of the three halls
leading off the main juncture have equal areas, and that the area of
the main juncture is small in comparison with that of each hall.  Then
to get half of the total area, one must combine portions of at least
two halls (but all of any two halls would be too much.  Basically the
most natural and symmetric division will require us to split one hall
down the middle, perhaps like this:

 ------     ------
 \     \   /     /
  \     \ /     /
   \     V     /
    \    :    /
     \   :   /
      |  :  |
      |  :  |
      |  :  |
      |  :  |
      -------

in order to get two equal pieces.  So as far as dividing polygons into
two subregions go, we could elaborate this example into an algorithm. 
I.e., if there are no triangles with zero external edges, then pick a
triangle with two external edges (there must be one) and start adding
adjacent triangles to it to form an increasing subregion until the
desired region is obtained (possibly by breaking the last triangle
adjoined into two "interpolated" parts as described previously).  If
there are triangles with no external edges, then when one is
encountered in the process of combining adjacent triangles, we check
the respective sizes of the "ears" (halls) across each of the three
sides of such a triangle.  If necessary, one of these three halls will
then have to be subdivided "down the middle" to obtain simply
connected (but still "gerrymandered") subregions of the appropriate
sizes.

Search Strategy

Keywords: "area of polygon"
://www.google.com/search?hl=en&lr=&ie=UTF-8&oe=UTF-8&q=%22area+of+polygon%22&btnG=Google+Search

Keywords: polygon triangulation
://www.google.com/search?hl=en&lr=&ie=UTF-8&oe=UTF-8&q=polygon+triangulation&btnG=Google+Search

Keywords: polygon triangulation "Visual Lisp"
://www.google.com/search?hl=en&lr=&ie=UTF-8&oe=UTF-8&q=polygon+triangulation+%22Visual+Lisp%22&btnG=Google+Search

Hi, Mathtalk-ga:

You have really done a lot of work it seems. I have yet to assimilate
the material.

Thank you

In "assimilating" the concepts, it might be helpful to think through
the special case of a convex polygon.

A figure is convex if and only if any two points inside the figure are
connected by a line segment that also lies inside the figure.  (So
your figure with dips and V's in outer boundary is not convex.)

A convex polygon can be triangulated by picking one vertex X and
drawing the line segments that connect it to each of the other
vertices.  Of course two of those line segments are already edges of
the original polygon.  Every triangle now has at least one side that
is an (external) edge of the original polygon.

Begin with either the left or right neighboring edge of the fixed
vertex X, and use the succession of triangles starting with the one
that contains that edge.  Sweep across the polygon until the desired
fraction of the polygon's area has been subsumed.

-- mathtalk-ga

Hi mathtalk-ga,

Thanks a lot for the effort in finding an approach to the solution. 
You can submit your comment as an answer and I will rate it for
payment. I could probably find something to convert curved edges into
smaller straight edges.

Hi, pmathews:

Thanks, a good rating would be helpful right now!  Give me a few hours
to polish the content; I'm not sure how much shorter I can make it,
but I'm sure I can tighten up the flow considerably.

regards, mathtalk