Scribd Logo
Upload

Welcome to Scribd!

  • 50 views

    CSN-523: Computational Geometry: Lecture 19: Partitioning A Polygon Into Monotone Polygons (Polygon Partitioning)

    Uploaded by

    saiavinash duddupudi
    The document discusses partitioning a polygon into monotone polygons. It defines monotone polygons as those that can be divided into horizontal strips by vertical lines. The key steps are: 1) Identify turn vertices such as split and merge vertices that make the polygon non-monotone. 2) Add diagonals from these turn vertices to "helper" vertices to partition the polygon into monotone pieces. 3) Use a plane sweep algorithm and data structures like a priority queue and binary search tree to efficiently find helper vertices and add the required diagonals, outputting the final monotone partition.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    CSN-523: Computational Geometry: Lecture 19: Partitioning A Polygon Into Monotone Polygons (Polygon Partitioning)

    Uploaded by

    saiavinash duddupudi
    50 views56 pages
    The document discusses partitioning a polygon into monotone polygons. It defines monotone polygons as those that can be divided into horizontal strips by vertical lines. The key steps are: 1) Identify turn vertices such as split and merge vertices that make the polygon non-monotone. 2) Add diagonals from these turn vertices to "helper" vertices to partition the polygon into monotone pieces. 3) Use a plane sweep algorithm and data structures like a priority queue and binary search tree to efficiently find helper vertices and add the required diagonals, outputting the final monotone partition.

    Original Title

    CSN523_Lec_19.pdf

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses partitioning a polygon into monotone polygons. It defines monotone polygons as those that can be divided into horizontal strips by vertical lines. The key steps are: 1) Identify turn vertices such as split and merge vertices that make the polygon non-monotone. 2) Add diagonals from these turn vertices to "helper" vertices to partition the polygon into monotone pieces. 3) Use a plane sweep algorithm and data structures like a priority queue and binary search tree to efficiently find helper vertices and add the required diagonals, outputting the final monotone partition.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    50 views56 pages

    CSN-523: Computational Geometry: Lecture 19: Partitioning A Polygon Into Monotone Polygons (Polygon Partitioning)

    Uploaded by

    saiavinash duddupudi
    The document discusses partitioning a polygon into monotone polygons. It defines monotone polygons as those that can be divided into horizontal strips by vertical lines. The key steps are: 1) Identify turn vertices such as split and merge vertices that make the polygon non-monotone. 2) Add diagonals from these turn vertices to "helper" vertices to partition the polygon into monotone pieces. 3) Use a plane sweep algorithm and data structures like a priority queue and binary search tree to efficiently find helper vertices and add the required diagonals, outputting the final monotone partition.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 56

    INDIAN INSTITUTE OF TECHNOLOGY ROORKEE

    CSN-523: Computational Geometry


    Lecture 19: Partitioning a Polygon into Monotone Polygons
    (Polygon Partitioning)

    Dr. Sudip Roy


    Assistant Professor
    Department of Computer Science & Engineering
    Piazza Class Room: https://piazza.com/iitr.ac.in/spring2017/csn523/home
    Moodle Site: http://moodle.iitr.ac.in/course/view.php?id=23 [Enrollment Key: csn523@2017]
    Monotone Partition:

    2
    Monotone Partition:

    3
    Monotone Partition:

    4
    Monotone Partition:

    5
    Monotone Partition:

    6
    Turn Vertex:

    Imagine walking from the topmost vertex of P to the bottommost vertex on


    the left/right boundary chain...

    Definition: A vertex where the direction in which we walk switches from


    downward to upward or vice versa

    To partition a polygon into y-monotone pieces, get rid of turn vertices by


    adding diagonals

    7
    Types of Turn Vertices:

    If we want to define the different types of turn vertices carefully,we should


    pay special attention to vertices with equal y-coordinate.We do this by
    defining the notions of below and above as follows ; a point p is below
    another point q if
    p <q
    y y
    or p =q
    y y
    and p >q
    x x
    , and p is above q if p >q
    y y
    or p =q
    y y
    and p <q
    x x

    Start Vertex - its two neighbors lie below it and the interior angle < 180

    End Vertex - its two neighbors lie above it and the interior angle < 180

    Split Vertex - its two neighbors lie below it and the interior angle > 180

    Merge Vertex - its two neighbors lie above it and the interior angle > 180

    8
    Vertex Ontology:

    Idea: The split and merge


    vertices are sources of
    local non-monotonicity.The
    following stronger stament
    is true.

    LEMMA:A polygon is y-
    monotone if it has no split
    vertices or merge vertices.

    9
    Vertex Types in a Simple Polygon:

    10
    Plane Sweep Approach:

    11
    Monotone Partitioning:

    12
    Adding diagonals:

    * The partition p into y-monotone pieces , get rid


    of split and merge vertices
    1. Add a diagonal going upward each split
    vertex.
    2. Add a diagonal going downward from each
    merge vertex.
    * Where do the edges go?

    13
    Monotone Partition:

    14
    Monotone Partition:

    15
    Monotone Partition:

    16
    Monotone Partition:

    17
    Monotone Partition:

    18
    Monotone Partition:

    19
    Monotone Partition:

    20
    Monotone Partition: Helpers

    Let helper helper(ej) be the lowest vertex above the sweep-


    line
    Such that the horizontal segment connecting the vertex to ej
    lies inside P

    21
    Removal of Split Vertices:

    For a split vertex vi ,let be the edge immediately to the


    left of it.
    Add a diagonal from vi to helper ej

    22
    Removal of Merge Vertices:

    23
    Removing Split/Merge Vertices:

    v1 vn: a counter-clock enumeration of vertices of P


    e1 en: a set of edges of P, where ei = segment (vi , vi+1)
    Events are stored in event queue (priority queue), ordered by
    y-coord.
    If a split vertex, connect it to the lowest vertex (helper of its
    left edge) between the edges to its left and right
    If a merge vertex, connect it to the highest vertex between
    the edges to its left and right
    Store the edges (and their helpers) of P in the leaves of
    dynamic binary search tree T, left-to-right order reflects in
    order of leaves. Helpers may be replaced. Store only edges
    that have P to their right (or the left edges).

    24
    Data Structures used:

    A doubly connected edge list DCEL is used to store the monotone polygons. A DCEL has
    the following properties:
    1. Any vertex has access to one edge that it is on.
    2. Any face has access to one edge that surrounds it.
    3. Any edge has access to 2 vertices and the face to its right and the face to its left.
    A priority queue Q on the vertices of P, using their y-coordinates as priority. If two points
    have the same y-coordinates, the one with smaller x has higher priority
    Status structure T, is a Balanced Binary Search Tree that stores the edges. It represents the
    current portion of the polygon the sweep line is currently crossing is needed. T is a BBST,
    sorted based on relative x-position of edges. For our purposes and examples, lower x-
    coordinate edges will be to the left of edges with higher x-coordinates.
    Three kinds of updates to T are possible.
    1. Put new edge into T. (start vertex)
    2. Replace an edge within T (adding old edge into DCEL). (merge vertex)
    3. Remove edge from T (adding old edges into DCEL) Note: these edges will be
    adjacent in T. (end vertex)

    25
    MakeMonotone(P):

    Input: A simple polygon P stored in a doubly-connected edge list D


    Output: A partitioning of P into monotone subpolygons stored in D

    1. Construct a priority queue Q on the vertices of P, using their y-


    coordinates as priority. If two points have the same y-coordinates, the
    one with smaller x has higher priority
    2. Initialize an empty binary search tree T
    3. while Q is not empty
    4. do Remove vi with the highest priority from Q
    5. Call the appropriate procedure to handle the vertex,
    depending on its type

    26
    HandleStartVertex(Vi):

    (Insert this vertexs edge into the sweep line status structure T; set the
    helper of the left edge to v)

    At start vertex v5, we


    insert e5 into T

    27
    HandleEndVertex(Vi):

    At end vertex v15, the helper of


    the edge e14 is v14. v14 is not a
    merge vertex, so we dont need to
    insert a diagonal

    28
    HandleSplitVertex(Vi):

    For split vertex v14, e9 is the edge


    to the left. Its helper is v8, so we
    add a diagonal from v14 to v8

    29
    HandleMergeVertex(Vi):

    For vertex v8, the helper v2


    of edge e7 is a merge
    vertex, so we add a
    diagonal from v8 to v2

    30
    HandleRegularVertex(Vi):

    At the regular vertex v6, we


    add diagonal from v6 to v4

    31
    Monotone Partition:

    32
    Monotone Partition:

    33
    Monotone Partition:

    34
    Monotone Partition:

    35
    Monotone Partition:

    36
    Monotone Partition:

    37
    Monotone Partition:

    38
    Monotone Partition:

    39
    Monotone Partition:

    40
    Monotone Partition:

    41
    Monotone Partition:

    42
    Monotone Partition:

    43
    Monotone Partition:

    44
    Monotone Partition:

    45
    Monotone Partition:

    46
    Monotone Partition:

    47
    Monotone Partition:

    48
    Monotone Partition:

    49
    Monotone Partition:

    50
    Monotone Partition:

    51
    Monotone Partition:

    52
    Monotone Partition:

    53
    Monotone Partition:

    54
    Monotone Partition:

    55
    Monotone Partition:

    56

    You might also like