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)
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)
There's a group at UNC that specializes on that sort of stuff:
formatting link
These are also common issues that arise in computer graphics and computational geometry.
formatting link
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)...
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.
formatting link
> * 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.
Sum the triangles used to tessellate P1.
Sum the area of intersection of overlapping triangles from P1 and P2.
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.
formatting link
> * 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.
formatting link
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.
PolyTech Forum website is not affiliated with any of the manufacturers or service providers discussed here.
All logos and trade names are the property of their respective owners.