chet@netcom.netcom.COM (Eric Chet) (05/06/91)
Hello
I have a polygon with N vertices. I first need to test if it's concave
or convex. If concave split it into a minimum number of convex polygons.
Any ideas.
Thank you in advance, chet@netcom.comlambert@silver.cs.umanitoba.ca (Tim Lambert) (05/08/91)
>>>>> On 6 May 91 07:14:32 GMT, chet@netcom.netcom.COM (Eric Chet) said: > I have a polygon with N vertices. I first need to test if it's concave > or convex. If concave split it into a minimum number of convex polygons. You can test if a corner is convex by calculating the signed area of the triangle formed by the three vertices that define the corner. Splitting a polygon into a minimum number of convex polygons is quite tricky: See J. M. Kiel "Decomposing a Polygon into simpler components" SIAM J on Computing 14 799--817 (1985)
dfr@usna.NAVY.MIL (Prof. David F. Rogers) (05/08/91)
In article <LAMBERT.91May7190825@silver.cs.umanitoba.ca> lambert@silver.cs.umanitoba.ca (Tim Lambert) writes:
!!!!!! On 6 May 91 07:14:32 GMT, chet@netcom.netcom.COM (Eric Chet) said:
!! I have a polygon with N vertices. I first need to test if it's concave
!! or convex. If concave split it into a minimum number of convex polygons.
!
!You can test if a corner is convex by calculating the signed area of
!the triangle formed by the three vertices that define the corner.
!
!Splitting a polygon into a minimum number of convex polygons is quite
!tricky: See
!J. M. Kiel "Decomposing a Polygon into simpler components" SIAM J on
!Computing 14 799--817 (1985)
One technique of implimenting this technique is described in
Procedural Elements for Computer Graphics by Rogers (see freq. asked
questions). A fall out of this implementation is a technique for
spliting the concave polygon into convex parts. It does not yield
an optimal split in the sense of the minimum number of convex polygons
but it will split the concave polygon into convex parts. Getting the
minimum number of convex parts is the really tricky part. But in
some applications this is not critical.
Dave Rogerslambert@silver.cs.umanitoba.ca (Tim Lambert) (05/09/91)
>>>>> On 8 May 91 13:38:07 GMT, dfr@usna.NAVY.MIL (Prof. David F. Rogers) said: > !!!!!! On 6 May 91 07:14:32 GMT, chet@netcom.netcom.COM (Eric Chet) said: > !! I have a polygon [that I want to split] into a minimum > !! number of convex polygons. > ... Procedural Elements for Computer Graphics by Rogers (see freq. > asked questions) [contains a] technique for spliting the concave > polygon into convex parts. It does not yield an optimal split in the > sense of the minimum number of convex polygons ... One more point: the technique described in Rogers introduces some new vertices at points where the extension of edges into the interior of the polygon intersects another edge. (These are known as Steiner points.) Depending on your application, this might not be desirable. (For example, if the vertices are expressed in integer coordinates, the Steiner points probably will not be.) A simple technique for a (non-minimal) split is to add diagonals between concave vertices. (You have to reject diagonals that intersect polygon edges.) Tim
dfr@usna.NAVY.MIL (Prof. David F. Rogers) (05/12/91)
In article <LAMBERT.91May9125404@silver.cs.umanitoba.ca> lambert@silver.cs.umanitoba.ca (Tim Lambert) writes:
!!!!!! On 8 May 91 13:38:07 GMT, dfr@usna.NAVY.MIL (Prof. David F. Rogers) said:
!
!! !!!!!! On 6 May 91 07:14:32 GMT, chet@netcom.netcom.COM (Eric Chet) said:
!! !! I have a polygon [that I want to split] into a minimum
!! !! number of convex polygons.
!
!! ... Procedural Elements for Computer Graphics by Rogers (see freq.
!! asked questions) [contains a] technique for spliting the concave
!! polygon into convex parts. It does not yield an optimal split in the
!! sense of the minimum number of convex polygons ...
!
!One more point: the technique described in Rogers introduces some new
!vertices at points where the extension of edges into the interior of
!the polygon intersects another edge. (These are known as Steiner
!points.) Depending on your application, this might not be desirable.
!(For example, if the vertices are expressed in integer coordinates,
!the Steiner points probably will not be.)
!
!A simple technique for a (non-minimal) split is to add diagonals
!between concave vertices. (You have to reject diagonals that
!intersect polygon edges.)
The algorithm in Procedural Elements can be implimented such that
the Steiner points are eliminated. When a concave polygon is found
one takes the line from the vertex on the axis to the first vertex
above the axis to split off the polygonal piece. Note it is possible
that this split off piece may be concave so it must also be investigated.
Dave Rogers