Services & ResourcesWolfram ForumsMathGroup Archive

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

Re: Polygon Union

• To: mathgroup at smc.vnet.net
• Subject: [mg100600] Re: Polygon Union
• From: Daniel Lichtblau <danl at wolfram.com>
• Date: Tue, 9 Jun 2009 03:54:08 -0400 (EDT)
• References: <200906050703.DAA25620@smc.vnet.net> <h0d6qt$sp6$1@smc.vnet.net>

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.


> 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

• Follow-Ups:
  • Re: Re: Polygon Union
    • From: Daniel Lichtblau <danl@wolfram.com>

• References:
  • Polygon Union
    • From: David Skulsky <edskulsky@gmail.com>