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
<% if( /^image/.test(type) ){ %>
<% } %>
<%-name%>
Correction of a typo; Wrong---> Assume we have two non-intersection polygons Corrected ---> Assume we have two non-self-intersection polygons
Regard,
Albert
<% if( /^image/.test(type) ){ %>
<% } %>
<%-name%>
Albert Goodwill wrote:

...
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
<% if( /^image/.test(type) ){ %>
<% } %>
<%-name%>
Hey Daniel,
Regards,
Albert
<% if( /^image/.test(type) ){ %>
<% } %>
<%-name%>

Site Timeline

• Seeking participants for on-line facial perception experiment

• - previous thread in General Robotics Forum