Convex Partitioning of a Polygon into Smaller Number of Pieces with Lowest Memory Consumption

Convex Partitioning of a Polygon
into Smaller Number of Pieces
with Lowest Memory Consumption
Kasun Ranga Wijeweera
(krw19870829@gmail.com)
1

What is a Polygon?
• Let v0, v1, v2…, vn-1 be n points in the plane.
• Let e0 = v0v1, e1 = v1v2…, ei = vivi+1…, en-1 = vn-1v0 be n
segments connecting the points.
• These segments bound a polygon if and only if
1. The intersection of each pair of segments adjacent in the
cyclic ordering is the single point shared between them: ei ∩
ei+1 = vi+1, for all i = 0…, n – 1.
2. Nonadjacent segments do not intersect: ei ∩ ej = Ф, for all j
≠ i + 1.
3. None of three consecutive vertices are collinear.
Note that all index arithmetic are modulo n.
3

What is a Convex Polygon?
• A polygon P is called convex if x in P and y in P implies that
the segment xy is a subset of P.
• A vertex is called reflex if its internal angle is greater than π.
• Any polygon with a reflex vertex is not convex.
6

Triangulation of a Polygon
• Definition: The decomposition of a polygon into a set of non
overlapping triangles.
• Example:
7

Convex Partitioning of a Polygon
• Definition: The decomposition of a polygon into a set of non
overlapping convex pieces.
• Example:
8

Convex Partitioning of a Polygon…
• A partition into triangles is a special case of a partition into
convex polygons.
• However, triangulation is by no means optimal in the number
of convex pieces.
9

Research Problem
• Hertel Mehlhorn algorithm can partition a polygon into exact
convex pieces in O (n2) time and O (n2) space.
• Even though there are algorithms which produce smaller
number of convex pieces than the HM algorithm, they are
either less efficient or fail to produce exact convex pieces.
• A convex partitioning algorithm is proposed which produces
exact convex pieces in O (n3) time and O (n2) space.
• The proposed algorithm produces smaller number of convex
pieces than the HM algorithm and it is more efficient than the
other algorithms which produce exact convex pieces.
10

Convex Partitioning Algorithms
• Hertel Mehlhorn (1983): O (n2)
• Greene (1983): O (n4)
• Keil (1985): O (n3 log n)
• Chazelle (1985): O (n3)
• Lien et al. (2006): O (nr), r reflex
• Hongguang et al. (2015): O (nr), r reflex
12

A Diagonal of a Polygon
• If the intersection of line segment AB with ∂P is exactly the
set {A, B} and the line segment AB is nowhere exterior to the
polygon P then the line segment is called a diagonal of the
polygon.
13

Hertel Mehlhorn Algorithm
• Start with a triangulation of P. Remove an inessential
diagonal; repeat.
• This process can be done in O (n) time.
14

Related Research Paper
K. R. Wijeweera, S. R. Kodituwakku (2017), Convex
Partitioning of a Polygon into Smaller Number of Pieces
with Lowest Memory Consumption, Ceylon Journal of
Science, Volume 46 (Issue 1), pp. 55-66.
16

Representation of the Polygon
• The variable points stores the number of vertices of the
polygon.
• The coordinates of the vertices of the polygon are stored
using two arrays x and y.
• Then (x[i], y[i]) denotes the ith vertex of the polygon where i
= 0, 1…, (points - 1).
17

Finding the Lowest Vertex of the Polygon
• The function lv returns the index of the lowest vertex of the
polygon.
• The index of one particular vertex should be returned when
there are several lowest vertices.
• Lemma: Lowest vertex is always convex.
18

An Important Mathematical Result
• The vertices of the triangle: P1 (x1, y1), P2 (x2, y2), P3 (x3, y3).
• Let t = x1 * (y2 – y3) + x2 * (y3 – y1) + x3 * (y1 – y2).
• t = 0 ↔ (P1, P2, P3) are collinear.
• t > 0 ↔ (P1, P2, P3) are in anticlockwise order.
• t < 0 ↔ (P1, P2, P3) are in clockwise order.
19
t > 0 t < 0

Calculating the Sign of a Vertex
• The function tv returns the sign of value t.
• The function getWise returns the sign of the vertex by
considering its two neighboring vertices.
20

Finding the Reflex Vertices of the Polygon
• All the reflex vertices of the polygon should be found.
• The array reflex is used to store the state of each vertex.
• Initially each element of the array reflex is zero.
• The function setReflex sets reflex[i] to 1 if ith vertex is reflex.
• The variable min stores the index of the lowest vertex.
• If getWise(i) * getWise(min) < 0 then the ith vertex is reflex.
21

Two Points with respect to a Line Segment
• Suppose L is a line segment with P1 (x1, y1) and P2 (x2, y2) as
end points.
• Then P3 (x3, y3) and P4 (x4, y4) are the given two points.
• The function isTwoSides returns 1 if P3 and P4 are situated in
two sides of the extended line segment L. Otherwise it
returns 0.
• The function tv is used for this purpose.
22

Two Points with respect to a Line Segment…
• If tv{P1, P2, P3} * tv{P1, P2, P4} < 0  P3, P4 are on same
side of L.
• If tv{P1, P2, P3} * tv{P1, P2, P4} > 0  P3, P4 are on opposite
sides of L.
23

Test for X-intersection of Two Line Segments
• Suppose L1 and L2 are two line segments.
• End points of L1 are P1 (x1, y1) and P2 (x2, y2).
• End points of L2 are P3 (x3, y3) and P4 (x4, y4).
• The function isIntersect returns 1 if these line segments x-
intersect else returns 0.
24
✔ ✘ ✘

Test for X-intersection of Two Line Segments…
• If following two conditions are satisfied only then L1 and L2
x-intersect.
1. P3 and P4 should be in two sides of L1.
2. P1 and P2 should be in two sides of L2.
• Therefore, isTwoSides {P1, P2, P3, P4} * isTwoSides {P3, P4,
P1, P2} = 1  the two line segments x-intersect.
25
✔ ✘ ✘

Test whether a Given Point is inside the Polygon
• The function isInside returns 1 if the point (xc, yc) is inside
the polygon. Otherwise it returns 0.
• A horizontal line is drawn beginning from the given point.
• Count the number of cuts of the polygon by the horizontal
line.
• If the number of cuts is even  The point is outside the
polygon.
• If the number of cuts is odd  The point is inside the
polygon.
26

Test whether a Given Point is inside the Polygon...
• The function pos is used to find the position of the vertex
with index k with respect to the line y = yc.
• The function pos returns 1, 0, or -1 if the point is above the
line, on the line or below the line respectively.
27

• If pos (yc, i) * pos (yc, j) < 0 then the edge {(x[i], y[i]), (x[j],
y[j])} x-intersects the horizontal line y = yc.
• The equation of the edge can be written as:
(y – y[i])/(x – x[i]) = (y[j] – y[i])/(x[j] – x[i]);
 x = x[i] + (y – y[i]) * (x[j] – x[i])/(y[j] – y[i]);
• Let (xp, yp) be the intersection point. Then by substituting y
= yc in above equation:
xp = x[i] + (yc – y[i]) * (x[j] – x[i])/(y[j] – y[i]);
28

• Initially variable p = 0.
• For each edge, x-intersecting the horizontal line such that xp
> xc, the value of p should be incremented by one.
• There are four special cases which should be considered for
incrementing the value of p in addition to x-intersections.
29

• Case 1: Line y = yc is touching a vertex.
• This case does not affect the value of p.
30

• Case 2: Line y = yc goes through a vertex.
• In this case, the value of p should be incremented by one.
31

• Case 3: Line y = yc is touching an edge.
• This case does not affect the value of p.
32

• Case 4: Line y = yc goes through an edge.
• In this case, the value of p should be incremented by one.
33

• Case 1 and Case 3 do not change the value of p.
• These two cases do not cause horizontal line to go inside or
outside the polygon.
34

• Case 2 and Case 4 increment the value of p by one.
• These two cases cause horizontal line to go inside or outside
the polygon.
35

• Case 1 and Case 2 deal with a vertex.
• Let the index of the vertex is i.
• Check the condition (y[i] = yc AND x[i] > xc).
• Then a (= i - 1) and b (= j + 1) are the indices of the two
neighboring vertices.
• If pos (a) * pos (b) < 0 then Case 2 else Case 1.
36

