CODEWITHSUNDEEP
algorithmgeometrycomputational-geometry
sayeg84
sayeg84

Reputation: 117

Algorithm for 3D polygonal chain intersection

I have two 3D polygonal chains and I want to know if they intersect or not. This problem is known as the Polygonal Chain Intersection. Good algorithms exists for the 2D case, but I have not seen any for the 3D case

Anybody can help with this?

Upvotes: 2

Views: 137

Answers (1)

Futurologist
Futurologist

Reputation: 1914

Ok, maybe this is a stupid algorithm, but why don't you pick some plane (in general position, or one of the coordinate planes), project orthogonally the two 3D chains onto the plane and solve the 2D problem using one of these efficient algorithms, which will allow you to locate all points of intersection between the projections and all pairs of segments from the two 3D chains, whose projections intersect at the intersection points. Then from each intersection 2D point, draw the line through that point, perpendicular to the plane and check where this line intersects each of the two 3D segments, one from the first 3D chain, the other from the second, whose projections intersect at the 2D intersection point. If the resulting points are different, the 2D projected intersection point is not a true 3D intersection point. Else, you get an intersection point for the 3D chains.

Upvotes: 2

Related Questions