CODEWITHSUNDEEP
2dpolygoncomputational-geometryclipping
Daerst
Daerst

Reputation: 973

Clipping and triangulating a triangle with a non convex polygon

I'm starting with a single 2D triangle that I want to clip with a (potentially) convex 2D polygon. It's not self-intersecting, but may 'keep' or 'discard' the intersecting area based on the winding order.

I want to end up with a triangulation, i.e. a list of n vertices and m triangles, defined by 3 vertices each, of the clipped region in 2D space.

What would be the easiest (for me as a developer), and what the fastest (in terms of computation) way to achieve this?

Upvotes: 0

Views: 1382

Answers (1)

user1196549
user1196549

Reputation:

If I a right, you want to clip inside the polygon, i.e. get the intersection between the triangle and the polygon.

As the triangle is a convex shape, the Sutherland-Hodgman algorithm is appropriate and no too difficult to implement (https://en.wikipedia.org/wiki/Sutherland%E2%80%93Hodgman_algorithm).

Notice that if the intersection is not simply connected, the resulting polygon will be connected, with double edges joining the would-be parts. Some cleanup might be required.

After finding the intersection, you re-triangulate using the ear-clipping method or a more efficient one (https://en.wikipedia.org/wiki/Polygon_triangulation).

Alternatively, you can triangulate the polygon and perform the clipping of every triangle with the original one.

The triangle-triangle clipping problem is again solved with Sutherland-Hodgman, somewhat simplified as the input polygons have a constant size, and their intersection is convex and at worse an hexagon. Trigulation of a convex polygon is immediate.

Upvotes: 1

Related Questions