Services & Resources / Wolfram Forums / MathGroup Archive

MathGroup Archive 2009

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Re: Polygon Union

I need to make a couple of corrections to my post from yesterday.

Daniel Lichtblau wrote:
> On Jun 6, 2:45 am, "Scot T. Martin" <smar... at seas.harvard.edu> wrote:
>> I've also been thinking about this problem. I use the continental maps
>> that are available through CountryData[], and I'd rather have a continent
>> without an internal political boundaries shown. I've been surprised that
>> this possibility is not a built-in option.
> 
> See last remark below.

I wrote this, then added a final paragraph and did not change this. What 
I meant was the stuff beginning with "For the case of internal boundaries".


>> On Fri, 5 Jun 2009, David Skulsky wrote:
>>> I am looking for a Mathematica function which generates the union of
>>> two (not necessarily convex) polygons.  I found a package on the web
>>> (the Imtek library, I believe) which includes a convex polygon
>>> intersection function, but not a polygon *union* function.  Does
>>> anyone know if such a function is available or, if not, can anyone
>>> suggest an algorithm to implement in Mathematica?
>>> Thanks in advance,
>>> David Skulsky
> 
> Consider a pair of polygons p1 and p2. For the case where boundaries
> might transversally intersect, a reasonable tactic is to iterate over
> vertices of p2 to see which lie in p1, and vice versa. Then look at
> neighbors of such points (that are not themselves inside one and
> bounding the other) to find intersecting segments. This will allow to
> recast as one polygon. Reasonably efficient code for doing the inside/
> outside tests can be found in the MathGroup archives:
> 
> http://forums.wolfram.com/mathgroup/archive/2009/Feb/msg00519.html
> 
> For the case of internal boundaries, you can look for segments that
> get repeated. This should usually work, unless you have, say, Ohio and
> Kentucky both claiming a river right up to the land boundary on the
> other state's side (in that case, instead of looking for segments you
> might look for militias. Actually you can treat this as the
> transversal intersection case.)
> 
> A related issue is when you try to merge polygons that have common
> boundaries, but vertices disagree due to small numeric error. In such
> cases it is useful to do comparisons at precision lower than that used
> in specifying the boundary vertices.
> 
> Daniel Lichtblau
> Wolfram Research

The handling of transversal intersections is not in general correct. If 
we have a pair of neighboring points of p2, say, that both lie in p1, 
that does not mean the entire connecting segment lies inside p1. If you 
are dealing with country boundaries, where individual segments tend to 
be small, this will usually be the case, but for general nonconvex 
polygons it does not necessarily hold. Likewise for neighbors of p2 that 
both lie outside p1: their connecting segment might still intersect the 
boundary of p1. And of course if the edge between a pair of neighbors in 
p2 crosses the p1 boundary, it might be in multiple places.

I do not know what is regarded as best prectice for handling this. An 
approach that strikes me as sensible is related to the inside/outside 
test (URL above) from February. It should work reasonably well if 
individual segments are "small" relative to dimensions of the polygons 
(as is usually the case with, say, map boundaries. And if this property 
does not hold, one can subdivide segments so it will.) Anyway, the idea 
is simply to bin segments in p1 by endpoints, in such a way that it is 
easy to locate all possible p1 segments crossed by any given edge in p2. 
Then test each possible crossing.

The reason for binning is of course to avoid having to test every p1 
segment against every p2 segment. If there are m vertices in p1 and n in 
p2, then the complexity of the preprocessing is O(m+n), and if we assume 
all bins have a small number of segments, the processing complexity is 
also O(m+n). For "reasonable" polygons (ones that do not require 
substantial refinement to make edges "small"), this should be in the 
ballpark of optimal. That is, there might be methods that are t times 
faster, but such that t increases with vertex counts.

Daniel Lichtblau
Wolfram Research
  • Prev by Date: Re: Slow/jerky animations inside manipulate
  • Next by Date: a graph problem-> heptagon analog to the dodecahedron
  • Previous by thread: Re: Polygon Union
  • Next by thread: Re: Polygon Union