f



Polygon intersection, coverage, area, bounding box/circle,

Hi,

Assume we have two non-intersection polygons
P1 = p1(x1,y1), p2(x2,y2),..., pN(xN,yN)
P2 = p1(x1,y1), p2(x2,y2),..., pM(xM,yM)
where "Pi" is the polygon constructed with the ordered 2D points
"pi(xi,yi)", ie. vertices.
They could be convex or concave.

Following are two simple example polygons P1 and P2, with 4 and 6
vertices respectively.
P1 :
===
p1(x1,y1)    O----------O p2(x2,y2)
                   \           /
                    \          /
p1(x4,y4)      O-------O p3(x3,y3)

P2 :
===
p1(x1,y1)    O----------O p2(x2,y2)
                   \            \
                    \            \
                     \            O p3(x3,y3)
                      \           /
                       \         O p4(x4,y4)
                        \        |
    p6(x6,y6)      O-------O p5(x5,y5)

Question:
=======
Is there a public algorithm, and/or C/C++ source code that can test
the following;
   * If P1 and P2 intersect
     bool IsInterect(P1, P2);
   * If P1 covered by P2 (all vertices and edges of P1 are located in
P2)
     bool IsCovered(P1,P2);
   * Total area of P1
      float AreaOf(P1);
   * Area of intersection P1 and p2
      float AreaOfIntersection(P1,P2);
   * Bounding box of P1
     B1= BoundingBox(P1); (where B1 is a rectangle with 4 vertices)
   * Bounding Circle of P1
     C1 = BoundingCircleOf(P1); (where C1 defined by center coordiante
and radius)

Regards,

Albert

0
Albert
3/23/2007 5:28:12 AM
comp.robotics.misc 7077 articles. 0 followers. Post Follow

3 Replies
329 Views

Similar Articles

[PageSpeed] 7

Correction of a typo;
Wrong---> Assume we have two non-intersection polygons
Corrected ---> Assume we have two non-self-intersection polygons

Regard,

Albert

0
Albert
3/23/2007 12:27:50 PM
Albert Goodwill wrote:
> Assume we have two non-intersection polygons
> P1 = p1(x1,y1), p2(x2,y2),..., pN(xN,yN)
> P2 = p1(x1,y1), p2(x2,y2),..., pM(xM,yM)
> where "Pi" is the polygon constructed with the ordered 2D points
> "pi(xi,yi)", ie. vertices.
> They could be convex or concave.
....
> Is there a public algorithm, and/or C/C++ source code that can test
> the following;

There's a group at UNC that specializes on that sort of stuff:
http://www.cs.unc.edu/~geom/collide/

These are also common issues that arise in computer graphics and 
computational geometry.
http://en.wikipedia.org/wiki/Computational_geometry

I don't know of any simple packages that do all of what you need...  If 
your answers don't have to be precise, its rather straightforward to 
coax OpenGL into answering these question (render a frame, then count 
the remaining pixels)...

 >    * If P1 and P2 intersect
 >      bool IsInterect(P1, P2);

Tessellate both P1 and P2 into triangles; then test pairs of triangles 
from each until you find an intersection (true) or run out of pairs (false).

Most computer graphics libraries have utility functions to automate the 
tessellation of polygons into triangles.  Triangles are the simplest 
shape with area; there are very efficient calculations for intersection 
(just search for "triangle intersection") and area.
http://en.wikipedia.org/wiki/Polygon_triangulation

 >    * If P1 covered by P2 (all vertices and edges of P1 are located in
 > P2)
 >      bool IsCovered(P1,P2);

I don't remember the best algorithm for this, but I think it was based 
on this approach:
P2 is covered by P1 if
- all the vertices in P2 are contained in P1
- the borders of P1 and P2 do not cross

Alternatively, for each triangle in P2, search P1 for the triangles that 
cover it.  The test succeeds if such a cover can be found for all the 
triangles in P2.

 >    * Total area of P1
 >       float AreaOf(P1);

Sum the triangles used to tessellate P1.

 >    * Area of intersection P1 and p2
 >       float AreaOfIntersection(P1,P2);

Sum the area of intersection of overlapping triangles from P1 and P2.

 >    * Bounding box of P1
 >      B1= BoundingBox(P1); (where B1 is a rectangle with 4 vertices)

If you want axis-aligned boxes, this one's easy (take the min/max in 
each dimension).  Non-aligned boxes are another optimization problem, 
perhaps best solved by starting with a convex hull.
http://en.wikipedia.org/wiki/Convex_hull#Planar_case

 >    * Bounding Circle of P1
 >      C1 = BoundingCircleOf(P1); (where C1 defined by center coordiante
 > and radius)

This topic spawned a couple threads on the Mathematica newsgroup.
http://forums.wolfram.com/mathgroup/archive/2004/Aug/msg00276.html
http://forums.wolfram.com/mathgroup/archive/2004/Aug/msg00334.html

The abbreviated version: the optimal bounding circle will intersect two 
or three of your points; the hard part is finding these points 
efficiently.  Again, it helps to have generated a convex hull.  Or 
approximate the solution by centering the circle at the "center of mass" 
and then determining the necessary radius.

Hope that helps,
Daniel
0
D
3/25/2007 4:58:17 AM
Hey Daniel,

MANY THANKs for your informative reply.

Regards,

Albert


0
Albert
3/29/2007 8:52:49 AM
Reply: