I need some Java code to calculate the area of intersection of two
convex polygons. The polygons are represented as lists (or arrays) of
Points and I'd like a list of points back. Actually I only really need
the area occupied by the intersection - so a floating point number for
the resulting area would be fine. Code needs to be licensable for use
in a commercial product (not GPL)

---

Request for Question Clarification by mathtalk-ga on 30 Jul 2005 10:12 PDT

Hi, jportway-ga:

I'll try to help you find what you are looking for.  Based on the fact
you seek a Java code implementation, my impression is that performance
is  perhaps being subordinate to considerations of portability (and
accuracy!).  Is this impression correct, and are you a Java programmer
yourself?

You state that the input "polygons are represented as lists (or
arrays) of Points" and that either getting the actual (convex polygon)
intersection back (possibly as an empty polygon) or "a floating point
number for the resulting area" will suffice.  Is it assumed that the
order of the Points in such lists are consistent with the order in
which they occur on the polygon (boundary)?

You imply that GPL code cannot be used in a commercial product.  This
is disputed by a large number of firms who use GPL code in their
products, but I'm not arguing the point (I'm not an expert!).  But it
raises the question of whether you prefer licensable (for a fee)
library code to something that might be free.  As far as I know, there
are no "patents" on the basic algorithms for computing intersections
of convex polygons, at least in 2D (Microsoft may have designs on
these!).

So let me lay out some options:

1) I point you to a linear time algorithm for computing the
intersection of two convex polygons, and you write the implementation
yourself in Java.  The implementation becomes your own intellectual
property and no license fees are involved.

2) I point you to Java code that others have posted, which may or may
not be in the public domain.  To some extent it would be up to you to
contact the various authors and determine whether they claim a
copyright in the material, and if so whether the terms of licensing
are mutually acceptable.  Of course I'd point out any posted
information in this regard to expedite your decision/negotiation.

3) I point you to one or more commercial Java libraries that do what
you need, and you determine if the fees and licensing are appropriate
to your needs.

As a starting point, do you have a budget in mind for the licensing fee?


regards, mathtalk-ga

Off the top of my head (without researching the problem), it would
seem that a simple solution would be to break the 2-D region into
smaller sections, much like how street maps (you know, the printed
kind no one uses anymore) have an overlaid grid to locate individual
streets.

Just hash each segment of one polygon into every sub-section it passes
through (can easily be calculated without a search). Then, for each
segment of the other polygon, compare against all segments in the
sub-sections it passes through to determine the points of intersection
between the two polygons.

The trick to making this efficient is to choose a near-optimal level
of granularity for the sub-sections. You do not want too many or too
few segments per sub-section. In general, I think a divide-and-conquer
approach would work well, where you continue to split a given region
in half until there are a small enough number of segments passing
through each region. This would cover cases where more granularity is
required in some regions, but not others.

Hi, I have developed code for this purpose using my custom polygon
class that uses Point2D.Float arrays.

The class is used to calculate polygons of intersection, union, XOR
and also for creating shadows from view points inside polygons.

It also has a feature to calculate area, 'centre' (centre of mass) and
circular and rectangular bounds.  You can call getGeneralPath() on it
to get a GeneralPath object that you can paint with, etc.

The class works so long as the polygon doesn't have sides that cross
each other.  The polygon can have reflexive angles however and can
have many vertices.

The precision is imperfect due to floating point arithmetic and in
special case scenarios where lines intersect over their length.

What would you do with my code and can i be paid for it?