File: algo.html

package info (click to toggle)
librnd 4.4.0-1
links: PTS, VCS
area: main
in suites: forky, sid
size: 12,812 kB
sloc: ansic: 126,990; sh: 2,602; makefile: 2,145; awk: 7
file content (635 lines) | stat: -rw-r--r-- 28,413 bytes
parent folder | download | duplicates (2)
<html>
<body>
<center>
<H1> A CLOSED SET OF ALGORITHMS FOR PERFORMING SET OPERATIONS ON POLYGONAL REGIONS IN THE PLANE... </H1>
<h2> ... for coders </h2>
</center>
<h3> Preface to this interpretation </h3>
<dl>
<p>
<a href="https://web.archive.org/web/20160418014630/http://www.complex-a5.ru/polyboolean/downloads/polybool_eng.pdf">
The excellent paper</a> by <i>Michael V. Leonov and Alexey G. Nikitin</i> at the
<i>A. P. Ershov Institute of Information Systems, Siberian Branch of Russian</i>
back from the 1990s clearly and precisely presents a surprisingly simple
algorithm for the problem also called <i>polygon clipping</i>. Besides describing
the algorithm, the paper also gives accurate definitions and an estimation on
runtime.
<p>
While the paper, in its original form, is already rather useful, I've found
that as a coder, I have a hard time processing some parts of it, because
of the following factors:
<ul>
	<li> mathematically precise, but often complex wording for expressing otherwise simple concepts
	<li> condensed mathematical expressions
	<li> file format: the original pdf seems to be broken (I had two different pdf reader implementation choke on it)
	<li> while figures and example cases are chosen very wisely to present interesting cases, more labeling and coloring could make it easier to understand them
</ul>
<p>
This document is an English-to-English translation of the original paper, with
the intended target audience being coders who want to understand and implement
the algorithm but do not wish to prove or verify the maths behind it.
In fact, this document is more of <i>my personal interpretation</i>
than a translation.
<p>
This document closely follows the structure of the original document, so
that the two can be read in parallel.
<p>
I heavily simplified or even skipped parts that are very important for
mathematical correctness but not required for implementing the algorithm in
code. Instead of the mathematical notations, beyond the most
basic operators I use a named operator function; instead of single letter
variables, I use multiple-letter ASCII-only variable names (no greek letters).
Instead of condensing the formulas, I rather make them more verbose, explaining
what each variable is for. These modifications may degrade pedantic mathematical
correctness, but I believe it makes it easier to digest the information on
first pass.
<p>
I've also redrawn all illustrations so that they have more labels, more colors;
more information explicitly encoded in them that otherwise could have been
implied or figured from context.
<p>
When an algorithm is specified in pseudo-code or as expressions in tables,
the original paper uses a Pascal-like syntax mxed with non-ASCII math notations,
this paper uses an ASCII-only C-like syntax.
<p>
Finally, this document is plain, hand written html, which is much more portable
than pdf.
</dl>


<h3> Abstract </h3>
<p>
See the original paper.

<h3> Introduction </h3>
<p>
See the original paper.
<p>
The basic concept of the algorithm is simple: insert a new vertex (corner)
in the contour of polygons ('A' and 'B') where they intersect (marked as
p1 and p2 on Figure 1). Then split up the polyline of 'A' into contour sections
between intersection points, name these contour sections CA1, CA2. Do the same
on 'B', resulting contour sections are called CB1 and CB2.
<p>
<center>
<img src="fig1.svg" width="800px">
<br>
Figure 1. Intersection polygons.
</center>
<p>
With this the problem is converted from geometry
to topology. A few simple properties can be defined, such as whether
points left of a contour section are within 'A' or 'B'. A contour section is "boring",
since it does not have any intersection thus properties can not change. All
the algorithm needs to do is figuring which contour sections to include in
the result (and whether to reverse their direction so the result is
a continous loop of polyline). For example an union operator will keep CA1
and CB1, an intersection will keep CA2 and CB2 and an "A-B" will keep
CA1 and CB2 (with reversed direction).


