View Question
Q: Area of intersection of two polygons ( No Answer,   6 Comments )
 Question
 Subject: Area of intersection of two polygons Category: Computers > Algorithms Asked by: rob12345678-ga List Price: \$50.00 Posted: 11 Aug 2005 06:34 PDT Expires: 10 Sep 2005 06:34 PDT Question ID: 554427
 ```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.```
 There is no answer at this time.

 Subject: Re: Area of intersection of two polygons From: myoarin-ga on 12 Aug 2005 10:25 PDT
 ```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```
 Subject: Re: Area of intersection of two polygons From: mathtalk-ga on 12 Aug 2005 10:37 PDT
 ```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```
 Subject: Re: Area of intersection of two polygons From: rob12345678-ga on 12 Aug 2005 11:46 PDT
 ```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.```
 Subject: Re: Area of intersection of two polygons From: sethahoyt-ga on 13 Aug 2005 00:38 PDT
 ```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.```
 Subject: Re: Area of intersection of two polygons From: doopdoop-ga on 03 Nov 2005 23:40 PST
 ```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.```
 Subject: Re: Area of intersection of two polygons From: bigwal-ga on 28 Mar 2006 17:53 PST
 `Have you been able to resolve this problem?`