Menu
▾
▴
[Pcb-src-changes] pcb.git: branch: master updated (af2f50d4fb838de13dfbb5243e2114c66fefba7b)
|
From: <gi...@gp...> - 2010-06-02 20:29:05
|
The branch, master has been updated
via af2f50d4fb838de13dfbb5243e2114c66fefba7b (commit)
via 4a44c883afc56747ea95522fcbdf9dc0b6a38952 (commit)
via 91fd6d3ea006ebc9e9189d81e0211b7c2646dfb2 (commit)
from 3d0a8bd1dae0816d364a774bf9b958faf2983ec7 (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 | 58 ++++++++++++++++++++++++++++++++++++++++---------------
1 files changed, 42 insertions(+), 16 deletions(-)
=================
Commit Messages
=================
commit af2f50d4fb838de13dfbb5243e2114c66fefba7b
Author: Peter Clifton <pc...@ca...>
Commit: Peter Clifton <pc...@ca...>
Fix node_label() function to work with self-intersection
Rather than just giving up if we encounter our own edges in the
CVC list at first, skip them until we either run out of edges, or
find one belonging to the other polygon.
I'm not 100% sure this is the correct fix, but it "seems to work".
Test-case:
Layer(1 "component")
(
Line[60000 70000 60000 90000 4000 2000 "clearline"]
Line[80000 60000 80000 90000 4000 2000 "clearline"]
Line[90000 90000 90000 50000 4000 6000 "clearline"]
Line[60000 40000 80000 60000 4000 6000 "clearline"]
Polygon("clearpoly")
(
[10000 10000] [140000 10000] [140000 140000] [10000 140000]
)
)
:100644 100644 6a40752... a8a8b89... M src/polygon1.c
commit 4a44c883afc56747ea95522fcbdf9dc0b6a38952
Author: Peter Clifton <pc...@ca...>
Commit: Peter Clifton <pc...@ca...>
Fix the polygon touching contour test in poly_ChkContour
The following test-cases were used to help verify the changes:
This polygon forms a self-touching shape like this:
\| However, the right-hand edge does NOT have a node at the junction.
/| This previously caused it to fail the self-intersection test.
It should be reported as good.
Polygon("")
(
[85000 50000] [85000 90000] [83000 90000]
[83536 63535] [85000 59999] [83535 56464]
)
This polygon forms a self-intersecting shape like this:
|/ (The vertical section is a straight line with no node in the middle)
/| It must be reported as bad.
Polygon("")
(
[85000 50000] [85000 90000] [83000 90000]
[83536 63535] [85000 59999] [89535 56464]
)
This polygon self-intersects, and must be reported as bad:
Polygon("")
(
[160000 50000] [160000 90000] [170000 100000]
[180000 120000] [180000 150000] [160000 150000]
[160000 120000] [170000 100000] [180000 90000]
[180000 50000]
)
This polygon self-touches, and should be reported as good:
Polygon("clearpoly")
(
[120000 50000] [120000 90000] [130000 100000]
[120000 120000] [120000 150000] [140000 150000]
[140000 120000] [130000 100000] [140000 90000]
[140000 50000]
)
:100644 100644 f8ed16b... 6a40752... M src/polygon1.c
commit 91fd6d3ea006ebc9e9189d81e0211b7c2646dfb2
Author: Peter Clifton <pc...@ca...>
Commit: Peter Clifton <pc...@ca...>
Fix poly_ComputeInteriorPoint() to work correctly for holes
The step where the algorithm finds a convex node to start from must
take into account whether the polygon vertices are ordered as a hole
or an outer contour. We now correctly compute a point inside the hole,
rather than possibly outside it.
This fixes an assertion on the following test-case. Prior to this
commit, the incorrect "interior" point tested for the concave hole
happens to lie inside the polygon's other hole, causing it to fail
an assert during processing.
Layer(2 "solder")
(
Line[340000 160000 183700 108000 1500 3000 "clearline"]
Line[92000 121000 120000 90000 1500 3000 "clearline"]
Line[270000 90000 120000 90000 1500 3000 "clearline"]
Polygon("clearpoly")
(
[40000 40000] [320000 40000] [320000 200000] [40000 200000]
)
)
The bug was created in my attempt to speed up poly_ContourInContour:
commit 3d0a8bd1dae0816d364a774bf9b958faf2983ec7
:100644 100644 31b71f1... f8ed16b... M src/polygon1.c
=========
Changes
=========
commit af2f50d4fb838de13dfbb5243e2114c66fefba7b
Author: Peter Clifton <pc...@ca...>
Commit: Peter Clifton <pc...@ca...>
Fix node_label() function to work with self-intersection
Rather than just giving up if we encounter our own edges in the
CVC list at first, skip them until we either run out of edges, or
find one belonging to the other polygon.
I'm not 100% sure this is the correct fix, but it "seems to work".
Test-case:
Layer(1 "component")
(
Line[60000 70000 60000 90000 4000 2000 "clearline"]
Line[80000 60000 80000 90000 4000 2000 "clearline"]
Line[90000 90000 90000 50000 4000 6000 "clearline"]
Line[60000 40000 80000 60000 4000 6000 "clearline"]
Polygon("clearpoly")
(
[10000 10000] [140000 10000] [140000 140000] [10000 140000]
)
)
diff --git a/src/polygon1.c b/src/polygon1.c
index 6a40752..a8a8b89 100644
--- a/src/polygon1.c
+++ b/src/polygon1.c
@@ -387,7 +387,7 @@ node_label
static unsigned int
node_label (VNODE * pn)
{
- CVCList *l;
+ CVCList *first_l, *l;
char this_poly;
int region = UNKNWN;
@@ -400,12 +400,15 @@ node_label (VNODE * pn)
* and check if this edge (pn -> pn->next) is found between the other poly's entry and exit
*/
if (pn->cvc_next->angle == pn->cvc_next->prev->angle)
- {
- l = pn->cvc_next->prev;
- assert (l->poly != this_poly);
- }
+ l = pn->cvc_next->prev;
else
l = pn->cvc_next->next;
+
+ first_l = l;
+ while ((l->poly == this_poly) && (l != first_l->prev))
+ l = l->next;
+ assert (l->poly != this_poly);
+
assert (l && l->angle >= 0 && l->angle <= 4.0);
if (l->poly != this_poly)
{
commit 4a44c883afc56747ea95522fcbdf9dc0b6a38952
Author: Peter Clifton <pc...@ca...>
Commit: Peter Clifton <pc...@ca...>
Fix the polygon touching contour test in poly_ChkContour
The following test-cases were used to help verify the changes:
This polygon forms a self-touching shape like this:
\| However, the right-hand edge does NOT have a node at the junction.
/| This previously caused it to fail the self-intersection test.
It should be reported as good.
Polygon("")
(
[85000 50000] [85000 90000] [83000 90000]
[83536 63535] [85000 59999] [83535 56464]
)
This polygon forms a self-intersecting shape like this:
|/ (The vertical section is a straight line with no node in the middle)
/| It must be reported as bad.
Polygon("")
(
[85000 50000] [85000 90000] [83000 90000]
[83536 63535] [85000 59999] [89535 56464]
)
This polygon self-intersects, and must be reported as bad:
Polygon("")
(
[160000 50000] [160000 90000] [170000 100000]
[180000 120000] [180000 150000] [160000 150000]
[160000 120000] [170000 100000] [180000 90000]
[180000 50000]
)
This polygon self-touches, and should be reported as good:
Polygon("clearpoly")
(
[120000 50000] [120000 90000] [130000 100000]
[120000 120000] [120000 150000] [140000 150000]
[140000 120000] [130000 100000] [140000 90000]
[140000 50000]
)
diff --git a/src/polygon1.c b/src/polygon1.c
index f8ed16b..6a40752 100644
--- a/src/polygon1.c
+++ b/src/polygon1.c
@@ -2504,23 +2504,45 @@ poly_ChkContour (PLINE * a)
else if (vect_dist2 (i1, a1->next->point) < EPSILON)
hit1 = a1->next;
else
- return TRUE;
+ hit1 = NULL;
if (vect_dist2 (i1, a2->point) < EPSILON)
hit2 = a2;
else if (vect_dist2 (i1, a2->next->point) < EPSILON)
hit2 = a2->next;
else
- return TRUE;
+ hit2 = NULL;
-#if 1
- /* now check if they are inside each other */
- if (inside_sector (hit1, hit2->prev->point) ||
- inside_sector (hit1, hit2->next->point) ||
- inside_sector (hit2, hit1->prev->point) ||
- inside_sector (hit2, hit1->next->point))
- return TRUE;
-#endif
+ if ((hit1 == NULL) && (hit2 == NULL))
+ {
+ /* If the intersection didn't land on an end-point of either
+ * line, we know the lines cross and we return TRUE.
+ */
+ return TRUE;
+ }
+ else if (hit1 == NULL)
+ {
+ /* An end-point of the second line touched somewhere along the
+ length of the first line. Check where the second line leads. */
+ if (inside_sector (hit2, a1->point) !=
+ inside_sector (hit2, a1->next->point))
+ return TRUE;
+ }
+ else if (hit2 == NULL)
+ {
+ /* An end-point of the first line touched somewhere along the
+ length of the second line. Check where the first line leads. */
+ if (inside_sector (hit1, a2->point) !=
+ inside_sector (hit1, a2->next->point))
+ return TRUE;
+ }
+ else
+ {
+ /* Both lines intersect at an end-point. Check where they lead. */
+ if (inside_sector (hit1, hit2->prev->point) !=
+ inside_sector (hit1, hit2->next->point))
+ return TRUE;
+ }
}
}
while ((a2 = a2->next) != &a->head);
commit 91fd6d3ea006ebc9e9189d81e0211b7c2646dfb2
Author: Peter Clifton <pc...@ca...>
Commit: Peter Clifton <pc...@ca...>
Fix poly_ComputeInteriorPoint() to work correctly for holes
The step where the algorithm finds a convex node to start from must
take into account whether the polygon vertices are ordered as a hole
or an outer contour. We now correctly compute a point inside the hole,
rather than possibly outside it.
This fixes an assertion on the following test-case. Prior to this
commit, the incorrect "interior" point tested for the concave hole
happens to lie inside the polygon's other hole, causing it to fail
an assert during processing.
Layer(2 "solder")
(
Line[340000 160000 183700 108000 1500 3000 "clearline"]
Line[92000 121000 120000 90000 1500 3000 "clearline"]
Line[270000 90000 120000 90000 1500 3000 "clearline"]
Polygon("clearpoly")
(
[40000 40000] [320000 40000] [320000 200000] [40000 200000]
)
)
The bug was created in my attempt to speed up poly_ContourInContour:
commit 3d0a8bd1dae0816d364a774bf9b958faf2983ec7
diff --git a/src/polygon1.c b/src/polygon1.c
index 31b71f1..f8ed16b 100644
--- a/src/polygon1.c
+++ b/src/polygon1.c
@@ -2333,6 +2333,7 @@ poly_ComputeInteriorPoint (PLINE *poly, Vector v)
VNODE *min_q = NULL;
double dist;
double min_dist;
+ double dir = (poly->Flags.orient == PLF_DIR) ? 1. : -1;
/* Find a convex node on the polygon */
pt1 = &poly->head;
@@ -2346,7 +2347,7 @@ poly_ComputeInteriorPoint (PLINE *poly, Vector v)
dot_product = dot_orthogonal_to_direction (pt1->point, pt2->point,
pt3->point, pt2->point);
- if (dot_product > 0.)
+ if (dot_product * dir > 0.)
break;
}
while ((pt1 = pt1->next) != &poly->head);
|