CODEWITHSUNDEEP
geometry2dpolygondivide
Jorjon
Jorjon

Reputation: 5434

Split 2D quad by line

I found many implementations that deal with splitting a polygon by a given line, but I only need to split a Quad (rectangle with 4 vertexes).

Is there an algorithm optimized for this task? Simplicity is valued over performance.

I narrowed down 4 types of intersection:

Adjacent

Where the line enters one side and leaves through an adjacent side.
This will generate 1 polygon with 3 points and 1 polygon with 5 points.

Adjacent

Opposite

Where the line enters one side and leaves through the opposite side.
This will generate 1 polygon with 4 points and 1 polygon with 4 points.

Opposite

Diagonal Opposite

Where the line enters one corner and leaves through the opposite corner.
This will generate 1 polygon with 3 points and 1 polygon with 3 points.

Diagonal Opposite

Diagonal Adjacent

Where the line enters one corner and leaves through an adjacent side.
This will generate 1 polygon with 3 points and 1 polygon with 4 points.

Diagonal Adjacent

But so far I was unable to come up with a good simple algorithm.

Upvotes: 2

Views: 383

Answers (1)

MBo
MBo

Reputation: 80325

There are a lot of effective algorithms to clip a line by rectangular window.

I've used Liang-Barski one for my purposes (check "External Links" section for effective implementation)

Upvotes: 1

Related Questions