<h3> Basic definitions </h3>
<p>
Our coordinate system is a 2d Euclidian plane with the usual Cartesian system.
A point is specified by its x;y coordinates, but points are not stored, only
used as a reference for this document. A vertex is also specified by its x;y
coordinates and is stored in polylines which are stored in [polygon] regions in turn.
<p>
(Definition 1 and 2)
<p>
A [polygon] <i>region</i> consists of zero or more <i>islands</i>.
(The original paper calls this <i>polygon</i>; this document will call it
an island to reduce confusion with similar terms.)
An island is an outer polyline and zero or more inner polylines (which act
as cutouts). A <i>polyline</i> is an ordererd, cyclic list of vertices,
containing at least 3 vertices.
<p>
A <i>contour</i> is a section of a polyline that contains 1 or more edges.
(Unlike in the original paper, this document never uses contour as a synonym
a whole polyline but only to reference a section of the polyline between two
intersections. In the corner case when the polyline has no intersection,
the contour is the whole polyline.)
<p>
An <i>edge</i> is a straight line segment<sup><a href="#note1">1</a></sup>
that starts from such a vertex and ends at the next vertex; an edge is
referenced by its starting vertex. This also means edges are directed from
start vertex to end vertex. There are no zero-legth edges.
<p>
Given such a directed edge, there is a left neighborhood and a right neighborhood
(of imaginary points) next to the edge. (This concept is used only to decide
if something is left or right to the edge.)
<p>
The <i>straight</i> ordering of vertices or edges within a polyline is
counter-clockwise (CCW), the <i>reverse</i> ordering is clockwise (CW).
<p>
<center>
<img src="fig2.svg" width="800px">
<br>
Figure 2. Neighborhoods. a) is an edge E with its left and right neighborhood;
b) shows a vertex on the right between two edges of an outline, dividing the
plane into an inner neighborhood and an outer neighborhood (of the vertex and
of the edges).
</center>
<p>
A <i>high degree</i> vertex is shared by the endpoints of more than two edges.
<p>
(Definition 3)
<p>
Given a polyline, there's an <i>inner neighborhood</i> (all points inside
the polyline) and an <i>outer neighborhood</i> (all points outside).
A valid polyline can be self touching (a vertex between
two edges falling on a 3rd edge of the polyline) but can not be self
intersecting.
<p>
The outline of an island is always <i>straight</i> (CCW) while cutouts
are always <i>reversed</i> (CW). Each island has exactly one outline, and that is
the outmost polyline of the island. Polylines of an island do not touch or
intersect other polylines within the island.
<p>
<center>
<img src="fig3.svg" width="800px">
<br>
Figure 3. The left region has one outer polyline and one self-touching inner
(cutout) polyline. The middle region has two islands of a single outer
polylines each. The third region has a rectangular island with a trangular
cutout and a second triangular island placed within that cutout.
</center>

<p>
Naming convention: this document will name vertices as V or Vsomething,
edges as E or Esomething, and index them starting from 0 from an
arbitrarily chosen vertex on the polyline, so that (for example) Efoo[5]
is the edge that starts at Vfoo[0] and ends at Vfoo[1]. The last edge of
a polyline of n vertices, E[n-1] is between V[n-1] and V[0]. Polylines
are named Psomething; when indexed, Pfoo[0] is the outline, indices starting
from 1 refer to cutouts.
<p>
A <i>sector</i> is an imaginary area, a  neighborhood of points between
two adjacent edges of a polyline. It is roughly the points within the
triangle formed by the two edges and a third, virtual line connecting
their non-incident ends. (Sectors are not calculated but are used in the
explanation and in conceptual relations between edges and polylines.)

<h3> The algorithm </h3>
<p>
Input:
<ul>
	<li> A and B: two regions
	<li> op: an operation (one of: <i>union</i>, <i>intersection</i>, <i>difference</i>, <i>xor</i><sup><a href="#note1">2</a></sup>)
</ul>
Output: a region R; R = op(A, B).
<p>
The algorithm is split into four steps:
<ul>
	<li> Step 1. Processing of the edge intersections.
	<li> Step 2. Edge and contour labeling.
	<li> Step 3. Collecting the resulting contours.
	<li> Step 4. Placing the resulting contours in R.
