StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p><strong>What I think you should do</strong></p> <p>Do not attempt to do this yourself if you can possibly help it. Instead, use one of the many available polygon intersection algorithms that already exist.</p> <p>I was strongly considering the following codebase on the strength of their demonstration code and the fact that they mentioned their handling of most/all of the weird cases. You would need to donate an amount (of you/your company's choice) if you use it commercially, but it's worth it to get a robust version of this kind of code.</p> <p><a href="http://www.cs.man.ac.uk/~toby/gpc/" rel="nofollow noreferrer">http://www.cs.man.ac.uk/~toby/gpc/</a></p> <p>What I actually did was to use a polygon-intersection algorithm that is part of the Java2D libraries. You can possibly find something similar in MS's own C# libraries to use.</p> <p>There are other options out there as well; look for "polygon clipper" or "polygon clipping", since the same basic algorithms that handle polygon intersection also tend to be usable for the general clipping cases.</p> <p>Once you actually have a polygon clipping library, you just need to subtract polygon B from polygon A to get your first piece of output, and intersect polygons A and B to get your second piece of output.</p> <p><strong>How to roll your own, for the hopelessly masochistic</strong></p> <p>When I was considering rolling my own, I found the Weiler-Atherton algorithm to have the most potential for general polygon-cutting. I used the following as a reference:</p> <p><a href="http://cs1.bradley.edu/public/jcm/weileratherton.html" rel="nofollow noreferrer">http://cs1.bradley.edu/public/jcm/weileratherton.html</a></p> <p><a href="http://en.wikipedia.org/wiki/Weiler-Atherton" rel="nofollow noreferrer">http://en.wikipedia.org/wiki/Weiler-Atherton</a></p> <p>The details, as they say, are too dense to include here, but I have no doubt that you'll be able to find references on Weiler-Atherton for years to come. Essentially, you split all the points into those that are entering the final polygon or exiting the final polygon, then you form a graph out of all the points, and then walk the graph in the appropriate directions in order to extract all the polygon pieces you want. By changing the way you define and treat the "entering" and "exiting" polygons, you can achieve several possible polygon intersections (AND, OR, XOR, etc.).</p> <p>It's actually fairly implementable, but like with any computational geometry code, the devil is in the degeneracies.</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