CODEWITHSUNDEEP
performancealgorithmcomputational-geometry
DOFHandler
DOFHandler

Reputation: 225

Intersection of a line and a concave polygon 3D

My problem is to find if a generic (convex or concave) polygon and a rectangular polygon in 3D space has a not-null intersection. Each polygon is defined by the set of the ordinated contour points (if point p1 is after/before point p2 the edge p1-p2 exists).

It is easy to find the intersection line of the two plane of the polygons so the problem is finding the intersections of a line and the finite polygons and if the resulting intersections have a portion in common. I found algorithms for the intersection of a line and a convex polygon but I can't find anything for the general case of concave polygon.

Any suggestion? Thank you

Upvotes: 3

Views: 1811

Answers (3)

agentp
agentp

Reputation: 6989

find the intersection point of the plane-intersection line with every edge of both figures. From there its s straightforward problem of looking at the ordering of the points on the line to check for any overlap.

Of course the special case where they are coplanar is a whole other problem..

Upvotes: 1

cmaster - reinstate monica
cmaster - reinstate monica

Reputation: 40594

If you can rely on the polygon to be planar, you can first intersect the line with the plane and then transform the intersection point into the coordinate system of the plane.

Assuming you have also transformed all the vertices of the polygon, the problem is now to decide whether the 2D intersection point is within a 2D polygon.

Upvotes: 0

HugoRune
HugoRune

Reputation: 13789

There are usually no fast solutions for concave polygon intersection / containment/ etc queries.

The general solution is always to triangulate the polygon into a series of convex triangles, then run your intersection test with those triangles.

Upvotes: 0

Related Questions