Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Intersection of two convex polygons

I have two convex polygons. Polygons are implemented as cyclic lists of their vertices. How to find an intersection of this two polygons?

like image 952
DaZzz Avatar asked Oct 27 '12 15:10

DaZzz


People also ask

Do two convex polygons intersect?

To be able to decide whether two convex polygons are intersecting (touching each other) we can use the Separating Axis Theorem. Essentially: If two convex polygons are not intersecting, there exists a line that passes between them. Such a line only exists if one of the sides of one of the polygons forms such a line.

How do you find the intersection of two polygons?

Compute the center of mass for each polygon. Compute the min or max or average distance from each point of the polygon to the center of mass. If C1C2 (where C1/2 is the center of the first/second polygon) >= D1 + D2 (where D1/2 is the distance you computed for first/second polygon) then the two polygons "intersect".

What is the number of intersections of diagonals in a convex equilateral polygon?

Thus the number of diagonals pass through the centre is n2C1. But one of them is to be included, so, the total intersection is nC4−n2C1+1.

What is convex polygon theorem?

Convex Polygon Exterior Angles The exterior angle sum theorem states that the sum of the exterior angles of a convex polygon is 360°. If a convex polygon is regular with “n” number of sides, then each exterior angle of a convex polygon is measured as 360°/n.


2 Answers

For each edge V1-V2 in the first polygon,
    Let H := Half-plane tangenting V1-V2, with the remaining
        vertices on the "inside".
    Let C := New empty polygon.
    For each edge V3-V4 in the second polygon,
        Let X := The intersection between V3-V4 and H.
        If V3 inside H, and V4 is outside H then,
            Add V3 to C.
            Add X to C.
        Else if both V3 and V4 lies outside H then,
            Skip.
        Else if V3 outside H, and V4 is inside H then,
            Add X to C.
        Else
            Add V3 to C.
    Replace the second polygon with C.

This should suffice for simple usage; 10-20 vertices and not recalculating every frame. — O(n2)


Here is a few links:

  • Computer Graphics I – Polygon Clipping and Filling (pdf)
  • rosettacode.org – Sutherland-Hodgman polygon clipping
like image 68
Markus Jarderot Avatar answered Sep 18 '22 00:09

Markus Jarderot


You can benefit from the fact that both polygons are convex. And with this knowledge you can achieve O(n) time by using the followin sweep line algorithm:

Find the topmost points in both polygons. For simplicity suppose you have no horizontal edges. Create lists of edges contributing to the Left and Right boundaries of a polygon.

While sweeping down the plane you store 4 edges. left_edge_C1, right_edge_C1, left_edge_C2, right_edge_C2. You don't need any complex to strore the edges, because there are only four of them. You can find next event point just by iterating all possible options.

At each event point some edge appear on the boundary of their intersection. Basically, at each event point you can have one of three cases (see the pic.).

enter image description here

like image 37
Yola Avatar answered Sep 18 '22 00:09

Yola