</ul>

<p>
<center>
<img src="fig4.svg" width="800px">
<br>
Figure 4. The two input regions and the protoype for result R, with all edges
included. The vertex circled on the three regions are in the same point on
the plane.
</center>



<h3> Step 1: processing edge intersections </h3>
<p>
Find all intersections between edge objects of A and B (ignoring the
shared endpoint of adjacent edges within a polyline but not ignoring
other intersections happening between edges of the same polyline):
<ul>
	<li> for an edge-edge mid intersection, insert a new vertex in both regions, at the intersection point, splitting the edge of both objects
	<li> if a vertex of an island is on the edge of another, split that edge inserting a new vertex in the intersection point
	<li> if two edges overlap, split them ensuring there's a vertex on the start and end of the overlap
	<li> (if two vertices fall on the same point, don't do anything)
</ul>
<p>
Figuer 5 shows the result. Vertices inserted for intersections are marked
with bold. Input regions A and B are arranged so that the circled vertex
(a5, B2, B9), marked with y in the result, is a common point. Note: a5 is
on an inner (cutout) polyline in A, while B consists of a single outer polyline
in which B2 and B9 happens to be on the same point in space (self touching
polyline).
<p>
<center>
<img src="fig5.svg" width="800px">
<br>
Figure 5. The two input regions with inserted cross-vertices marked with bold
and the protoype for result R, with all edges included.
</center>


<p>
By now any intersection has an explicit vertex on all related polylines.
If there are multiple vertices falling on the same point, that means there is
an intersection/touching there and all vertices on that point are called <i>
cross-vertices</i>.
<p>
Comment: for each such point of intersection there are at least two
cross-vertices for such a point.
<p>
Comment: this process <b>does change the structure of input regions</b>, when it is creating new vertices,
which means if the original regions are to be preserved, a copy needs to be made.
However, this process (<b>in theory</b><sup><a href="#note3">3</a>, <a href="#note4">4</a></sup>)
does not change the shape/meaning/topology of the input regions.)
<p>
Take each cross-vertex V[i], where i is the index of the given vertex within
the polyline. There will be a <i>previous edge</i> Ep that
ends on that vertex and a <i>next edge</i> En that starts at that vertex.
Allocate two <i>cross-vertex descriptors</i> (CVD), Dp and Dn, and assign them
to Ep and En respectively (cross-linking the corresponding E and D with pointers
in both directions). A CVD contains angle<sup><a href="#note5">5</a></sup> information and flags.
<p>
For every intersection point, collecd all CVDs into a cyclic list called
the <i>connectivity list [of that point]</i>. The connectivity list is ordered
by the angle of the CVDs (fig. 6). Order of equal angles is unspecified.
<p>
<center>
<img src="fig6.svg" width="800px">
<br>
Figure 6. Cross linking CVDs in the point circled on fig. 5; top cyclic list
is the outer polyline of region B, bottom cyclic list is the inner polyline
of region A; middle is the cyclic list of DVDs for this point, sorted by
angle; green arrows represent cross-linking-pointers between the cross vertices
in that point (B2, B9 and a5) and the corresponding CVDs.
</center>
<p>
Comment: for a geometric point, like the one curcled in fig. 5, there is
only one <i>connectivity list</i> and each cross vertices linked to the
CVDs of that <i>connectivity list</i> are in that point. The same cross
vertices can not be linked to any other <i>connectivity list</i>, because
that other <i>connectivity list</i> would be for a different point.


<h3> Step 2. Edge and contour labeling </h3>
<p>
Let Pc be the outer contour of either input region A or input region B. Let Pm
be the outer contour of the other input region.
<p>
(Predicate 1.) After the first step:
<ul>
	<li> Any pair of edges of A and B intersect at their endpoints (and
	     may or may not overlap, but if they overlap, they overlap in full
	     length)
	<li> Every edge of Pc:
		<ul>
			<li> either overlaps with an edge in Pm (and is called a <i>shared edge</i>)
			<li> or lies fully inside Pm (except for an endpoint maybe)
			<li> or lies fully outside Pm (except for an endpoint maybe)
		</ul>
	<li> if Pc does not have any cross-vertex, it is either fully inside Pm or
	     is outside of Pm
