[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
gEDA-cvs: pcb.git: branch: master updated (1099c473dc24b8c1567261235ae3f4916b47cfc7)
The branch, master has been updated
via 1099c473dc24b8c1567261235ae3f4916b47cfc7 (commit)
from 4082c9b12655bd5a5e77bf4ecd2755034079b0b8 (commit)
Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.
=========
Summary
=========
src/polygon1.c | 127 +++++++++++++++++++-------------------------------------
1 files changed, 43 insertions(+), 84 deletions(-)
=================
Commit Messages
=================
commit 1099c473dc24b8c1567261235ae3f4916b47cfc7
Author: Harry Eaton <haceaton@xxxxxxxxxxxxxxxxxxxxx>
Commit: Peter Clifton <pcjc2@xxxxxxxxx>
Re-write node_label() to only label the edge being passed as its argument.
Breifly, the old code tried to walk the entire CVCList labeling
multiple edges. The new code tries only to label the argument vertex
i.e. the forward ('N') edge from this vertex. It tries to look
counter-clockwise just one edge which will give the answer in most
cases. If that fails it looks further into the CVCList until it can
find the answer, then stops. The code is much simpler because we know
that the edge we are labeling is always departing the cross-vertex
point.
(Futher comments and original bug diagnosis by Peter Clifton)
This prevents "double labeling", where the old routine could label any
edges which intersect at the vertex passed to node_label().
This fixes a bug discovered by Stefan Salewski, where certain boards
could trigger an assert failure when PCB was built with debugging.
The bug, it would seem - is relating to the way (and order) we were
labeling edges of polygon contours:
2
|/\ In this diagram, x is on the outer contour of our polygon,
x | and is in fact two vertices at the same point, lets denote
|\/ these as |\ and |/
1
The labelling algorithm works up from point 1, gets to |\, whereupon it
gets the CVCList for the spatial point x - which contains |\ AND |/
along with the (shared) edges from the clipping contour.
node_label is called with the |\ vertex, but in the process of scanning
the CVCList at this point, it also checks for SHARED edges. It _only_
checks shared edges against the |\ vertex, NOT the |/ one.
During this pass, the | edge coming from the |/ vertex gets mis-labelled
as "OUTSIDE", where is should eventually get labelled "SHARED"
BUG:
We then skip over calling node_label with the |/ vertex, since | has
already been labelled. We next get to point 2.
Point 2 looks at the | edge, and declares it to be "INSIDE". (It should
already have been labelled "SHARED" by this point, so node_label doesn't
know any better.
The | edge is already labelled "OUTSIDE" when we go to label it
"INSIDE".. assertion fail.
This commit avoids missing the correct labelling of shared edges, by
ensuring we never label any edges in advance of calling node_label
for them.
:100644 100644 3b01bea... f8e711e... M src/polygon1.c
=========
Changes
=========
commit 1099c473dc24b8c1567261235ae3f4916b47cfc7
Author: Harry Eaton <haceaton@xxxxxxxxxxxxxxxxxxxxx>
Commit: Peter Clifton <pcjc2@xxxxxxxxx>
Re-write node_label() to only label the edge being passed as its argument.
Breifly, the old code tried to walk the entire CVCList labeling
multiple edges. The new code tries only to label the argument vertex
i.e. the forward ('N') edge from this vertex. It tries to look
counter-clockwise just one edge which will give the answer in most
cases. If that fails it looks further into the CVCList until it can
find the answer, then stops. The code is much simpler because we know
that the edge we are labeling is always departing the cross-vertex
point.
(Futher comments and original bug diagnosis by Peter Clifton)
This prevents "double labeling", where the old routine could label any
edges which intersect at the vertex passed to node_label().
This fixes a bug discovered by Stefan Salewski, where certain boards
could trigger an assert failure when PCB was built with debugging.
The bug, it would seem - is relating to the way (and order) we were
labeling edges of polygon contours:
2
|/\ In this diagram, x is on the outer contour of our polygon,
x | and is in fact two vertices at the same point, lets denote
|\/ these as |\ and |/
1
The labelling algorithm works up from point 1, gets to |\, whereupon it
gets the CVCList for the spatial point x - which contains |\ AND |/
along with the (shared) edges from the clipping contour.
node_label is called with the |\ vertex, but in the process of scanning
the CVCList at this point, it also checks for SHARED edges. It _only_
checks shared edges against the |\ vertex, NOT the |/ one.
During this pass, the | edge coming from the |/ vertex gets mis-labelled
as "OUTSIDE", where is should eventually get labelled "SHARED"
BUG:
We then skip over calling node_label with the |/ vertex, since | has
already been labelled. We next get to point 2.
Point 2 looks at the | edge, and declares it to be "INSIDE". (It should
already have been labelled "SHARED" by this point, so node_label doesn't
know any better.
The | edge is already labelled "OUTSIDE" when we go to label it
"INSIDE".. assertion fail.
This commit avoids missing the correct labelling of shared edges, by
ensuring we never label any edges in advance of calling node_label
for them.
diff --git a/src/polygon1.c b/src/polygon1.c
index 3b01bea..f8e711e 100644
--- a/src/polygon1.c
+++ b/src/polygon1.c
@@ -388,108 +388,67 @@ node_label (VNODE * pn)
int region = UNKNWN;
assert (pn);
- assert (pn->cvc_prev);
- this_poly = pn->cvc_prev->poly;
- /* search clockwise in the cross vertex connectivity (CVC) list
+ assert (pn->cvc_next);
+ this_poly = pn->cvc_next->poly;
+ /* search counter-clockwise in the cross vertex connectivity (CVC) list
*
- * check for shared edges, and check if our edges
- * are ever found between the other poly's entry and exit
+ * check for shared edges (that could be prev or next in the list since the angles are equal)
+ * and check if this edge (pn -> pn->next) is found between the other poly's entry and exit
*/
-#ifdef DEBUG_LABEL
- DEBUGP ("CVCLIST for point (%d,%d)\n", pn->point[0], pn->point[1]);
-#endif
- /* first find whether we're starting inside or outside */
- for (l = pn->cvc_prev->prev; l != pn->cvc_prev; l = l->prev)
+ if (pn->cvc_next->angle == pn->cvc_next->prev->angle)
{
- if (l->poly != this_poly)
- {
- if (l->side == 'P')
- region = INSIDE;
- else
- region = OUTSIDE;
- }
+ l = pn->cvc_next->prev;
+ assert (l->poly != this_poly);
}
- l = pn->cvc_prev;
- do
+ else
+ l = pn->cvc_next->next;
+ assert (l && l->angle >= 0 && l->angle <= 4.0);
+ if (l->poly != this_poly)
{
- assert (l->angle >= 0 && l->angle <= 4.0);
-#ifdef DEBUG_LABEL
- DEBUGP (" poly %c side %c angle = %g\n", l->poly, l->side, l->angle);
-#endif
- if (l->poly != this_poly)
+ if (l->side == 'P')
{
- if (l->side == 'P')
+ if (l->parent->prev->point[0] == pn->next->point[0] &&
+ l->parent->prev->point[1] == pn->next->point[1])
{
- region = INSIDE;
- if (l->parent->prev->point[0] == pn->prev->point[0] &&
- l->parent->prev->point[1] == pn->prev->point[1])
- {
- LABEL_NODE (pn->prev, SHARED); /* incoming is shared */
- pn->prev->shared = l->parent->prev;
- }
- else if (l->parent->prev->point[0] == pn->next->point[0] &&
- l->parent->prev->point[1] == pn->next->point[1])
- {
- LABEL_NODE (pn, SHARED2); /* outgoing is shared2 */
- pn->shared = l->parent->prev;
- }
+ region = SHARED2;
+ pn->shared = l->parent->prev;
}
else
- {
- region = OUTSIDE;
- if (l->parent->next->point[0] == pn->next->point[0] &&
- l->parent->next->point[1] == pn->next->point[1])
- {
- LABEL_NODE (pn, SHARED);
- pn->shared = l->parent;
- }
- else if (l->parent->next->point[0] == pn->prev->point[0] &&
- l->parent->next->point[1] == pn->prev->point[1])
- {
- LABEL_NODE (pn->prev, SHARED2); /* outgoing is shared2 */
- pn->prev->shared = l->parent;
- }
- }
+ region = INSIDE;
}
else
{
- VNODE *v;
- if (l->side == 'P')
- v = l->parent->prev;
+ if (l->angle == pn->cvc_next->angle)
+ {
+ assert (l->parent->next->point[0] == pn->next->point[0] &&
+ l->parent->next->point[1] == pn->next->point[1]);
+ region = SHARED;
+ pn->shared = l->parent;
+ }
else
- v = l->parent;
- if (NODE_LABEL (v) != SHARED && NODE_LABEL (v) != SHARED2)
+ region = OUTSIDE;
+ }
+ }
+ if (region == UNKNWN)
+ {
+ for (l = l->next; l != pn->cvc_next; l = l->next)
+ {
+ if (l->poly != this_poly)
{
-#ifdef DEBUG_LABEL
- /* debugging */
- if (NODE_LABEL (v) != UNKNWN && NODE_LABEL (v) != region)
- {
- CVCList *x = l;
- LABEL_NODE (v, region);
- pline_dump (v);
- do
- {
- fprintf (stderr, "poly %c\n", x->poly);
- pline_dump (x->parent);
- }
- while ((x = x->next) != l);
- }
-#endif
- assert (NODE_LABEL (v) == UNKNWN || NODE_LABEL (v) == region);
- LABEL_NODE (v, region);
+ if (l->side == 'P')
+ region = INSIDE;
+ else
+ region = OUTSIDE;
+ break;
}
}
}
- while ((l = l->prev) != pn->cvc_prev);
-#ifdef DEBUG_LABEL
- DEBUGP ("\n");
-#endif
- assert (NODE_LABEL (pn) != UNKNWN && NODE_LABEL (pn->prev) != UNKNWN);
- if (NODE_LABEL (pn) == UNKNWN || NODE_LABEL (pn->prev) == UNKNWN)
+ assert (region != UNKNWN);
+ assert (NODE_LABEL (pn) == UNKNWN || NODE_LABEL (pn) == region);
+ LABEL_NODE (pn, region);
+ if (region == SHARED || region == SHARED2)
return UNKNWN;
- if (NODE_LABEL (pn) == INSIDE || NODE_LABEL (pn) == OUTSIDE)
- return NODE_LABEL (pn);
- return UNKNWN;
+ return region;
} /* node_label */
/*
_______________________________________________
geda-cvs mailing list
geda-cvs@xxxxxxxxxxxxxx
http://www.seul.org/cgi-bin/mailman/listinfo/geda-cvs