Re: Polygon intersection

On Sat, 6 Sep 2003, Bill Hibbard wrote:

> I'll think about this a bit more.

Clipping an arbitrary non-convex polygon against another is
pretty messy, but all you really need is the are of the
intersection (then compared to the total area of one polygon).
This shouldn't be too hard. To compute the area of polygon A
intersected with polygon B:

1. Pass A and B to DelaunayCustom.fill() which will partition
each into triangles.

2. Clip triangle set A against each triangle of B. To do this,
create a new method (if you do it in I'll
be happy to add it to the system) to clip a set of triangles
against a triangle by three successive calls to DelaunayCustom.clip(),
with the output from one edge clip passed as the input to the
next edge clip (each edge defines a half plane, and the triangle
is the intersection of the three half planes).

3. The result of clipping triangle set A against each triangle
of B will be a big collection of triangles whose disjoint union
is the intersection of polygons A and B. Add up the areas of all
these triangles to get the area of the intersection. You can call
DelaunayCustom.computeArea() to get the area of each triangle.

If you needed the intersection as a set of polygons, the messy
part would be figuring out how all the triangles in the intersection
should be combined to form connected polygons. But you only need
the area. If you want to put the whole computation into a method
in DelaunayCustom, I would be happy to add it to the system.

Let us know if you have any questions or problems.

Good luck,

> On Sat, 6 Sep 2003, Andrew Donaldson wrote:
> > Hi Bill and everyone,
> >
> >
> >    We have an application where we need to know if a polygon intersects
> > another polygon by a 'reasonable amount' - in this case 10%.
> >
> >
> >    The existing Bureau application does this by internally rendering
> > both polygons and testing for pixels being overwritten.
> >
> >
> >    After some head scratching, it seems that this includes a clipping
> > problem. All the google search results were scary, and the clipping I
> > did at uni was the special case of clipping against a view pyramid,
> > which is easier.  We need to clip against an arbitrary polygon.
> >
> >
> >    Looking at DelaunyCustom, there is a clip method, but it says it clips
> > against a half plane (is that like a flat hobbit?).  Has anyone done any
> > work in visad to clip a polygon against another polygon?  Alternately,
> > is there a good way of knowing how much two polygons intersect by?
> >
> >
> >    By the way, some of our polygons are representing state and council
> > boundaries, so they have hundreds of vertices.
> >
> >
> > thanks,
> >
> > Andrew.
> >
> > --
> >   Andrew Donaldson
> >   Email:   A.Donaldson@xxxxxxxxxx                Bureau of Meteorology
> >   Phone:   +61 3 9669 4537            P.O. Box. 1289K/150 Lonsdale St,
> >   Fax:     +61 3 9669 4128                       Melbourne, Australia.
> >
> >
> >