</ul>
<p>
The label on an edge E (stored as E.flags) of Pc is one of:
<ul>
	<li> INSIDE: when E is inside Pm
	<li> OUTSIDE: when E is outside Pm
	<li> SHARED1: when E overlaps with an edge from Pm that, and the two edges have the same direction
	<li> SHARED2: when E overlaps with an edge from Pm that, and the two edges have different direction
</ul>
<p id="pc_flags">
The label of Pc (stored as Pc.flags) is one of:
<ul>
	<li> ISECTED: if it contains at least one cross-vertex
	<li> INSIDE: if it has no cross-vertex and it is fully inside Pm
	<li> OUTSIDE: if it has no cross-vertex and is outside of Pm
</ul>

<h4>Algorithm for edge (and polyline) labeling</h4>
<ul>
	<li> 1. If Pc does not contain any cross-vertice: label Pc INSIDE or OUTSIDE<sup><a href="#note6">6</a></sup>. Do not label edges of Pc.
	<li> 2. If Pc contains at least one cross-vertex: label Pc ISECTED, and label
	     its each edge E[i] (i is between 0 and n, n is the number of vertices in Pc):
	<ul>
		<li> 2.1. if E does not contain cross-vertices at its endpoints:
			<ul>
				<li> 2.1.2. if i == 0: if starting vertex lies inside Pm label E[i] INSIDE, else label E[i] OUTSIDE
				<li> 2.1.1. if i != 0: copy label value from E[i-1]
			</ul>
		<li> 2.2. if E contains 1 or 2 cross-vertices at its endpoints:
			<ul>
				<li> 2.2.1. there is an overlapping edge in Pm that has the same starting point as E and the same ending point as E: label E as SHARED1
				<li> 2.2.2. there is an overlapping edge in Pm that has the same starting point as the endpoint of E and the same ending point as the start point of E: label E as SHARED2
				<li> 2.2.3. Pc's cross-vertices connectivity lists do not contain any vertex from Pm: C touches itself but doesn't intersect M; jump to 2.1
				<li> 2.2.4. Pc's cross-vertices connectivity lists contains vertices (called Vm[j]) from Pm:
					<ul>
						<li> take the <i>sector</i> defined by Vm[j-1], Vm[j] and Vm[j+1]
						<li> check, using the angle of E: if E is inside that <i>sector</i>, label E as INSIDE, else label E as OUTSIDE (see Fig. 7).
					</ul>
			</ul>
	</ul>
</ul>
<p>

<p>
<center>
<img src="fig7.svg" width="400px">
<br>
Figure 7. Deciding if an edge being labeled is INSIDE or OUTSIDE of region M
</center>

<h3> Step 3. Collecting the resulting contours </h3>
<p>
An essential idea is that the polylines of R are collected using edge and
polyline labels instead of using coordinates<sup><a href="#note7">7</a></sup>.

<h4> rules for edge inclusion in result </h4>
<p>
Consider an edge E belonging to a pline in either input region A or B. Let NL(E)
be the left neighborhood of E and NR(E) be the right neighborhood of E, where
neighborhood is a theoretical construction and as a simplifiation can
be considered to consists of arbitrary points very close to the edge. Such a
neighborhood is either fully inside or fully outside of A (or B).
<p>
The rules for inclusion of edge E is described in table 1 and actions
described in Table 1b.
<p>

