CODEWITHSUNDEEP
algorithmgraphicspolygon
Tikhon Belousko
Tikhon Belousko

Reputation: 777

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 these two polygons?

Upvotes: 14

Views: 19306

Answers (3)

Yola
Yola

Reputation: 19033

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

Upvotes: 11

Joseph O'Rourke
Joseph O'Rourke

Reputation: 4406

Besides @Yola's nice plane-sweep description, there is a linear-time algorithm described in Computational Geometry in C, Chapter 7. And C & Java code is available (at the same link). There are several tricky degenerate cases, e.g., when the two polygons intersect at a point, or the intersection is a segment.

Upvotes: 3

Markus Jarderot
Markus Jarderot

Reputation: 89171

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:

Upvotes: 11

Related Questions