Vectorial non-zero fill filter
McSeem
My question is rather complex (from my point of view) and I really hope
you can help me.
When filling polygons there are two fill rules, even-odd (AKA
alternating) and non-zero (AKA winding). These rules are defined in
SVG:
http://www.w3.org/TR/SVG11/painting.html#FillProperties:
Non-zero:
This rule determines the "insideness" of a point on the canvas by
drawing a ray
from that point to infinity in any direction and then examining the
places
where a segment of the shape crosses the ray. Starting with a count of
zero,
add one each time a path segment crosses the ray from left to right and
subtract one each time a path segment crosses the ray from right to
left. After
counting the crossings, if the result is zero then the point is outside
the
path. Otherwise, it is inside. The following drawing illustrates the
nonzero
rule:
http://www.w3.org/TR/SVG11/images/painting/fillrule-nonzero.png
Even-odd:
This rule determines the "insideness" of a point on the canvas by
drawing a ray
from that point to infinity in any direction and counting the number of
path
segments from the given shape that the ray crosses. If this number is
odd, the
point is inside; if even, the point is outside. The following drawing
illustrates the evenodd rule:
http://www.w3.org/TR/SVG11/images/painting/fillrule-evenodd.png
The task is to remove unnecessary edges from a given polygon (or
poly-polygon),
preserving the non-zero rule and the directions of original polygons.
Here's the illustration:
http://antigrain.com/stuff/non-zero1.png
In case 1 we don't remove anything. In case 2 we remove the whole inner
triangle, because in case of non-zero fill it doesn't affect the result
anyhow.
Case 3 is difficult. Here we can do in three different ways.
1) Not doing anything. The question is how to define the criterion of
"not
doing anything". I suspect it's a very difficult task and for now we
discard
this variant.
2) Produce a poly-polygon, like in figure 3d. Here we will have two
polygons,
ABCDEF and CGHE.
3) Produce a single polygon: ABCGHECDEF.
Anyway, we can't repeat any edge twice or more, but we can duplicate
vertices.
Case 4 is equivalent to the "OR" operation. Case 3 is "XOR". It seems
like we
can use classical Constructive Area Geometry, (OR, AND, SUB, XOR), for
example,
this one: http://www.cs.man.ac.uk/aig/staff/alan/software
But it's more complex than that:
http://antigrain.com/stuff/non-zero2.png
Here we have a poly-polygon that consists of a triangle and
self-intersecting
quadrangle (ABCD). As the result we should have the picture on the
right. In
one case we can have a poly-polygon: ABCDEFGH, IJE, JKG. In the other
case a
single polygon will also do: ABCDEIJEFGJKGH (phew! looks correct). The
single
polygon is better but it can compicate the algorithm a lot, so that, a
poly-polygon is also suitable.
Here's another case:
http://antigrain.com/stuff/non-zero3.png
The algorithm should remove self-intresecting areas of ABCDEF and
produce just
a triangle, preserving the directions of the polygons. Here we can see
that the classical boolean operations (AND, OR, SUB, XOR) won't help.
So, any ideas, links, thoughts are highly appreciated!
McSeem
http://antigrain.com
hoff...@fho-emden.de
this is a well known problem, as described in the
PostScript Language Reference Manual.
Different rules deliver different results e.g. for
the star or the donut, as demonstrated.
One solution is the strict definition of an 'outer
contour', as defined by this algorithm:
1. Find a starting point on the contour which is
not inside e.g. by searching by a scanline from
far left (edge of bounding box).
2. Go once around in ccw direction and go always
to the right at a bifurcation.
This delivers a contour without holes, which can be
treated by any of the standard methods.
Here it's shown for pixels:
http://www.fho-emden.de/~hoffmann/inside.jpg
It should be possible to apply the strategy to vectors.
Any other strategy would depend on the image content.
Best regards --Gernot Hoffmann
McSeem
> contour', as defined by this algorithm:
> 1. Find a starting point on the contour which is
> not inside e.g. by searching by a scanline from
> far left (edge of bounding box).
> 2. Go once around in ccw direction and go always
> to the right at a bifurcation.
> This delivers a contour without holes, which can be
> treated by any of the standard methods.
> Here it's shown for pixels:
> http://www.fho-emden.de/~hoffmann/inside.jpg
Thanks Gernot!
Yes, finding the "outermost" contour is a much simpler task. Actually I
want to solve the task of "perfect stroker". It seems we could find the
two contours, the outermost and the innermost, like in this picture:
http://antigrain.com/stuff/non-zero3.png
But it's not always possible to define, what is inner and what is
outer, for example:
http://antigrain.com/stuff/non-zero6.png
Here we have a self-intersecting quadrangle, then we calculate the
stroke. Then, we should have picture on the right as the result of
filtering. Here we have one outer contour and two inner ones. And most
of all, the directions must be preserved, that is, if the outer contour
is CW, both inner ones must have CCW directions.
McSeem
http://antigrain.com
Bob Williamson
> One solution is the strict definition of an 'outer
> contour', as defined by this algorithm:
> 1. Find a starting point on the contour which is
> not inside e.g. by searching by a scanline from
> far left (edge of bounding box).
> 2. Go once around in ccw direction and go always
> to the right at a bifurcation.
> This delivers a contour without holes, which can be
> treated by any of the standard methods.
> Here it's shown for pixels:
> http://www.fho-emden.de/~hoffmann/inside.jpg
>
algorithm's first step is employed because it assures
that you don't begin the trace at a vertex that's
destined to be eliminated.
It would also greatly simply your problem if you could
constrain the input such that the vertices of that outer
polygon (i.e., the polygon which includes the left-most
vertex) are oriented in CCW direction (i.e., such that
the signed area of that polygon is positive). If a CCW
orientation isn't assured, then you'll have to test the
orientation and (for CW polygons) reverse the logic for
determining which internal polygons need to be drawn as
exclusion areas.
Bob
Bob Williamson
> Actually I want to solve the task of "perfect stroker". It
> seems we could find the two contours, the outermost and the
> innermost, like in this picture:
> http://antigrain.com/stuff/non-zero3.png
> But it's not always possible to define, what is inner and
> what is outer, for example:
> http://antigrain.com/stuff/non-zero6.png
> Here we have a self-intersecting quadrangle, then we
> calculate the stroke. Then, we should have picture on the
> right as the result of filtering. Here we have one outer
> contour and two inner ones. And most of all, the directions
> must be preserved, that is, if the outer contour is CW,
> both inner ones must have CCW directions.
>
"oriented edges".
First, structure your input data as an edge list (DCEL is a
very nice structure).
Second, perform a sweep of the input edges, and break those
edges which intersect each other at their points of
intersection. (As you create these new vertices, assure that
they're pointed to by their leading edges and have pointers
to their trailing edges.) Thus, at this stage the polygons
remain unchanged except that you now have some collinear
edges.
Third, test the orientation of the left-most polygon (the one
with the vertex that has the smallest x-value). Based on
that orientation, you determine whether a CCW orientation
implies the donut or the donut hole.
Fourth, trace the "outer contour" as Gernot proposed. But as
you encounter bifurcating vertices (those new vertices you
just created in step 2), you recurse left and traverse right.
The recursion will identify the "hole" polygons (if the
polygon's orientation implies a hole). You'll need to
recurse into internal polygons that aren't holes since those
edges may lead you to other polygons that are holes. You
just don't output those edges to your new SVG file unless
their orientation identifies them as holes.
Fifth, sweep the edge list iteratively (repeating step 4)
until each edge has been visited precisely once. This will
assure that you find all properly nested polygons.
Bob
hoff...@fho-emden.de
your task is quite understandable, but I have some doubts
whether it can be automated without additional information
by the programmer.
As far as I remember, e.g. for the donut, we have in Post-
Script two choices:
1. The angle direction, cw or ccw for the inner and the
outer circle.
2. fill or eofill, which defines the inside/outside checking
rule.
Sorry, didn't check the syntax actually, but I'm sure that
BOTH settings will define whether the interior of the donut
is rendered or not.
That leads to the unpleasant result: can be solved only by
human interaction.
Best regards --Gernot Hoffmann
McSeem
My point is as follows. There is a rasterization algorithm that can
work with both, even-odd and non-zero fill rules. It takes a
poly-polygon as an input and produces a number of horizontal scanlines
to draw. Each scanline consists of a number of spans (start, length).
The algorithm is pretty simple and fast and I do actually use it to
draw strokes (in particular). The non-zero fill rule produces exactly
what I need in all cases, polygons and polylines, self-intersecting or
not. And most of all, we don't need to know the *absolute* directions
of the contours, it doesn't make any difference. The only important
thing is *relative* directions of the *edges*. For example, a
self-intersecting quadrangle may not have a certain direction as a
signed area: (0,0) (10,0) (0,10) (10,10) has zero area. However, the
rasterizer perfectly handles it. The most important thing is that in
the rasterizer we don't have to analyse any directions, it's all done
automatically.
I use it to render strokes and everything else and it always produces
exactly what I need. But after rasterizarion we lose the vectorial
information and there's a number of tasks where we need it.
All I need is to filter extra edges that don't affect anyhow the visual
result of non-zero fill. And I feel it's quite possible. Afterall, just
theoretically we could rasterize the shape with very high resolution
(say, 10000x10000 pixels) and then restore the vector information
(vectorize the image). Of course it's expensive and inaccurate, but it
proves that it's possible to do using only the original vector
representation.
Thanks again!
McSeem
http://antigrain.com
McSeem
I will think about it.
I still feel that the most promising way is to analyze horizontal
scanlines at the "event points", that is, at the vertices and
intersections. That's what Alan does. And I also feel that a slight
modification of GPC can do what I need, but I'm now sure how exactly.
McSeem
> constrain the input such that the vertices of that outer
> polygon (i.e., the polygon which includes the left-most
> vertex) are oriented in CCW direction (i.e., such that
> the signed area of that polygon is positive). If a CCW
> orientation isn't assured, then you'll have to test the
> orientation and (for CW polygons) reverse the logic for
> determining which internal polygons need to be drawn as
> exclusion areas.
No, I can't constraint it. In general I don't know the direction and
can't deterimine it. A self-intersecting polygon doesn't have a certain
direction; it may only have a *prevailing* direction, but it won't
help. And the signed area can be zero.
McSeem
However, the rasterizer with non-zero fill perfectly handles any cases.
It means (IMO) that it's also doable in the vector form.
Bob Williamson
Yes, absolutely! This IS doable programmatically.
And regarding the question of 'prevailing' orientation -- maybe
we should speak of the 'local interior' being to the left or
right (or possibly on both sides) of a given edge rather than
calling the polygon CW or CCW. By dividing the initial edges
into segments that intersect only at vertices, we can always
unambiguously refer to the left or right side of an edge as
being the interior of the shape.
Specifically, beginning with the western-most vertex and
selecting the edge that's southern-most -- i.e., the edge from
v to v->next where: area(v->prev, v, v->next) > 0.0 -- we see
immediately that the interior side of that edge is to the left
of the path from v to v->next. As we trace the 'outer contour'
we simply define 'interior' as the side that's to the left of
each edge we traverse. But that still leaves the hard problem
of carving out holes within that shape.
Sorry, I need to withdraw my suggestion to recursively trace
those holes. You wouldn't want the recursion to traverse an
edge that's actually part of the outer contour, so you need to
traverse the entire outer contour BEFORE you start clipping
away at its interior.
I need to do a little more thinking and digging -- I'll post
more when I have something worth saying. This is an
interesting (i.e., fun) problem.
Bob
McSeem
In my opinion, the most promising way is to modify the GPC algorithm by
Alan Murta, see http://www.cs.man.ac.uk/aig/staff/alan/software/
(actually it's an implementation of general clipping by Bala R. Vatti)
Alan decomposes the polygons into scanlines and then assembles the new
polygons according to the given operation (and, or, sub, xor). I feel
that the first part (decomposition and finding the intersections) can
be used as is. All we need is to replace the assembling part. For each
scanline Alan creates an AET (active edge table) for each scanline and
scans it from left to right. That's pretty similar to what the scanline
rasterized does. And it's also very easy to determine the "insideness"
accoding to the non-zero rule. Maybe I'll try to invent something
similar to GPC, but still not 100% sure. Any other ideas are
appreciated!
Bob Williamson
> Thanks Bob!
>
> ... I feel that the first part (decomposition and finding the
> intersections) can be used as is. All we need is to replace
> the assembling part.
I believe I can provide you with that missing "assembling part".
Eliminating the common edges of adjacent filled polygons is a
problem I've grappled with before. You can do this by simply
walking the outer edge of every cluster of adjacent polygons.
Visualize this as a farmer who owns several fields. The farmer
wants to fence his property, but he doesn't want to build fences
between any two of his own fields -- just between his fields and
his neighbor's. First, he surveys all the fields and marks the
edges between his fields and those belonging to different
farmers. Programmatically this means: given a "doubly-connected
edge list" (DCEL), we simply iterate over the entire list of
edges and set a flag that indicates that the edge is between
polygons that will be colored differently; i.e., this is an edge
that that will NOT be eliminated.
Second, the farmer builds fences by starting at the western-
most point of his property, and walks the perimeter such that
his farm is always on his left. He builds the fence as he walks
the property line. Eventually he'll fence his way back to where
he started.
Programmatically this is a straightforward traversal of a DCEL.
A DCEL is a structure like this:
typedef struct {
double x; /* x-coordinate */
double y; /* y-coordinate */
} coord; /****************** point ****************/
typedef struct {
int edge; /* index value of an edge of this face */
int vrtx; /* index value of a vrtx of that edge */
} face; /****************** face *****************/
typedef struct {
coord p; /* x,y-coordinates */
int edge; /* edge incident at this vrtx */
} vrtx; /****************** vrtx *****************/
typedef struct {
int v1; /* start vrtx */
int v2; /* end vrtx */
int lft; /* left defining site */
int rgt; /* right defining site */
int s_cw; /* next edge in CW order around start vrtx */
int e_cw; /* next edge in CW order around end vrtx */
} edge; /***************** edge ******************/
The main feature of a DCEL is, of course, the "edge" structure
(hence the name "edge list").
Values for n1, n2 are index values of an array: vrtx vrt[];
Values for lft, rgt are index values of an array: face fac[];
Values for s_cw, e_cw are index values of an array: edge edg[];
You traverse from edge to edge by pivoting around the vertices
v1 or v2 to find the next connected edge in the clockwise
direction from the edge we're at. (You'd have to add "polygon-
ownership" and "needs-to-be-fenced" flags to the face and edge
structures respectively to store the values that guide your
trace.)
Back to our illustration:
Following our left-hand trace rule, if our mythic farmer was
walking an 'outer contour', then he will have traversed this
polygon in a CCW direction. If he was walking around a donut
hole, then he will have traversed it clockwise. (Your
http://antigrain.com/stuff/non-zero6.png example will produce
two such clockwise holes.)
Below is an SVG file that illustrates this "fence-walking"
algorithm: We begin with polygons A-B-C-D-E and W-X-Y-Z.
These intersect at points f,g,h,j,k,l,m,n,o,p,q,r,s.
The output we want is three polygons:
W-X-o-m-h ,
C-h-j-m-p-o-E-s-B-r-q-n-k-l-D-g-A-f , and
n-r-Y-Z-l .
The farmer begins at an edge of the western-most point of his
farm (edge W-X) and walks around a single field, W-X-o-m-h.
Notice that when the farmer arrives at vertex "o", he sees
three edges that required fences. He simply chooses the left-
most one.
Having fenced one field, the farmer realizes he's not done and
proceeds to the western-most point of his property that still
remains to be fenced (vertex "C"). Just as happened at vertex
"o", when the farmer arrives at vertex "h", he finds multiple
field edges to be fenced, but he simply chooses the left-most
and builds the fence along edge h-j.
Now at vertex "j", he encounters only one edge (edge j-m) that
his survey identified as needing a fence. It's NOT the left-
most edge, but it IS the left-most marked edge. Always
following his left-hand trace rule, the farmer closes back to
vertex "C", and thence proceeds to fence his last remaining
field (n-r-Y-Z-l).
Martin Held and I published a paper on this technique, which
I'll gladly share with you (though I can't publish on the Web
-- the copyright belongs to the IEEE). I can freely share a
PowerPoint show (2.4 MB) I presented at the IEEE-PES general
meeting last year. I'll email either or both of those to you
if you're interested.
As I said, this is a interesting problem!
Bob
<?xml version="1.0" standalone="no"?>
<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.0//EN"
"http://www.w3.org/TR/2001/REC-SVG-20010904/DTD/svg10.dtd">
<svg width="100%" height="100%">
<g fill-rule="nonzero" fill="red" stroke="black" stroke-width="1">
<path d="M 250,75 L 323,301 131,161 369,161 177,301 z
M 100,180 L 150,230 350,230 400,180 z"/>
<text x="245px" y="72px"
style="fill:rgb(black);font-size:15">A</text>
<text x="323px" y="317px"
style="fill:rgb(black);font-size:15">B</text>
<text x="117px" y="161px"
style="fill:rgb(black);font-size:15">C</text>
<text x="372px" y="161px"
style="fill:rgb(black);font-size:15">D</text>
<text x="165px" y="317px"
style="fill:rgb(black);font-size:15">E</text>
<text x="85px" y="178px"
style="fill:rgb(black);font-size:15">W</text>
<text x="135px" y="247px"
style="fill:rgb(black);font-size:15">X</text>
<text x="355px" y="247px"
style="fill:rgb(black);font-size:15">Y</text>
<text x="405px" y="178px"
style="fill:rgb(black);font-size:15">Z</text>
<text x="215px" y="155px"
style="fill:rgb(green);font-size:15">f</text>
<text x="280px" y="155px"
style="fill:rgb(green);font-size:15">g</text>
<text x="152px" y="195px"
style="fill:rgb(green);font-size:15">h</text>
<text x="218px" y="195px"
style="fill:rgb(green);font-size:15">j</text>
<text x="275px" y="195px"
style="fill:rgb(green);font-size:15">k</text>
<text x="340px" y="195px"
style="fill:rgb(green);font-size:15">l</text>
<text x="211px" y="215px"
style="fill:rgb(green);font-size:15">m</text>
<text x="280px" y="215px"
style="fill:rgb(green);font-size:15">n</text>
<text x="185px" y="240px"
style="fill:rgb(green);font-size:15">o</text>
<text x="220px" y="240px"
style="fill:rgb(green);font-size:15">p</text>
<text x="271px" y="240px"
style="fill:rgb(green);font-size:15">q</text>
<text x="306px" y="240px"
style="fill:rgb(green);font-size:15">r</text>
<text x="246px" y="261px"
style="fill:rgb(green);font-size:15">s</text>
</g>
</svg>
McSeem
It really is very helpful!
McSeem
> Following our left-hand trace rule, if our mythic farmer was
> walking an 'outer contour', then he will have traversed this
> polygon in a CCW direction. If he was walking around a donut
> hole, then he will have traversed it clockwise. (Your
> http://antigrain.com/stuff/non-zero6.png example will produce
> two such clockwise holes.)
Well, in my illustration the outer contour is CW and the inner holes
are CCW. In my opinion it would be preferably to keep the oridinal
direction of the edges (well, just for the sake of consistency). And I
also don't see any reason why we should change (or arrange them). The
point of the non-zero fill rule is that we can preserve the *original*
directions of the edges. Under any circumstances, as far as I can see.
If the directions are be changed, it's OK too, but if we do that we
will have to change the directions of *ALL* edges (again, as far as I
understand).
Thanks again!
Bob Williamson
McSeem wrote:
> In my opinion it would be preferably to keep the original
> direction of the edges (well, just for the sake of
Retaining the orientation of each edge is not "generally"
possible (meaning, there may be instances where that can be
done, but there will be some polygon arrangements where the
sequence of the vertices in your re-constituted polygons
will run counter to the direction of an original edge). I
suspect this is true of that svg file I attached.
Besides, as you pointed out to me, there's really no such
thing as a "prevailing orientation" of non-simple polygons
anyway.
Bob
McSeem
the entire polygons (a polygon may have no certain direction, but an
edge must).
Your statement is true and there is an interesting observation.
Another physical meaning of the winding rule is as follows (it's called
"winding" as if we wind a wire). Suppose there are closed contours with
direct current in them. The current produces magnetic field of
normalized intensity = 1 or -1 depending on the direction. The CCW
direction gives us N in the front of the contour and S behind it (and
vice versa). Then we overlap all the contours and sum all magnetic
fields. If the field at the given point is zero (compensated) we have a
hole. Otherwise - fill.
With the filter we just cut some loops and reconnect the contours.
Usually we can do that in several different ways. We just "reduce"
those loops that in summary produce magnetic field of abs(intensitry)
more than one!
I have tried to filter your picture manually (in Inkscape) and here's
the result:
http://antigrain.com/stuff/non-zero-bob.svg
And the observation is as follows. We find all the closed loops that
contribute extra field. For example, in the original red shape, "A" is
a loop that adds extra field. The triangle below is a loop too. But "B"
isn't the loop! And in the center (originally) there summary field = 1!
(The star gives you 2 in the center, the trapeziod adds -1).
Another observation is as follows.
I manually filtered your shape (rather inaccurate, but that's OK). The
green one is a single, self-intersecting polugon, ABCD...etc. And in
*this* case we *preserve* the directions of the edges.
In the other case (blue shape) it consists of one outermost contour and
four triangles with opposite direction. Yes, in this case we have to
*change* the direction of some edges.
McSeem
Bob Williamson
McSeem wrote:
...
> Your statement is true and there is an interesting observation.
>
> Another physical meaning of the winding rule is as follows
> (it's called "winding" as if we wind a wire). Suppose there are
> closed contours with direct current in them. The current produces
> magnetic field of normalized intensity = 1 or -1 depending on the
> direction. The CCW direction gives us N in the front of the
> contour and S behind it (and vice versa). Then we overlap all the
> contours and sum all magnetic fields. If the field at the given
> point is zero (compensated) we have a hole. Otherwise - fill.
I like your analogy (it speaks my language). I have a real-life
story about this "winding" rule. I am responsible for computing the
quantity of company property in each tax jurisdiction of our service
area. We have city limit boundaries in our GIS which I use to do
point-in-polygon testing on our active inventory. A few years ago
I found that my program found no property within a west Texas city
we serve. Visual examination of the GIS source revealed no
problem. I dumped the vertex coordinates to a text file and found
that the polygon had been drawn such that it made two complete
loops. My "odd-even" rule dutifully told me that all the poits
inside both those loops were actually outside the city. Anyway,
we paid the taxes. Now back to your story ...
> With the filter we just cut some loops and reconnect the
> contours. Usually we can do that in several different ways. We
> just "reduce" those loops that in summary produce magnetic
> field of abs(intensitry) more than one!
>
> I have tried to filter your picture manually (in Inkscape) and
> here's the result:
> http://antigrain.com/stuff/non-zero-bob.svg
Beautiful!
> And the observation is as follows. We find all the closed loops
> that contribute extra field. For example, in the original red
> shape, "A" is a loop that adds extra field. The triangle below
> is a loop too. But "B" isn't the loop! And in the center
> (originally) there summary field = 1!
> (The star gives you 2 in the center, the trapezoid adds -1).
You're on to something here. Can we generalize a rule about when
we deviate from the original path (in changing from my original
RED figure to your GREEN one)? Is the green figure the one
you're trying to create or do you want to eliminate the self-
intersections?
> Another observation is as follows.
> I manually filtered your shape (rather inaccurate, but that's
> OK). The green one is a single, self-intersecting polygon,
> ABCD...etc. And in *this* case we *preserve* the directions of
> the edges. In the other case (blue shape) it consists of one
> outermost contour and four triangles with opposite direction.
> Yes, in this case we have to *change* the direction of some
> edges.
Neither the BLUE nor the GREEN is the polygon my method creates.
Please look back at my posting and note that the edge-tracing I
do will create just three polygons, which kiss at vertices h,m,o
and l,n,r. I'll draw this as a YELLOW figure, but not today.
Bob
McSeem
> story about this "winding" rule. I am responsible for computing the
> quantity of company property in each tax jurisdiction of our service
> area. We have city limit boundaries in our GIS which I use to do
> point-in-polygon testing on our active inventory. A few years ago
> I found that my program found no property within a west Texas city
> we serve. Visual examination of the GIS source revealed no
> problem. I dumped the vertex coordinates to a text file and found
> that the polygon had been drawn such that it made two complete
> loops. My "odd-even" rule dutifully told me that all the poits
> inside both those loops were actually outside the city. Anyway,
> we paid the taxes. Now back to your story ...
Yes, that's interesting. Actually, the Point-in-poly test is simpler,
with both, non-zero and even-odd rules. Here's an article by Eric
Haines:
http://www.acm.org/tog/editors/erich/ptinpoly/
And some methods consider the "directional" winding. Well, but I guess
your task was more general and more complex.
> Neither the BLUE nor the GREEN is the polygon my method creates.
> Please look back at my posting and note that the edge-tracing I
> do will create just three polygons, which kiss at vertices h,m,o
> and l,n,r. I'll draw this as a YELLOW figure, but not today.
I see, but it doesn't make any difference. :) Instead of two triangles
we can have a sexangle with one common point in the middle.
In general, any result will do, I mean, self-intersecting or not. My
point is the following (or maybe it's even a theorem).
======================
If we keep self-intersections we don't have to change the directions of
any edges.
======================
Well, it's not a theorem really, it's just an observation, made on the
basis of just one case :)
But you see, the "green" case is a single self-intersecting polygon and
all the resulting edges have the same direction as in the original
multi-polygin. The essence of the method "in green" is that we remove
all the closures that contribute "extra magnetic field"! It might be
simpler than GPC, but I'm not sure.
Another example is here:
http://antigrain.com/stuff/non-zero1.png
In case 3 we can produce different results (3b) and one of them is a
single, self-intersecting polygon ABCGHDCF with a "kissing" point at C.
In another variant we simply leave it as is! It will also do. Anything
that preserves the non-zero rule will do and technically in case 3 we
don't have to do anything. But how to determine that we "we don't need
to do anything"? That seems to be difficult.
In case 4 we just remove the internal loop.
McSeem
Bob Williamson
> > Neither the BLUE nor the GREEN is the polygon my method creates.
> > Please look back at my posting and note that the edge-tracing I
> > do will create just three polygons, which kiss at vertices h,m,o
> > and l,n,r. I'll draw this as a YELLOW figure, but not today.
>
> I see, but it doesn't make any difference. :) Instead of two
> triangles we can have a sexangle with one common point in the
> middle.
>
Maxim,
Here's an SVG showing the figures that would result from my
fence-building method. (I fibbed about making all three polygons
YELLOW) Hopefully now you can see which three polygons I was
referring to. Note that all three of these polygons are CCW
(winding number = +1):
<?xml version="1.0" standalone="no"?>
<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN"
"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">
<svg width="100%" height="100%">
<g fill-rule="nonzero" fill="red" stroke="black" stroke-width="1">
<path d="
M 100.00,180.00
L 150.00,230.00
199.93,230.00
204.83,214.84
157.06,180.00 z"/>
</g>
<g fill-rule="nonzero" fill="cadetblue" stroke="black"
stroke-width="1">
<path d="
M 131.00,161.00
L 157.06,180.00
216.08,180.00
204.83,214.84
225.63,230.00
199.93,230.00
177.00,301.00
250.00,247.77
323.00,301.00
300.07,230.00
274.37,230.00
295.17,214.84
283.92,180.00
342.94,180.00
369.00,161.00
277.78,161.00
250.00, 75.00
222.22,161.00 z"/>
</g>
<g fill-rule="nonzero" fill="orange" stroke="black" stroke-width="1">
<path d="
M 295.17,214.84
L 300.07,230.00
350.00 230.00
400.00,180.00
342.94,180.00 z"/>
</g>
<g fill-rule="nonzero" fill="yellow" stroke="black" stroke-width="1">
> But you see, the "green" case is a single self-intersecting
> polygon and all the resulting edges have the same direction
> as in the original multi-polygin. The essence of the method
> "in green" is that we remove all the closures that contribute
> "extra magnetic field"! It might be simpler than GPC, but I'm
> not sure.
You seem to have some options in deciding what configuration
satisfies your requirements -- the GREEN or BLUE configurations
you illustrated: http://antigrain.com/stuff/non-zero-bob.svg
or the three non-intersecting polygons my procedure creates. I
doubt there's a general method that will consistently create a
single self-intersecting polygon so that the winding number of
any point is either plus one or zero (such as the GREEN one in
your illustration), but it would be great if there is.
Let me know which goal you're after. Based on my past work, I
know my fence-building approach does work, but it'll be
interesting to see if you can devise a method to generate any
other acceptable output configurations.
Bob
PS: English is a very inconsistent language. A 3-sided figure
is a triANGLE, 4-sided is a quadraLATERAL, 5-, 6-, 7-, etc. are
respectively pentaGON, hexaGON, heptaGON, etc. -- though I kind
of like your word "sexangle". (I suppose a non-simple sexangle
could be called a bi-sexangle since it goes "both ways", CW and
CCW.)
hoff...@fho-emden.de
thanks for your always pleasant posts.
How to name a plane figure with four sides:
1. Quadralateral (your version - IMO wrong)
2. Quadriliteral (my preferred version - wrong)
3. Quadraliteral (wrong)
4. Quadrilateral (corrrect, Oxford...Dictionary 1974)
5. Quadrangle (mostly a regular quadrilateral ?)
6. Quadragon (new suggestion, together with triagon)
Best regards --Gernot Hoffmann
McSeem
So, as we can see we the result may be different and technically any
variant will do. But I consider your configuration as the best one (the
most consistent one). It doesn't have self-intersections and it doesn't
have holes. Well, in case of a "donut" the hole must be there. BTW,
does you algotithm produce a hole or a single polyon with a "bridge" in
case of a "donut"? In my opinion there must be a hole because it's not
a good idea to add any extra edges not existing in the original
polygons.
Now let's get back to your question about the necessity to change the
direction of some edges. In your example I don't see it.
In my "GREEN" configuration there is a single self-intersectring
polygon and no necessity to change any directions. In the "BLUE"
configuration there is an outer polygon and holes. And in this case we
do need to change the directions. Simply because the edges of the
original polygons that belong to the outermost contour have different
directions.
!!!!!!!!!!! But your result does not require to change any directions
either! And if it's true for *all* cases (I can't prove it, it just
seems to be so) it would simplify the algorithm vastly (IMO).
Is there any negative demonstration that would show us we still need to
change edge directions?
The self-intersecting result (GREEN one) contains less number of
points, but once again, I like your configuration. It kind of
simplifies and "flattens" the whole thing. Oh! I know why. For example,
after your method we can calculate the exact *actual* area of the
polygon, just as a sum of absolute values of signed areas for each
polygon. In my cases it wouldn't be obvious.
Thanks again!
McSeem
Bob Williamson
Gernot,
I just hate it when non-native English speakers correct
my grammar and spelling. I learned from Martin Held that
this punctuation mark ":" is called a "colon" (not a
"colin") and that that "proven" is an adjective (not a
participle) -- it turns out "proved" is the participle,
which was news to me. It seems to me that those Austrians
(not being satisfied with running California) have
appointed themselves the grammar police of English (at
least for us unwashed Americans).
In my defense all I can say is, "You live closer to
England than I do."
Thanks,
Bob
PS -- Quadrangle actually IS an English word, but it's
used most commonly for a rectangular space between
buildings, or for the arrangement of buildings to form a
rectangular courtyard. The U.S. Geological Survey also
uses that word (or more commonly the abbreviation "quad")
to refer to their 7.5-minute mapsheets, a quarter of a
15-minute sheet.
Bob Williamson
> Thanks Bob!
> ... BTW, does your algorithm produce a hole or a single polyon
> with a "bridge" in case of a "donut"? In my opinion there must
> be a hole because it's not a good idea to add any extra edges
> not existing in the original polygons.
As you surmise, the algorithm I proposed will produce true
"holes", not "bridges". Imagine how the "fence-building will
handle your example configuration:
http://antigrain.com/stuff/non-zero6.png
The "fence-building" algorithm can only trace along existing
edges that are between areas that will be filled differently
(i.e., along edges of farm fields that the surveyor has marked
to be fenced) -- there are no such "bridging" edges between
the outer and inner polygons.
And as I pointed out, this method also has the helpful side
effect of drawing any holes in the opposite direction. That is,
if the outermost polygon is drawn CCW, the holes within it will
be CW. This will be true regardless of how deeply nested the
polygons are.
> Now let's get back to your question about the necessity to
> change the direction of some edges. In your example I don't
> see it. In my "GREEN" configuration there is a single self-
> intersecting polygon and no necessity to change any
> directions. ...
Yes, that's something I found very appealing about your GREEN
configuration. Thus, my question about whether you can define a
programmatic method that will assure you will have only winding
values of +1 or zero in the output configuration. My suspicion
is that nested polygons (holes within donuts within holes within
donuts, etc.) would frustrate any such attempt.
> !!!!!!!!!!! But your result does not require to change any
> directions either! And if it's true for *all* cases (I can't
> prove it, it just seems to be so) it would simplify the
> algorithm vastly (IMO).
I think I just got lucky. (You put me in the awkward position
of trying to prove that my method isn't as good as you think it
is, but I'll see if I can come up with a counter-example.)
> The self-intersecting result (GREEN one) contains less number
> of points, but once again, I like your configuration. It kind
> of simplifies and "flattens" the whole thing. Oh! I know why.
> For example, after your method we can calculate the exact
> *actual* area of the polygon, just as a sum of absolute values
> of signed areas for each polygon. In my cases it wouldn't be
> obvious.
I'm not sure I see your point about "actual area". The signed
area is the same either way -- I've just found three simple
polygons, whereas you've derived on self-intersecting one.
Perhaps what you find appealing is the fact that (by using my
method) each point of intersection becomes an explicit vertex --
is that maybe what you mean?
Bob
Przemyslaw Koprowski
> How to name a plane figure with four sides:
>
> 1. Quadralateral (your version - IMO wrong)
> 2. Quadriliteral (my preferred version - wrong)
> 3. Quadraliteral (wrong)
> 4. Quadrilateral (corrrect, Oxford...Dictionary 1974)
> 5. Quadrangle (mostly a regular quadrilateral ?)
> 6. Quadragon (new suggestion, together with triagon)
>
quadrilateral - four-sided figure
quadrangle - four-sided *plane* figure
I would say that the distincion may be crucial from
the point of view of both classical geometry and computer
graphics!
BTW, beside "pentagon" there is also "pentangle" but
it is just another name for "pentagram".
Przemek
--
"Beauty is the first test: there is no permanent place
in the world for ugly mathematics." G.H. Hardy
McSeem
> effect of drawing any holes in the opposite direction. That is,
> if the outermost polygon is drawn CCW, the holes within it will
> be CW. This will be true regardless of how deeply nested the
> polygons are.
So, if I unterdstand corrctly all nested holes will have the same
direction? And it will be opposite to the outermost contour?
If so, I still need something different, and it might be a confusion.
http://antigrain.com/stuff/non-zero95.png
On the left we have 4 nested triangles with alternating directions. In
this case the algorithm shall not do anything because we will have the
winding numbers 1,0,1,0 (from outer to inner). On the right picture the
situation is different and the winding numbers are 1,2,1,0 (also from
outer to inner). But from the point of view of non-zero fill, the case
on the right is equivalent to just keeping the outermost and the inmost
triangles. Two intermediate ones will be removed. In both cases we
should not change the direction of the edges.
> > !!!!!!!!!!! But your result does not require to change any
> > directions either! And if it's true for *all* cases (I can't
> > prove it, it just seems to be so) it would simplify the
> > algorithm vastly (IMO).
>
> I think I just got lucky. (You put me in the awkward position
> of trying to prove that my method isn't as good as you think it
> is, but I'll see if I can come up with a counter-example.)
Sorry about that :-)
But it was your statement that in certain cases we must reverse some
edges (or parts of them). I have a feeling that there is no necessity
of that, but I don't have a strict proof.
So, I'm only asking you to prove your own statement which should be
easy by providing an example that contradicts my statement.
> I'm not sure I see your point about "actual area". The signed
> area is the same either way -- I've just found three simple
> polygons, whereas you've derived on self-intersecting one.
> Perhaps what you find appealing is the fact that (by using my
> method) each point of intersection becomes an explicit vertex --
> is that maybe what you mean?
Well, I agree, I said something unclear. My point was that after the
filter we will always have winding numbers no more than 1 and no
self-intersections. And also, we will have no more extra (newly
introduced) holes, unlike my "blue" configuration, where there is an
outermost contour plus new holes in it. It's not that important from
the point of view of drawing but it can simplify the consecutive
processing, like calculation of the area considering the winding rule.
McSeem
Bob Williamson
McSeem wrote:
> > And as I pointed out, this method also has the helpful side
> > effect of drawing any holes in the opposite direction. That is,
> > if the outermost polygon is drawn CCW, the holes within it will
> > be CW. This will be true regardless of how deeply nested the
> > polygons are.
>
> So, if I unterdstand corrctly all nested holes will have the same
> direction? And it will be opposite to the outermost contour?
> If so, I still need something different, and it might be a
> confusion. http://antigrain.com/stuff/non-zero95.png
No, I didn't mean to imply all nested holes would be oriented in
the same direction. By using the plural "holes" I was merely
allowing that there may be more than one hole at that same nesting
level. What this method WILL do is alternate between winding
numbers plus one and zero as you proceed deeper into nested
polygons. In other words, all holes will be drawn clockwise and
all fills will be CCW. Or to put it another way, the space to be
filled will be on the left side of every edge.
Remember (as you specified in your original post) only edges that
border an area with a winding number equal to zero should be
preserved, so when our mythical "surveyor" marks the edges that
are to be fenced, he should ignore those edges where neither side
has a winding number equal to zero. So, in the case of the two
CCW polygons (in the figure on the right in your "non-zero95.png"
example, those edges will NOT be marked for fencing, and thus,
they will NOT be traced nor written to the output.
Finally, I don't have a rigorous proof, but I've about concluded
that it IS always possible to construct fences that preserve the
orientations of the original edges. My proposal to always keep
the non-zero side of the edge to your left (as you walk from edge
to edge) does't enforce the preservation of the original
orientations, but if you were to change that rule slightly (as
follows), it would.
Beginning at the western-most vertex, proceed to walk the surveyed
edges in the direction of the edges' original orientation. As you
proceed from edge to edge, you always keep the non-zero face on
the same side as it was with that first edge. In other words, if
the non-zero side was initially on the left, at each vertex you
traverse to the left-most "surveyed" edge; if the non-zero side
was initially on the right, at each vertex you traverse to the
right-most "surveyed" edge.
I believe this heuristic will preserve the original orientations,
but even if it doesn't, it will work just as well as my original
proposal. It's your call, but I would argue against making this
modification since it destroys the symmetry of all donuts being
CCW and all holes being CW.
I think I'm done with this topic.
Bob
hoff...@fho-emden.de
not found in an Oxford English Dictionary.
Another alternative is, that 'Quadralateral' belongs
to the group of mutilated words, like 'Seperetion',
'Gammut' and so on.
Best regards --Gernot Hoffmann
Bob Williamson
hoff...@fho-emden.de wrote:
> Perhaps 'Quadralateral' is American English, therefore
> not found in an Oxford English Dictionary.
>
> Another alternative is, that 'Quadralateral' belongs
> to the group of mutilated words, like 'Seperetion',
> 'Gammut' and so on.
I hap'ns ta thank the Queen of Ingland tocks funny (but
I s'pose that's wut hap'ns when cuzzins keeps amarryin'
each other -- not that there's anythin wrong with that,
mind you).
Just won word of advice: "Don't go misunderestimatin us
'Merkins." We mayn't be too brite, but we gots nukes.
Bob
McSeem
Thank! Now it's fully comprehensive. And sorry for stealing your
time...
Bob Williamson
McSeem wrote:
> Thank! Now it's fully comprehensive. And sorry for
> stealing your time...
My pleasure. As I said, this is a fun problem. Best
wishes on your coding this.
Bob