<table border=1 cellspacing=0>
	<tr><th> &nbsp; <th colspan=2> Edge labels <th colspan=4> action per operator
	<tr><th> &nbsp; <th colspan=2> &nbsp;      <th> union <th>inters. <th>diff. <th>xor

	<tr><th> 1. <td> <img src="t1_1.svg" width=250px> <td> E is in input region A, E's label is OUTSIDE, NL(E) is inside input region A, NR(E) is not inside any region.
      <td> A+S <td> O   <td> A+S <td> A+S

	<tr><th> 2. <td> <img src="t1_2.svg" width=250px> <td> E is in input region B, E's label is OUTSIDE, NL(E) is inside input region B, NR(E) is not inside any region.
      <td> A+S <td> O   <td> O   <td> A+S

	<tr><th> 3. <td> <img src="t1_3.svg" width=250px> <td> E is in input region A, E's label is INSIDE, NL(E) is inside both input regions A and B, NR(E) is inside input region B.
      <td> O   <td> A+S <td> O   <td> A+R

	<tr><th> 4. <td> <img src="t1_4.svg" width=250px> <td> E is in input region B, E's label is INSIDE, NL(E) is inside both input regions A and B, NR(E) is inside input region A.
      <td> O   <td> A+S <td> A+R <td> A+R

	<tr><th> 5. <td> <img src="t1_5.svg" width=250px> <td> E from region A is overlapping edge F from region B and is labeled SHARED2; NL(E) is inside input region A, NR(F) is inside input region B. Pick either E or F for inclusion, use E's original direction for straight.<sup><a href="#note8">8</a></sup>
      <td> O   <td> A+S <td> O <td> O

	<tr><th> 6. <td> <img src="t1_6.svg" width=250px> <td> E from region A is overlapping edge F from region B and is labeled SHARED1; NL(E)==NL(F) is inside input both regions A and B, NR(E)==NR(F) is not inside either input region. Pick either E or F for inclusion.<sup><a href="#note8">8</a></sup>
      <td> A+S <td> O   <td> A+S <td> O
</table>
<center><p><i>Table 1.</i></p></center><br><br>


<table border=1 cellspacing=0>
	<tr><th>action ID <th> description
	<tr><td>A+S       <td> Add Straight: include edge in result region using its original direction
	<tr><td>A+R       <td> Add Reverse:  include edge in result region inverting its original direction (swap start and end vertices)
	<tr><td>O         <td> Omit: do not include edge in result region
</table>

<center><p><i>Table 1b.</i></p></center><br><br>

<p>
Comment: In other words, according to the above table, E is added in the resulting R:
<ul>
	<li> 1. when NL(E) is inside R and NR(E) is outside of R, the E is added with its original direction (fig. 1. example: union, case 1: edge is part of CA1)
	<li> 2. when NL(E) is outside R and NR(E) is inside of R, the E is added with reverse direction (fig. 1. example: xor, case 5: edge is part of CB2)
	<li> 3. when both NL(E) and NR(E) are outside R, E is not added (fig. 1. example: difference, case 2: edge is part of CB1)
	<li> 4. when both NL(E) and NR(E) are inside R, E is not added (fig. 1. example: union, case 5: edge is part of CB2)
</ul>
<p>
Comment: For shared edges only one of the edges is added.

<h4> jumping rules at intersections </h4>
<p>
If the collect step reaches a cross-vertex, that means we have reached an
intersection where more than 2 vertices (4 or more edges) meet. The number
of CVDs (descriptors from step 1) is twice the number of vertices at that
point. Using the <i>connectivity list</i> of step 1, that also means we have
a set of edges ordered by angle. Let each edge of this set be F(j), where
j is between 0 and length of the point's <i>connectivity list</i> minus 1.
<p>
Points in the <i>sector</i> between F[j] and F[j+1] are either all inside
or outside of region A and/or B. If the points of two neigbouring sectors
are in the result R, by definition 3 their outer polyline contour will be
the same.
<p>
Using this rule, we loop over cross-linked edges F[] with j until we find
an edge that satisfies the above rule. In other words, we jump to the
closest (in angle) edge that would make up a polyline that includes 
all the same-polarity neighboring sectors, using the rules detailed below.

<h4> The collecting algorithm </h4>
<p>
The same algorithm is used for all operations, except for some differences
in inclusion rules.
<p>
Let Pc be the polyline currently being considered. The label of Pc is stored
in Pc.flags and the label of an edge E is stored in E.flags. Direction
FORWARD means the original direction (of E or Pc), BACKWARD means reversed
direction.
<p>
1. The simpler case is when Pc.flags != <a href="#pc_flags">ISECTED<a>,
which means the polyline has no intersection. In this case whether Pc
is included in R and whether it is reversed depends on conditions described
in Table 2.

