StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>You could do this iteratively and produce a set of connected components (instead of always just a single connected component):</p> <ol> <li>Put all polygons in an "open" list. Initialize a <em>components</em> list to empty.</li> <li>While <em>open</em> is not empty: <ul> <li>Remove a polygon <em>p</em> from <em>open</em> and set flag <em>changed</em> to true.</li> <li>Repeat while <em>changed</em> is true: <ul> <li>set <em>changed</em> to false</li> <li>for each polygon <em>q</em> in <em>open</em>: <ul> <li>if <em>q</em> intersects <em>p</em>, remove <em>q</em> from <em>open</em>, set <em>changed</em> to true, and set <em>p</em> to the union of <em>p</em> and <em>q</em>.</li> </ul></li> </ul></li> <li>add <em>p</em> to <em>components</em>.</li> </ul></li> </ol> <p>At the end, <em>components</em> will consist of all the non-intersecting, connected components that can be formed by union of the input polygons. In your posted sample, it should produce a single polygon.</p> <p>This is not the most efficient approach (see the algorithms in the link posted by Ricky Bobby), but it has the advantage of simplicity. Provided you aren't dealing with hundreds of polygons, it should perform just fine.</p> <p>P.S. As @japreiss points out, a union can have holes even if none of the input polygons has a hole, even if the inputs are all convex polygons. If the inputs can be concave, then even a union of 2 polygons can have a hole. Does your 2-polygon algorithm handle that already?</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload