From: luis@rice.edu (luis soltero)
Subject: Need help w/ polygon wire frame representation algorithm
Organization: Rice University
Date: Tue, 6 Oct 1992 18:31:39 GMT


i am posting this for a friend.  please send e-mail replies to me since
i do not regularly follow this group.  

thanks,

--luis

From draggon@pauling.che.uc.edu  Mon Oct  5 17:23:14 1992
Received: from moe.rice.edu by dingo.rice.edu via SMTP (920110.SGI/)
        (for luis) id AA15103; Mon, 5 Oct 92 17:23:14 -0500
Received: from pauling.che.uc.edu by moe.rice.edu (AA13361); Mon, 5 Oct 92 17:23:08 CDT
Received: by pauling.che.uc.edu id AA03002
  (5.65c/IDA-1.4.4 for rice.edu!luis); Mon, 5 Oct 1992 18:22:09 -0400
Date: Mon, 5 Oct 1992 18:22:09 -0400
From: Wendell Morris <draggon@pauling.che.uc.edu>
Message-Id: <199210052222.AA03002@pauling.che.uc.edu>
To: luis@rice.edu
Status: RO

Hi Luis,

Here is a basic description of the problem we need to solve.


------------------------------------------------------

We have an application which allows a user to create
arbitrary planar polygons, both convex and concave.  We need
to be able to export these shapes to AutoCAD (via DXF) as 3D
FACES.  If the polygon has 3 or 4 vertices, this is obviously
no problem.  For more than 4 vertices, however, we need to
first break the polygon into triangles (triangulate it?) so
that AutoCAD can understand it as a face (instead of just a
polyline).

The basic algorithm we have come up with is to pick any vertex
and attach a line segment from that vertex to a vertex which
is distance 2 away.  If this line segment lies completely
within the bounds of the polygon, you chop off the resulting
triangle and repeat the process.  If it's NOT completely
within the poylgon (or if it's colinear to an edge of the
polygon), you step to the next vertex and start the process
again.  Eventually you will be left with 3 vertices that form
the final triangle.

So, here's the big question : Does anyone out there have any
code that we could use to do this?  The real problem lies in
detecting whether or not the line segment lies completely
within the polygon.  I'm sure SOMEBODY must have already
solved this problem, and I absolutely hate the idea of
reinventing the entire thing from scratch.

I would also greatly appreciate any recommendations for books
that contain samples of working code to solve this and other
similar geometry problems.  I'm not really interested in books
presenting the theories, as I can probably get that from
almost any good reference.  I'd much rather have a book that
just gives me the answers in the form of working code
fragments.

Thanks in advance for your help.


-----------------------------------------------------------

Luis, you can post this under your name or mine, but please
have the responses come to you.  My danged mail is way too
unreliable.

Thanks for helping out.


				---   draggon

--
======================================+=======================================
Luis R. Soltero, Ph.D.                |    InterNet:  luis@rice.edu 
Keck Center for Computational Biology |    UucpNet:   luis@rice.UUCP
Rice University, P.O. Box 1892        |    PhoneNet:  (713) 285-5364 
Houston, Texas 77251                  |    FaxNet:    (713) 285-5154
======================================+=======================================