<p>
<table border=1 cellspacing=0>
	<tr><th>op      <th> is Pc included?                               <th> direction
	<tr><td>union   <td> Pc.flags == INSIDE                            <td> FORWARD
	<tr><td>inters. <td> Pc.flags == OUTSIDE                           <td> FORWARD
	<tr><td>diff.   <td> (Pc is in region A) && (Pc.flags == OUTSIDE)  <td> FORWARD
	<tr><td>diff.   <td> (Pc is in region B) && (Pc.flags == INSIDE)   <td> BACKWARD
	<tr><td>xor     <td> Pc.flags == OUTSIDE                           <td> FORWARD
	<tr><td>xor     <td> Pc.flags == INSIDE                            <td> BACKWARD
</table>

<center><p><i>Table 2.</i></p></center><br><br>


<p>
2. If Pc.flags == <a href="#pc_flags">ISECTED<a>, the polyline intersects
with another polyline. We need to find all edges in Pc which resulting
contour section can start from. n is the number of vertices in Pc,
E[] are edges of Pc; each E has a field called Mark that inidicates if
E has been included in a resulting contour already (it is set to false
initially on all E[]); v[] is each vertex in the polyline.
The algorithm for starting edges is:
<pre>
for(i=0; i &lt; n; i++) {
	if (EdgeRule(E[i], &dir) && !E[i].Mark) {
		contour r; /* a contour section is a list of edges */
		if (dir == FORWARD)
			r = Collect(v[i], dir);
		else
			r = Collect(v[i+1], dir);
		include_into_a_set_of_resulting_contours(r);
	}
}
</pre>

Function <b>bool EdgeRule(edge E, enum *dir)</b> is the
edge inclusion rule for currently performed operation (see Table 3). Argument
dir is an output with value FORWARD or BACKWARD.

<p>
<table border=1 cellspacing=0>
	<tr><th>op      <th> how to include E in the result R                           <th> direction
	<tr><td>union   <td> (E.flags == OUTSIDE) || (E.flags == SHARED1)               <td> FORWARD
	<tr><td>inters. <td> (E.flags == INSIDE) || (E.flags == SHARED1)                <td> FORWARD
	<tr><td>diff.   <td> (E in A) && (E.flags == OUTSIDE) || (E.flags == SHARED2))  <td> FORWARD
	<tr><td>diff.   <td> (E in B) && (E.flags == INSIDE) || (E.flags == SHARED2))   <td> BACKWARD
	<tr><td>xor     <td> E.flags == OUTSIDE                                         <td> FORWARD
	<tr><td>xor     <td> E.flags == INSIDE                                          <td> BACKWARD
</table>

<center><p><i>Table 3.</i> EdgeRule(E, dir)</p></center><br><br>

<pre>
contour Collect(vertex v, enum dir)
{
	edge E, Esh, Enext;
	contour r = alloc_empty_contour();

	do {
		add_vertex_to_contour(r, v);
		if (dir == FORWARD)
			E = edge_next_to(v);
		else
			E = edge_prev_to(v);
		E.mark = true;
		if ((E.flags == SHARED1) || (E.flags == SHARED2)) {
			Esh = get_edge_shared_with(E);
			Esh.mark = true;
		}
		if (dir == FORWARD)
			v = vertex_next_to(v);
		else
			v = vertex_prev_to(v);
		if (is_cross_vertex(v))
			Jump(&amp;v, &amp;dir);

		/* look at the next edge to terminate; this part was not well specified
		   in the psudo-code of the original paper */
		if (dir == FORWARD)
			Enext = edge_next_to(v);
		else
			Enext = edge_prev_to(v);
	} while(!Enext.mark)
	return r;
}

void Jump(vertex *v, enum *dir)
{
	if (*dir == FORWARD)
		d = prev_D_in_CW(Dp[v]);   /* DP[v] is the previous on the connectivity list of v */
	else
		d = prev_D_in_CW(Dn[v]);   /* DP[v] is the previous on the connectivity list of v */

	for(;;) {
		edge e = edge_of_descriptor(d);
		if (!e.mark && EdgeRule(e, &newdir)) { /* EdgeRule(): see Table 3 */
			*v = vertex_of_descriptor(d);
			if (edge_is_next_to_vertex(e, *v) && (newdir == FORWARD)) ||
			   (edge_is_prev_to_vertex(e, *v) && (newdir == BACKWARD)) {
				*dir = newdir;
				return;
			}
		}
		d = prev_D_in_CW(d);
	}
}

