Re: Re: Polygon Union
- To: mathgroup at smc.vnet.net
- Subject: [mg100637] Re: [mg100600] Re: Polygon Union
- From: Daniel Lichtblau <danl at wolfram.com>
- Date: Wed, 10 Jun 2009 05:32:19 -0400 (EDT)
- References: <200906050703.DAA25620@smc.vnet.net> <h0d6qt$sp6$1@smc.vnet.net> <200906090754.DAA25548@smc.vnet.net>
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
- References:
- Polygon Union
- From: David Skulsky <edskulsky@gmail.com>
- Re: Polygon Union
- From: Daniel Lichtblau <danl@wolfram.com>
- Polygon Union