• Case 3 and Case 4 deal with an edge.
• Let i and j be the indices of the two vertices of the edge
where j = i + 1.
• Check the condition (y[j] = yc AND x[j] > xc).
• Then a (= i - 1) and b (= j + 1) are the indices of the two
neighboring vertices.
• If pos (a) * pos (b) < 0 then Case 4 else Case 3.
37

• p is even  The new point is outside the polygon.
• p is odd  The new point is inside the polygon.
• Modulo operator is used.
IF (p MODULO 2 == 0)
{
RETURN 0;
}
38

Finding the Primary Sectors
• The convex partitioning is done by drawing line segments
inside the polygon.
• These segments are called sectors.
• These sectors are found in two stages namely primary
sectors and secondary sectors.
• This section describes the process of finding primary sectors.
39

Finding the Primary Sectors…
• The number of sectors are stored in variable secs which is
initially 0.
• End points of the sectors are stored in arrays.
• (sx[i], sy[i]) and (ex[i], ey[i]) denote the end points of the ith
sector.
• Finding primary sectors is done using function setSectors1.
40

• All line segments joining pairs of reflex vertices are tested for
being sectors.
• Two nested for loops are used to access all possible pairs of
vertices.
• The condition reflex[i] * reflex[j] = 0 denies the situations
where at least one of the vertices are not reflex. (Use of
keyword CONTINUE)
• A line segment in which both vertices are reflex may coincide
with an edge of the polygon if both of the vertices of the edge
are reflex. (Check the condition j – i > 0)
41

• The variable found is initialized to 0.
• Using another for loop, each edge of the polygon is accessed.
• Each edge is tested for x-intersection with the line segment
using function isIntersect.
• If at least one of the edges x-intersect with the line segment
then variable found would be set into 1.
42

• If still the variable found is 0 then using a for loop, each
vertex is tested whether the vertex is inside the line segment.
• If the function tv returns 0 then the three points are collinear.
• Then the projections on principle axes are considered to
decide whether the given vertex is inside the line segment or
not.
 Projection on x-axis, if |gradient| ≤ 1.
 Projection on y-axis, if |gradient| > 1.
• If the given vertex is inside the line segment then variable
found should be set into 1.
43

• If still the variable found is 0 then that means:
 The line segment does not have x-intersections with any
of the edges of the polygon.
 None of the vertices of the polygon are inside the line
segment.
• Now the line segment may be inside or outside the polygon.
• If the midpoint (midx, midy) of the line segment is inside the
polygon then the line segment is also inside the polygon.
• If the line segment separates the polygon into two polygons
such that the interior angles formed after separation are
convex then the line segment is added to the list of sectors.
(Use of function isUseful)
44

The function isUseful
• The angles a, b, c, d formed by the line segment should be
less than π for the line segment to be eligible as a sector.
45

The function isUseful…
• If A and B are on the same side of the extended line segment
then it cannot be a sector.
46

• The function isUseful returns 1 if the line segment is a sector
else returns 0.
• Here i and j represent the indices of the vertices of the line
segment.
• Initially variable t = 0.
47

a = (i - 1) MODULO points;
b = (i + 1) MODULO points;
IF (tv (x[i], y[i], x[j], y[j], x[a], y[a]) * tv (x[i], y[i], x[j], y[j], x[b], y[b]) > 0)
{
t = 1;
}
a = (j - 1) MODULO points;
b = (j + 1) MODULO points;
IF (tv (x[i], y[i], x[j], y[j], x[a], y[a]) * tv (x[i], y[i], x[j], y[j], x[b], y[b]) > 0)
{
t = 1;
}
48

• If the variable t is still 0 then function isUseful returns 1.
• If the line segment passes the isUseful test then it is added to
the list of sectors. (See function setSectors1)
reflex[i]=0;
reflex[j]=0;
sx[secs]=x[i];
sy[secs]=y[i];
ex[secs]=x[j];
ey[secs]=y[j];
secs = secs + 1;
49

Intersection Point of Two Straight Lines
• Any two straight lines intersect unless they are parallel.
• Let’s consider two lines L1 and L2 formed by end points {P1
(x1, y1), P2 (x2, y2)} and {P3 (x3, y3), P4 (x4, y4)} respectively.
• If L1 and L2 are not parallel then these eight coordinates are
sent to function findIntersection to compute the intersection
point (xn, yn).
50

Intersection Point of Two Straight Lines…
• Let’s take (m1, c1) and (m2, c2) as the (gradient, y-intercept)
of each line respectively if they exist.
• There are four different cases of these two lines.
51