/* prev_D_in_CW(Din) is the neatest D to Din in clockwise direction */
</pre>

<p>
Figure 9 shows the resulting contour segments for the four operations on the
example fom Figure 4:
<ul>
	<li> <i>union</i>: singe island (one outer pline) with two inner plines (holes)
	<li> <i>intersection</i>: two islands (one outer plines), no inner plines (holes)
	<li> <i>difference</i>: two islands (one outer plines), no inner plines (holes)
	<li> <i>xor</i>: thre islands (one outer plines), no inner plines (holes)
</ul>

<p>
TODO: fig 9

<H3> Placing the resulting contours in R </H3>
<p>
After the steps above, we have a set of plines to be included in R. For each
outer (CCW) pline a new island is created in R; then each inner (CW) pline,
which are stored on a separate list, are placed within the smallest island
they are within.

<H2> The analysis of the efficiency </h2>
<p>
See the original paper.

<H2> Conclusion </h2>
<p>
See the original paper.

<H2> References </h2>
<p>
See the original paper.


<hr>

<h3> Notes </h3>
<p>
These notes are not in the original paper, but are collected by the author
of this document on the basis of interpretation of the original paper and
experience with an implementation of this algorithm in pcb-rnd.

<p id="note1">1. While the original paper deals with lines only,
I believe the algorithm would work with any non-self-intersecting curve
object in place of a straight line segment. Some parts of the algorithm
depend on having at least 3 vertices in a valid polyline. This assumption
could be violated by using non-linear objects. For example with circular arcs
it's easily possible to have a 2-object "polyline", or even a single-object
one (a full circle). These corner cases can easily be avoided by splitting up
such objects, at arbitrary points, into 2 or 3 edges.

<p id="note2">2. The xor operation is called "symmetrical difference" in
the original paper.

<p id="note3">3. In practice it does, due to finite precision/resolution of
number representations with common programming practices. If vertex
coordinates are integers, intersection of two sloped edges will rarely fall
onto integer coordinates. Inserting a new vertex at the nearest integer coords
will slightly change the input region because instead of a single straight line
at a specific slope, the result is two slightly differently sloped lines. Using
floating point numbers instead of integers does not solve the problem either,
because the numbers that can be represented are sill finite, so the intersection
will likely fall in between two such numbers and the same rounding has to be done,
and the same type of error is introduced.

<p id="note4">4. The error introduced in note 3 can be significant: slightly
changing the slope of (a section of) an edge that had a touching vertex
from another island can convert that touching into a full intersection or
no touching, and this does change the topology of the problem.

<p id="note5">5. This does not have to be a real angle; anything that yields
the same ordering for a set of edges at a cross-vertex's point as if the
edges were ordered by true angle will work the same. A suitable cheaper
metric is the 0..1 normalized slope of the edge (e.g. dx/dy) combined
with the quadrant in which the edge falls, so that the result is between 0..4.

<p id="note6">6. It is enough to determine if one random vertex of Pc is
inside or outside, the rest of the vertices must be the same, because
no cross vertex means no intersection between Pc and Pm.

<p id="note7">7. This means the algorithm is <i>topological</i>: in step 1 it deals
with coordinates to determine intersections and it inserts new vertices
at the intersections. After that step the whole algorithm is only about linearly
iterating over lists and sometimes deciding where to go at intersections, but all
these are done purely on the topological information (<i>order</i> of points, CVDs, 
left-of/right-of, previous-of/next-of, inside/outside concepts).

<p id="note8">8. Since there can not be overlapping edges within a single
region, any overlap (any SHARED edge) can happen only between A and B edges,
and there will always be exactly two participants, one edge from A and another
edge from B. Since their endpoints are always the same, we are free to pick
either one of them for inclusion in result.