algorithm1.html 100644 25565 25565 15077 6443537717 12025 0 ustar garton
An O(kn) Time Algorithm for Finding an Ear
A very simple algorithm exists for finding an ear in the simple polygon P :
Function FindEar(P)
1. i = 0
2. ear not found = true
3. while ear not found
4. if
pi is
convex then
5. if triangle formed by
pi-1, pi, and
pi+1
contains no
concave vertex then
6. ear not found =
false
7. if ear not found then
8. i = i + 1
9. return pi
End FindEar
By the Two-Ears Theorem, simple polygon P has at least 2 ears if the number of vertices is > 3. If the number of vertices is 3, then P is a triangle and forms 1 ear. By the definition of a polygon, there is always at least 1 ear in P for the algorithm to find.
To complete the proof of correctness, it suffices to prove the following lemma :
Lemma: If a convex vertex pi is not an ear, then the triangle formed by pi-1, pi, and pi+1 contains a concave vertex.
Proof: If pi is not an ear, then the triangle formed by pi-1, pi, and pi+1 contains a vertex. Let pj be the vertex in the interior of this triangle (pi-1, pi, pi+1) such that the line L through pj and parallel to the line through pi-1 and pi+1 is as close to pi as possible. Let a and b be the points of intersection of line L with the polygon edges (pi, pi+1) and (pi-1, pi) respectively. Triangle (a, pi, b) has no vertices in its interior and lies entirely inside P. Vertices pj-1 and pj+1 must lie on the opposite side of line L, so pj is a concave vertex.
Q.E.D.
The proof of correctness for algorithm FindEar is complete.Q.E.D.
Lines 1 and 2 of FindEar run in constant time. The loop in line 3 is executed at most n - 2 times, which occurs when P has only 2 ears and is similar to this :
The start vertex for FindEar is p0. If the vertices are sorted in clockwise order, the ear shown in yellow is the first ear found. The number of vertices checked in order to find this ear is n - 2 (where n is the number of vertices in P).
Line 4 runs in constant time. Line 5 may require O(k) time where k - 1 is the number of concave vertices in P since it is possible that all concave vertices are checked for being in triangle (pi-1, pi, pi+1). Lines 6, 7, 8, and 9 all run in constant time.
So, since line 5 may be executed in time proportional to n, algorithm FindEar runs in O(kn) time. However, since k - 1 is the number of concave vertices, the algorithm can be as bad as O(n2).
This page was last updated on Wednesday, December 10th, 1997.
© 1997 Ian Inc.
algorithm2.html 100644 25565 25565 31267 6443541737 12022 0 ustar gartonAn O(n) Time Algorithm for Finding an Ear
A recursive algorithm was developed by Hossam ElGindy at the University of Newcastle, Hazel Everett at the Université du Québec, and Godfried T. Toussaint at McGill University [1].
The input is a good sub-polygon GSP and a vertex pi. Initially, the function FindAnEar is called with the simple polygon P and any vertex of P.
Function FindAnEar(GSP, pi)
1. if pi is an ear then
2. return pi
3. Find a vertex pj such that
(pi, pj) is a diagonal of
GSP.
Let GSP' be the good sub-polygon of GSP
formed by
(pi, pj).
Re-label the vertices of
GSP' so that pi = p0 and
pj = pk-1
(or pj =
p0 and pi = pk-1
as appropriate) where k is the number
of vertices of GSP'.
4. FindAnEar(GSP', floor(k/2))
End FindAnEar
The correctness of the algorithm follows from Lemmas 1, 2, and 3.
Lemma 1: A good sub-polygon has at least one proper ear.
Proof: Let (pi, pj) be the
cutting edge of GSP. By the
Two-Ears Theorem GSP has at
least two non-overlapping ears. Vertices pi and
pj cannot be the only ears of GSP since these
would overlap. Thus some other vertex of GSP is an ear and it is
a proper ear.
Q.E.D.
Lemma 2: A diagonal of a good sub-polygon GSP splits GSP into one good sub-polygon and one sub-polygon that is not good.
Proof: GSP contains exactly one edge, the cutting edge, which is not an edge of P. The cutting edge is entirely contained in one of the sub-polygons formed by the diagonal. Then the other sub-polygon is a good sub-polygon since it consists of edges of P and the diagonal which becomes its cutting edge.
Q.E.D.
Lemma 3: If vertex pi is not an ear then there exists a vertex pj such that (pi, pj) is a diagonal of P.
Proof: Given a vertex pi which is not an ear we
will show how to find a vertex pj such that
(pi, pj) is a diagonal. Construct a
ray, ray(pi), at pi that
bisects the interior of angle (pi-1,
pi, pi+1). Find the first
intersection point of ray(pi) with the boundary
of P. Note that this is done simply by testing each edge of the
polygon for intersection with ray(pi). Let
y be the intersection point on edge (pk,
pk+1). Point y must exist and y <>
pi-1 or pi+1. Note that the
line segment (pi, y) lies entirely inside P.
Thus if y is a vertex then (pi, y) is a
diagonal. Suppose y is not a vertex. Then pk+1
and pi-1 lie in one of the half-planes defined by
ray(pi), and pk and
pi+1 lie in the other. We will show that if triangle
(pi, y, pk+1) does not
contain a vertex pj such that (pi,
pj) is a diagonal of P then triangle
(pi, y, pk) does.
Q.E.D.
Q.E.D.
Line 1 of FindAnEar can be done in O(n) time where n
is the number of vertices in GSP. Line 2 takes constant time.
Line 3 can be done in O(n) time as well.
On the first two calls to FindAnEar, GSP has O(n)
vertices. Consider any subsequent call. Let k be the number of
vertices in GSP. We have i = floor(k/2) and
(p0, pk-1) the cutting edge of
GSP. Consider line 3. If 0 <= j <= i-2 then
GSP' = (pj, pj+1, ...,
pi). Otherwise, i+2 <= j <= k-1
and GSP' = (pi, pi+1, ...,
pj). In either case, GSP' contains no more
than floor(k/2) + 1 vertices.
This page was last updated on Wednesday, December 10th, 1997.
© 1997 Ian Inc.
algorithm2_proof3.gif 100644 25565 25565 6053 6443431336 13057 0 ustar garton GIF87af @, f ڋH扦ʶL ĢL*̦ JԪjܮN (8HXhx)9IYiy 0zhjʊHj*;;{Wۧj\G\LkL|4ʌ1}m<ݭ|]]Nd 0>n^3^*/^ϼ|/@~[nBhoD}m+rxȑB<$ʕT|̙3Ѽ &Ν+tibX@D- `hѥ&e uSQCԪ֦X]n)կKf c1yTۃ-._mzm״v[ki}+^=(f\Ia|xKaQ`ޥy2$C$yʤά:4F:vRִn[n\EF\ldO}9uagNu縿GuBώw=eUe_{~U SDMrكXM xLm_|py ¨Bj$~gWQ_X/U%N=JQ6i#:K"th`O9zI@~X%C2)R[QDPWΜf٦ZGEY(d/BQccPڙ&Gzfu#դ;"Jv ۟b̖ѠBj$(무Z)>Jszb:`m+ تAZ+۶Ű ηV5ߊ{4kܺyb!,Hjvs*pO,o1(R',唱s|CldaJǫFhM"[l%:8.ٲ̇ZJ+89D4 sE~L{@;Su a5d_KvW