• Case 1; (x1 = x2; x3 = x4): This case is ignored and not
handled using the function. Only coordinates of non-parallel
lines are sent to the function.
52

• Case 2; (x1 = x2; x3 ≠ x4): L1 is parallel to y-axis and L2 is
not parallel to y-axis.
• m2 = (y3 – y4)/(x3 – x4);
• c2 = y3 – m2 * x3;
• xn = x1;
• yn = m2 * xn + c2;
53

• Case 3; (x1 ≠ x2; x3 = x4): L1 is not parallel to y-axis and L2
is parallel to y-axis.
• m1 = (y1 – y2)/(x1 – x2);
• c1 = y1 – m1 * x1;
• xn = x3;
• yn = m1 * xn + c1;
54

• Case 4; (x1 ≠ x2; x3 ≠ x4): Both L1 and L2 are not parallel to
y-axis.
• m1 * xn + c1 = m2 * xn + c2  xn = (c2 – c1)/(m1 – m2);
• yn = m1 * xn + c1;
55

The Function setClosest
• The function setClosest takes two parameters i and j which
denote the indices of two end points of a given edge.
• The purpose is to find the closest point to vertex j which is
situated in the opposite side of vertex i with respect to vertex
j.
• In this example, the goal point is P1.
56

The Function setClosest…
• For each point (xn, yn), the function is invoked.
• The closest point is stored in coordinates (xg, yg).
• Initially variable found = 0.
• The variable found is set to 1 after first invocation of the
function.
• Here dx = x[i] – x[j] and dy = y[i] – y[j].
• Projection of the edge on principle axes:
 |dx| > |dy|  Projection on x-axis.
 |dx| ≤ |dy|  Projection on y-axis.
57

The Function setClosest…
• Let’s consider the projection on x-axis.
• The expression dx * (xn – x[j]) < 0 is true only for points
which are on the opposite side of vertex i with respect to
vertex j.
• If found = 0 then (xg, yg)  (xn, yn).
• If found ≠ 0 then dx > 0 or dx ≤ 0 should be considered.
• If dx > 0 then xn > xg  (xn, yn) is closer to vertex j than
(xg, yg). Similarly dx ≤ 0 should be handled.
• Similar mechanism can be used for projection on y-axis.
58

An Illustrative Example
• The indices of first two vertices are shown in example
polygon.
• The ordering of vertices is anticlockwise.
• However, the proposed algorithm works for both clockwise
and anticlockwise polygons.
59

An Illustrative Example…
• Find all reflex vertices of the polygon.
• Circles represent reflex vertices.
60

An Illustrative Example…
• The primary sectors are shown using dotted lines.
• The end vertices of a primary sector become non-reflex.
61

Finding the Secondary Sectors
• Finding the secondary sectors is done using the function
setSectors2.
• The i and j denote the indices of end points of an edge where
j = i + 1.
• The edges where reflex[j] = 1 are selected using condition if.
• The variable found is initially 0 and accessed inside function
setClosest.
62

Finding the Secondary Sectors…
• Suppose the edge is extended in ij direction to infinity.
• The extended edge may x-intersect with:
 Edges of the polygon.
 Sectors available in the sector list.
• In such cases, intersection points should be computed.
• Further, the extended edge may go through:
 End points of the edges.
 End points of the available sectors in the sector list.
63

• Out of those x-intersection points and go-through points,
the closest point to vertex j is selected. (Use of the function
setClosest)
• A new sector is added using extended edge by taking vertex j
and the closest point as its end points.
• Five FOR loops are used to do the above task.
64

• Let’s look at first FOR loop.
• The edges which x-intersect the extended edge are found
using function isTwoSides.
• The intersection points of such edges are found using
function findIntersection.
• With respect to each intersection point, the function
setClosest is invoked.
65

• Let’s look at second FOR loop.
• The polygon vertices which are on the extended edge are
found by testing co-linearity using function t.
• With respect to each such polygon vertex, the function
66

• Let’s look at third FOR loop.
• The available sectors which x-intersect the extended edge are
found using function isTwoSides.
• The intersection points of such sectors are found using
function findIntersection.
• With respect to each intersection point, the function
67

