Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.


Atul Thakur
Posts:
2
From:
College Park, MD, USA
Registered:
8/14/08


Concave Polygon Containment
Posted:
Aug 14, 2008 10:50 AM


Hi All, I have come to a point in my project where I need to test whether a concave polygon (A) can be contained by another concave polygon (B). I looked into some old literature and most of the places (Chazelle 1983, Toledo 1991, Agarwal 1995, etc.) they address the problem of convex polygon containment and use optimization based approaches. Has anyone here, come across concaveinconcave type of problem or some existing solution to it? Is it that this problem is not yet solved (which seems to me very less likely)? I can't use convex hull of inner polygon for the containment test because of the nature of my problem and type of solution I am seeking. I only know the shape of the polygons A and B and not their location and orientation. This can be done easily if the orientation and location of both polygons are known. Thinking of writing my own algorithm but before that want to make sure if no one has tried it before. thanks, Atul



