CODEWITHSUNDEEP
algorithm3dcomputational-geometry
innochenti
innochenti

Reputation: 1103

Intersection between two concave polygons in given direction

Input: Two 3d concave polygons A and B, unit vector d. No polygons are intersecting at time t = 0. Expected that direction d will not change very often, so some preprocess phase is needed.

Problem: Determine if two concave polygons A and B can be intersected in direction d, at some time t. In another words: if we move one polygon in given direction d, would it intersect another polygon?

Output: 1 - intersection exist, 0 - othewise.

Upvotes: 2

Views: 958

Answers (1)

Jarosław Gomułka
Jarosław Gomułka

Reputation: 4985

First you should find plane that is perpendicular to vector d.

Plane

For both 3d polygons you should calculate projection on this plane. Then, if the projections are overlapping then the 3d polygons will intersect at some time t.

Now you have simpler problem: checking if two 2d non-convex polygons are intersecting. You can do it by simply iterate over every pair of edges and check if they are intersecting.

Upvotes: 5

Related Questions