|
Posted by D Herring on March 25, 2007, 12:58 am
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
| 
Yahoo! 
Google 
Windows Live 
del.icio.us 
digg 
Netscape 
XML site map
Corrected ---> Assume we have two non-self-intersection polygons