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

Regards,

Albert

``` 0  Albert
3/23/2007 5:28:12 AM comp.robotics.misc  7077 articles. 0 followers. 3 Replies 354 Views Similar Articles

[PageSpeed] 12

```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
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

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, 0  Albert