of 12

# Polygon Union

Published on: Mar 4, 2016

#### Transcripts - Polygon Union

• 1. Polygon Union Amiya Tripathy (08431401) Imdad Rizvi (07431005) Sangita Mishra (08431001) Samee Azmi (08431601)
• 2. Problem Statement <ul><li>Given two polygon layers, we need to find the union of the two polygons. </li></ul>
• 3. Steps involved <ul><li>Take input polygons, store them in separate arrays. </li></ul><ul><li>Check whether the polygons intersect using the MBR method. </li></ul><ul><ul><li>(p1XMax >= p2XMin) && (p1YMax <= p2YMin) </li></ul></ul><ul><li>If poly_mbr = true </li></ul><ul><ul><li>Polygons might intersect </li></ul></ul>
• 4. Steps involved <ul><li>Angle for a convex polygon = 360 o if the point is in the polygon </li></ul>
• 5. Steps involved <ul><li>If the MBRs intersect then we consider that the polygons intersect </li></ul><ul><ul><li>We take the first edge consisting of p1x1y1 and p1x2y2 of the first polygon and similarly for the second polygon </li></ul></ul><ul><ul><li>Check for the min max among these four points </li></ul></ul><ul><ul><li>Generate an MBR for all the edges of polygon 2 and check it with each edge of polygon 1 </li></ul></ul><ul><ul><li>If the MBRs intersect then we check for point of intersection between these two edges. </li></ul></ul><ul><ul><li>Then we check if the intersection point lies on the line or not </li></ul></ul>
• 6. Data Considered
• 7. Finding Point of intersection <ul><li>Finding ua and ub </li></ul><ul><li>Substituting either of these into the corresponding equation for the line gives the intersection point. For example the intersection point (x,y) is </li></ul><ul><li>x = x1 + ua (x2 - x1) </li></ul><ul><li>y = y1 + ua (y2 - y1) </li></ul>
• 8. Checking point on the line <ul><li>Check if this point lies on the line or not </li></ul><ul><ul><li>chk1 = ipx/xmax1; </li></ul></ul><ul><ul><li>chk2 = ipx/xmax2; </li></ul></ul><ul><ul><li>chk3 = ipy/ymax1; </li></ul></ul><ul><ul><li>chk4 = ipy/ymax2; </li></ul></ul><ul><li>if(chk1 <= 1 && chk2 <= 1 && chk3 <= 1 && chk4 <= 1) </li></ul><ul><ul><li>Then the point is on the line </li></ul></ul>
• 9. Finding Angles <ul><li>We maintain a separate array of the intersection points and the involved vertices for intersection. </li></ul><ul><li>We are able to calculate angles for any given two edges </li></ul><ul><li>D = a.b/|A||B| </li></ul><ul><li>θ = cos -1 (D) </li></ul><ul><li>a = (x2-x1, y2-y1) </li></ul><ul><li>b = (x3-x1, y3-y1) </li></ul><ul><li> c = (x2 - x1) * (x3 - x1) + (y2 - y1) * (y3 - y1); </li></ul>
• 10. <ul><li>We need to generate a new array consisting of the new polygon vertices with intersecting points. </li></ul><ul><li>We get 4 directions from the intersection points of two lines. </li></ul><ul><li>Taking a base edge, we calculate the angles for the remaining three edges and store them. </li></ul><ul><li>We proceed in the direction where the angle is minimum anticlockwise. </li></ul><ul><li>Check for the co-ordinates in the new polygon arrays and proceed </li></ul><ul><li>Also check for the array of intersecting points </li></ul><ul><ul><li>Go back to step 1 </li></ul></ul><ul><ul><li>Repeat the process for both the intersection points till all the angles have been used. </li></ul></ul><ul><ul><li>We now have 4 polygons </li></ul></ul><ul><ul><ul><li>New A polygon </li></ul></ul></ul><ul><ul><ul><li>New B polygon </li></ul></ul></ul><ul><ul><ul><li>AB intersecting polygon (intersection) </li></ul></ul></ul><ul><ul><ul><li>Universal Polygon (Dissolved) </li></ul></ul></ul>Finding Polygons
• 11. Problems faced during implementation <ul><li>Deciding the direction in which we should proceed </li></ul><ul><li>Slope of line </li></ul><ul><li>Positive and negative tracing of vectors </li></ul>
• 12. Thank You