I am looking for visual basic 6 compliant code to determine the area
of intersection/overlap (if any) between two 2-D polygons on the same
plane. The polygons can have any number of vertices and will be
supplied by a listing of the x,y coordinates for each vertex. The
order the vertices are listed in is unknown (can be listed in either a
clockwise or counter-clockwise direction).

---

Request for Question Clarification by mathtalk-ga on 12 Aug 2005 05:37 PDT

Hi, rob12345678-ga:

Since you ask specifically for the area of intersection between two
polygons, I assume that the polygon (or polygons) formed by the
intersection is not of immediate interest.  Please advise if this
assumption is incorrect.

You state that it is not known whether the vertices are listed in a
clockwise or counter-clockwise direction.  However I assume you are
implying that the vertices are listed in one or the other order. 
Especially if the polygons are not convex, the order of listing the
vertices is important to the definition of the polygon, although a
clockwise vs. counter-clockwise variation is not a problem.  Please
confirm 1) the polygons are not known to be convex, and 2) that the
order in which the vertices are given for each polygon is either
clockwise or counter-clockwise (though it is not known in advance
which, and may be the same or opposite orientations for the two input
polygons).

regards, mathtalk-ga

---

Clarification of Question by rob12345678-ga on 12 Aug 2005 07:42 PDT

I can compute the area of a polygon, so returning a list (or lists) of
vertices for the polygon(s) formed by this intersection would be
adquate for me to achieve the end result. It also may be useful to
know these intersection polygons in the future, however it is not a
current requirement.

To confirm:

1) the polygons are not known to be convex, 

True.

2) that the order in which the vertices are given for each polygon is either
clockwise or counter-clockwise (though it is not known in advance
which, and may be the same or opposite orientations for the two input
polygons).

True.

In addition if you know of a good resource for similar solutions to
2-D geometric problems, please let me know. Thanks in advance!

---

Request for Question Clarification by mathtalk-ga on 15 Aug 2005 07:50 PDT

Hi, rob12345678-ga:

I took a look at the C code in the second link you posted over the
weekend, and it seems that it should be possible to port it to VB6
within a week or so.

Is it fair to say that performance is less important to you than
robustness of implementation?

regards, mathtalk-ga

---

Clarification of Question by rob12345678-ga on 15 Aug 2005 09:06 PDT

>> it should be possible to port it to VB6 within a week or so.

Sounds great. I'd also like a lay-person level explanation of the
approach as well as documented code if it's not too much to ask.

>> Is it fair to say that performance is less important to you than
robustness of implementation?

Performance is important. Of course, an implementation that produces
incorrect results is of no value. However the computed area can be
inaccurate to say 1% and there can be certain situations where the
result can't be computed (as long as these situations are documented,
highly unlikely, and hopefully detected and reported in the code).
Once that critera is met, the performance becomes the main issue.
Polygons can have up to a few hundred vertices each, and can number in
the thousands. I am essentially overlapping one layer of polygons over
another so there could be a few million pairs of polygons to test.
Although I can check for a possibility of overlap to discard most of
these pairings, runtime is a significant issue.

---

Request for Question Clarification by mathtalk-ga on 20 Aug 2005 20:06 PDT

Given the large number of potential pairs of polygons to test, I can
see that performance is a central issue.  I would therefore have to
recommend an implementation in C with in-line assembly for the most
intensive computational parts.  Even if this is to be called from
Visual Basic 6, implementing the area of intersection in this way
would reasonably be expected to provide a 3x's speed up.

Since this is pretty far off-base from what you were looking for, I'll
post more about this as a free Comment below.

regards, mathtalk-ga

---

Clarification of Question by rob12345678-ga on 25 Aug 2005 13:20 PDT

Hi mathtalk.

I understand that it is better to write the code in C, however I need
it in visual basic. It seems that if you are planning on writing the
code for me, it would be worth more than $50. Let me know.

I don't know what this means:  "I am looking for visual basic 6 compliant code,"
but from what follows, and the very respected Mathtalk-ga clarification:
it seems like we have got an x/y cooridinate system with two sets of
points that can be be identified as belonging to two different
polygons (maybe with "innie" and "outie" vertices) but we know where
all the points are and to which polygon they belong.
It can't be difficult to compute the overlapping area. It is just a
bunch of rectangles and traingles  -
- or haven't I understood at all?   (Please be polite!)
Myoarin

Hi, myoarin-ga:

You are right that, in principle, one can just decompose both polygons
into "disjoint" triangles (though this can be a bit tricky when, as
here, the polygons aren't necessarily convex) and then measure the
overlap between each possible pair of triangles (ie. one from each
polygon).

The application may be one that requires highly optimized code for
performance reasons, and breaking an N-sided polygon into N-2
triangles and an M-sided polygon into M-2 triangles might be too
inefficient, producing O(NM) pairs of triangles to check. 
Nevertheless the triangle-on-triangle approach is a good idea for a
"benchmark" implementation.

regards, mathtalk-ga

FYI, I have found this:

http://www.cmlab.csie.ntu.edu.tw/~jiajing/archives/000034.html

and probably better:

http://www.cap-lore.com/MathPhys/IP/

However, I am not good with C code and wish to find a comparable code
listing in VB. Also the explanation of the procedure in the latter
link is a little above my head. It would be nice to have a better
understanding of the approach as well.

I provided a comment for a very similar question in this category
which is as follows:

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.


Hope that helps.

As I guess you are using this algorithm in a larger context, you may
consider using a commercial polygon library right away.

E.g Algocom Polygon http://www.algorithmic-solutions.com/enalgocomspolygon.htm

It has Visual Basic bindings, and all the necessary routines. The
company is well known in the computational geometry field for good
software, both from an algorithmic and design viewpoint, although I
never worked with this particular piece. And, no, I don't get money
from them.

Have you been able to resolve this problem?