Hi All, This is my first posting in this forum and I am not sure if this is the right one for my question. I have come to a point where I need to test whether a concave polygon (A) can be contained by another concave polygon (B). I looked into literature and most of the places they address the problem of convex polygon containment and use optimization based approaches. Has anyone here, come across concave-in-concave 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. Desperately looking for some pointers. -Atul

I've never done anything like this before but after thinking about it for ~2 minuites, could you not just check if any one point lies in the outer-poly, ifso then loop through all the line segments that make up the inner-poly, if one of these lines colides with one of the lines of the outer-poly then its outside other wise its inside.

bool Poly::isInside(const Poly& other) const{   for(int i = 0; i < m_nVertices; ++i)   {      if(!other.containsPoint(m_vertices))         return false;   }   int j = m_nVertices-1;   for(int i = 0; i < m_nVertices; j = i++)   {      int l = other.m_nVertices-1;      for(int k = 0; k < other.m_nVertices; l = k++)      {         if(line_seg(m_vertices, m_vertices[j]).intersects(            line_seg(m_vertices[k], m_vertices[l]))            return false;      }   }   return true;}

Quote:Original post by staticVoid2
I've never done anything like this before but after thinking about it for ~2 minuites, could you not just check if any one point lies in the outer-poly, ifso then loop through all the line segments that make up the inner-poly, if one of these lines colides with one of the lines of the outer-poly then its outside other wise its inside.

bool Poly::isInside(const Poly& other) const{   for(int i = 0; i < m_nVertices; ++i)   {      if(!other.containsPoint(m_vertices))         return false;   }   int j = m_nVertices-1;   for(int i = 0; i < m_nVertices; j = i++)   {      int l = other.m_nVertices-1;      for(int k = 0; k < other.m_nVertices; l = k++)      {         if(line_seg(m_vertices, m_vertices[j]).intersects(            line_seg(m_vertices[k], m_vertices[l]))            return false;      }   }   return true;}

This can be done if the orientation and location of both polygons are known.

The problem stated here is to find containment when only the shape (independent of location and orientation) of polygons are known.
In other words it is like determining whether an arbitrary shaped plate (B) be inserted in an arbitrary hole (A). Obviously, the plate can only be rotated in its own plane and no other plane.
Thinking of writing my own algorithm but before that want to make sure if no one has tried it before.
-Atul

This is a really difficult problem. Most "find out if X is possible" or "if there exists" geometric problems are.

If you have specific input data in mind, as an approximation I would suggest finding the bounding rectangle of the "to be contained" polygon, then applying a minkowsi subtraction to the "containing" polygon, and seeing if you get a null set. If the set is non-null you definitely can contain the polygon, otherwise it means that you still may be able to, since this is only a very rough approximation. It should be reasonably accurate if the "to be contained" polygon is small relative to the "containing" polygon, and neither of them are "intricately convex".

Apart from that, I suggest looking at the "point matching" literature out there - if your polygons have similar shape, this should be able to give you an orientation in which the one may fit into the other (although in practice the "containing" polygon may be radically different from the "to be contained" polygon, so matches may be tricky.

Otherwise, another suggestion is to cast this as an optimization problem and define a fitness/objective function to maximize (here, you want to maximize the intersection area, where if the intersection area is equal to the "to be contained" polygon you have a solution. The next step is to rotate and translate gradually in order to try and maximize this function. The optimal solution is easy if your polygons are convex and you are just translating, but for non-convex polygons and three degrees of freedom (rotation+translation) this will prove to be very hard, since there will be many local minima and maxima. The optimization literature may help, but most of it is very involved.

Quote:Original post by arithma
If converting those concave polygons into convex polygons helps, I can hand you some code that does that.. Otherwise am interested to see where you'll take this

Thanks for the suggestions.
In my particular case it is not necessary that contained polygon is smaller than the containing polygon. I have however figured out that if I approximate the containing polygon by its convex hull it will be a good start for me.

As per my bigger problem if containing polygon CAN contain contained polygon but I get answer as NO then I CAN NOT tolerate it.

However, if containing polygon CAN NOT contain contained polygon but I get answer as YES then I CAN tolerate it (though my solution to bigger problem will not be efficient)

Under these circumstances I think assuming convex hull for containing polygon can be acceptable start.

In other words, can I state the following <or is it trivial to state without proof>?
**If a concave polygon A can contain concave polygon B then convex hull of A will also contain B and if A can not contain B then convex hull of A will not contain B.**

I really appreciate your help.

-Atul

Quote:Original post by athakur
In other words, can I state the following <or is it trivial to state without proof>?
**If a concave polygon A can contain concave polygon B then convex hull of A will also contain B and if A can not contain B then convex hull of A will not contain B.**

The first statement is trivially true, because the convex hull of a polygon is a superset of the polygon. The second statement is false. Consider B to be a regular pentagon, and A to be an inscribed star. A cannot contain B, but the convex hull of A (a pentagon identical to B) can contain B.