• Let’s look at fourth FOR loop.
• The available sector starting points which are on the extended
edge are found by testing co-linearity using function t.
• With respect to each such point, the function setClosest is
invoked.
68

• Let’s look at fifth FOR loop.
• The available sector ending points which are on the extended
edge are found by testing co-linearity using function t.
• With respect to each such point, the function setClosest is
invoked.
69

Back to the Example
• The primary sectors are shown using dotted lines.
• (2, 3), (6, 7), and (7, 8) edges create secondary sectors.
70

Back to the Example…
• The secondary sectors are shown in different type of dotted
lines.
• Note that the angles created are not reflex.
71

Comparison with Hertel Mehlhorn Algorithm
• In this example, both algorithms give same number of
partitions.
• However, the convex pieces are different.
72

Minimum Partitioning?
• The proposed algorithm may fail to give the minimum
number of convex pieces for some polygons.
• The previous example can be partitioned just by using four
convex pieces.
73

Time Complexity
• Let n be the number of vertices in the given polygon.
• It takes O (n) time to find the lowest vertex of the polygon.
• It takes O (n) time to find all reflex vertices of the polygon if
the lowest vertex is provided.
• Altogether, it takes O (n) + O (n) = O (n) time to find reflex
vertices.
• It is necessary to test line segments formed by each pair of
reflex vertices of the polygon to find primary sectors.
• It takes O (n2) time to access each pair in the worst case.
• It takes O (n) time to check whether a given line segment
intersects with each edge of the polygon.
• After finding such a non-intersecting line segment, it takes O
(n) time to check whether it is inside the polygon.
75

Time Complexity…
• It takes only O (1) time to check whether such an interior
non-intersecting line segment successfully contributes to
convex partitioning.
• Altogether, it takes O (n2) * {O (n) + O (n) + O (1)} = O (n3)
time to find primary sectors if the reflex vertices are
provided.
• Therefore, the time complexity of finding primary sectors is
O (n) + O (n3) = O (n3).
• Each edge of the polygon is considered to find secondary
sectors.
• It takes O (n) time to access each edge.
• A given virtually extended edge should be tested with each
edge of the polygon which takes O (n) time.
• The number of primary sectors cannot exceed O (n2).
76

Time Complexity…
• Therefore, it takes O (n2) time to test the virtually extended
edge with each primary sector in the worst case.
• It takes O (n) time to test the virtually extended edge with
each secondary sector in the worst case.
• It takes O (n) time to find the closest intersection point in the
worst case.
• Therefore, it takes O (n) * {O (n) + O (n) + O (n)} = O (n2)
time to find secondary sectors.
• Thus, the time complexity of the proposed algorithm is O (n3)
+ O (n2) = O (n3).
77

Space Complexity
• It takes n memory cells to hold x-coordinates and n memory
cells to hold y-coordinates.
• Altogether, it takes 2n memory cells to hold the input.
• Therefore, it needs O (n) space to hold the input.
• The number of candidate primary sectors cannot exceed O
(n2).
• Therefore, the space complexity of the primary sectors is O
(n2).
• Each edge is considered for candidate secondary sectors.
• Therefore, the space complexity of the secondary sectors is O
(n).
• The additional memory required is O (1).
• Therefore, the space complexity of the proposed algorithm is
O (n) + O (n2) + O (n) + O (1) = O (n2).
78

Number of Convex Pieces
• Number of convex pieces against Hertel Mehlhorn algorithm
was compared using twenty random polygons.
79

Comparison
• Hertel Mehlhorn algorithm is the fastest algorithm available
in literature.
• HM algorithm takes O (n2) time and O (n2) space.
• The proposed algorithm produces smaller number of convex
pieces than HM algorithm even though it is slower.
• Furthermore, the proposed algorithm is faster than the other
algorithms which produce exact convex pieces.
80

Conclusion
• The proposed convex partitioning algorithm gives smaller
number of convex pieces than the Hertel Mehlhorn algorithm
and also performs exact convex partitioning.
82

Convex Partitioning of a Polygon into Smaller Number of Pieces with Lowest Memory Consumption

Recommended

More Related Content

Similar to Convex Partitioning of a Polygon into Smaller Number of Pieces with Lowest Memory Consumption (20)

More from Kasun Ranga Wijeweera (20)

Recently uploaded (20)

Convex Partitioning of a Polygon into Smaller Number of Pieces with Lowest Memory Consumption