This is far less tested than the support for hole'd polygons. The idea is similar to DJ's polystitch plugin, but this one uses PCB's new support for saving polygons with holes in them. Usage: 1. Have some file from pstoedit's pcbfill back-end handy. Polygon contours are all thrown in as separate polygons are a real mess. 2. Select the region you want to sort out (all at once). NB: Only polygons on the same layer will be processed. 3. Run the action "polycombine" 4. Fix up the letter A in the logo! ;) I've attached a before + after example (which requires git HEAD pcb). NB: For some reason, the "A" in the logo I'm working with appears to have been emitted with the wrong winding orders by pstoedit. The work the plugin does to process the contours is actually pretty slow. (Awful computational complexity, and no speed-up tricks like r-trees are used). A more naive algorithm won't work because the contours to add / subtract are multiply nested in this image. I started off trying to loop over all polygons, computing the union of the positive contours, the union of the negative contours - then doing a single subtraction. This unfortunately deleted detail in the image. The plugin now works to construct a tree ordered by "containership" - and processes the relevant contours in an appropriate order so outer contours are processed before inner ones. Best regards, -- Peter Clifton Electrical Engineering Division, Engineering Department, University of Cambridge, 9, JJ Thomson Avenue, Cambridge CB3 0FA Tel: +44 (0)7729 980173 - (No signal in the lab!) Tel: +44 (0)1223 748328 - (Shared lab phone, ask for me)
/* PolyCombine plug-in for PCB
Copyright (C) 2010 Peter Clifton <pcjc2@xxxxxxxxx>
Licensed under the terms of the GNU General Public License, version 2.
Compile like this:
gcc -I$HOME/pcbsrc/git/src -I$HOME/pcbsrc/git -O2 -shared polycombine.c -o polycombine.so
The resulting polycombine.so goes in $HOME/.pcb/plugins/polycombine.so.
Usage: PolyCombine()
The selected polygons are combined together according to the ordering of their points.
*/
#include <stdio.h>
#include <math.h>
#include "global.h"
#include "data.h"
#include "macro.h"
#include "create.h"
#include "remove.h"
#include "hid.h"
#include "error.h"
#include "rtree.h"
#include "polygon.h"
#include "polyarea.h"
#include "assert.h"
#include "strflags.h"
#include "find.h"
#include "misc.h"
#include "draw.h"
static POLYAREA *
original_poly (PolygonType * p, bool *forward)
{
PLINE *contour = NULL;
POLYAREA *np = NULL;
Cardinal n;
Vector v;
int hole = 0;
*forward = true;
if ((np = poly_Create ()) == NULL)
return NULL;
/* first make initial polygon contour */
for (n = 0; n < p->PointN; n++)
{
/* No current contour? Make a new one starting at point */
/* (or) Add point to existing contour */
v[0] = p->Points[n].X;
v[1] = p->Points[n].Y;
if (contour == NULL)
{
if ((contour = poly_NewContour (v)) == NULL)
return NULL;
}
else
{
poly_InclVertex (contour->head.prev, poly_CreateNode (v));
}
/* Is current point last in contour? If so process it. */
if (n == p->PointN - 1 ||
(hole < p->HoleIndexN && n == p->HoleIndex[hole] - 1))
{
poly_PreContour (contour, TRUE);
/* Log the direction in which the outer contour was specified */
if (hole == 0)
*forward = (contour->Flags.orient == PLF_DIR);
/* make sure it is a positive contour (outer) or negative (hole) */
if (contour->Flags.orient != (hole ? PLF_INV : PLF_DIR))
poly_InvContour (contour);
assert (contour->Flags.orient == (hole ? PLF_INV : PLF_DIR));
poly_InclContour (np, contour);
contour = NULL;
assert (poly_Valid (np));
hole++;
}
}
return np;
}
typedef struct poly_tree poly_tree;
struct poly_tree {
PolygonType *polygon;
bool forward;
POLYAREA *polyarea;
poly_tree *parent;
poly_tree *child;
poly_tree *prev;
poly_tree *next;
};
/* ______
* ___________________|_ P6 | +P1 ____ +P6
* | P1 | | | |
* | _____ ____ |_|____| -P2 ____ -P4 ____ -P5
* | |P2 | |P5 | | |
* | | [] | |____| | +P3
* | | P3 | |
* | |_____| |
* | |
* | ___ |
* | |P4 | |
* | |___| |
* | |
* |_____________________|
*
* As we encounter each polygon, it gets a record. We need to check
* whether it contains any of the polygons existing in our tree. If
* it does, it will become the parent of them. (Check breadth first).
*
* When processing, work top down (breadth first), although if the
* contours can be assumed not to overlap, we can drill down in this
* order: P1, P2, P3, P4, P5, P6.
*/
static bool
PolygonContainsPolygon (POLYAREA *outer, POLYAREA *inner)
{
// int contours_isect;
/* Should check outer contours don't intersect? */
// contours_isect = Touching (outer, inner);
/* Cheat and assume simple single contour polygons for now */
// return contours_isect ?
// 0 : poly_ContourInContour (outer->contours, inner->contours);
return poly_ContourInContour (outer->contours, inner->contours);
}
static poly_tree *
insert_node_recursive (poly_tree *start_point, poly_tree *to_insert)
{
poly_tree *cur_node, *next = NULL;
// bool to_insert_isects_cur_node; /* Intersection */
bool to_insert_contains_cur_node; /* Containment */
bool cur_node_contains_to_insert; /* Containment */
bool placed_to_insert = false;
poly_tree *return_root = start_point;
if (start_point == NULL)
{
// printf ("start_point is NULL, so returning to_insert\n");
//to_insert->parent = !!; UNDEFINED
return to_insert;
}
/* Investigate the start point and its peers first */
for (cur_node = start_point; cur_node != NULL; cur_node = next)
{
next = cur_node->next;
// to_insert_isects_cur_node = IsPolygonInPolygon (to_insert->polygon, cur_node->polygon);
to_insert_contains_cur_node = PolygonContainsPolygon (to_insert->polyarea, cur_node->polyarea);
#if 0
printf ("Inspecting polygon %ld %s, curnode is %ld %s: to_insert_isects_cur_node = %d, to_insert_contains_cur_node = %i\n",
to_insert->polygon->ID,
to_insert->forward ? "FWD" : "BWD",
cur_node->polygon->ID,
cur_node->forward ? "FWD" : "BWD",
to_insert_isects_cur_node,
to_insert_contains_cur_node);
if (to_insert_isects_cur_node) /* Place as peer of this node? */
{
}
#endif
if (to_insert_contains_cur_node) /* Should be a parent of this node */
{
/* Remove cur_node from its peers */
if (cur_node->prev)
cur_node->prev->next = cur_node->next;
if (cur_node->next)
cur_node->next->prev = cur_node->prev;
/* If we've not yet got a home, insert the to_insert node where cur_node was previously */
if (!placed_to_insert)
{
to_insert->parent = cur_node->parent;
to_insert->next = cur_node->next;
to_insert->prev = cur_node->prev;
if (to_insert->prev)
to_insert->prev->next = to_insert;
if (to_insert->next)
to_insert->next->prev = to_insert;
placed_to_insert = true;
if (cur_node == start_point)
return_root = to_insert;
}
/* Prepend cur_node to our list of children */
cur_node->parent = to_insert;
cur_node->prev = NULL;
cur_node->next = to_insert->child;
if (to_insert->child)
to_insert->child->prev = cur_node;
to_insert->child = cur_node;
}
}
if (placed_to_insert)
{
// printf ("Returning new root %ld\n", return_root->polygon->ID);
return return_root;
}
// return (to_insert->parent == NULL) ? to_insert : to_insert->parent;
/* Ok, so we still didn't find anywhere which the to_insert contour contained,
* we need to start looking at the children of the start_point and its peers.
*/
// printf ("Looking at child nodes of the start_point\n");
/* Investigate the start point and its peers first */
for (cur_node = start_point; cur_node != NULL; cur_node = next)
{
next = cur_node->next;
cur_node_contains_to_insert = PolygonContainsPolygon (cur_node->polyarea, to_insert->polyarea);
#if 0
printf ("Inspecting polygon %ld, curnode is %ld: cur_node_contains_to_insert = %d\n",
to_insert->polygon->ID, cur_node->polygon->ID,
cur_node_contains_to_insert);
#endif
/* Need to look at the child, ONLY if we know it engulfs our to_insert polygon */
if (cur_node_contains_to_insert)
{
/* Can't set the parent within the call, so: */
to_insert->parent = cur_node;
cur_node->child = insert_node_recursive (cur_node->child, to_insert);
return start_point;
//return cur_node->parent;
}
}
// if (!placed_to_insert)
/* prepend to_insert polygon to peer of start_point ? */
// printf ("Prepending as peer to start_poly\n");
to_insert->parent = start_point->parent;
to_insert->prev = NULL;
to_insert->next = start_point;
to_insert->next->prev = to_insert;
return to_insert;
}
static POLYAREA *
compute_polygon_recursive (poly_tree *root, POLYAREA *accumulate)
{
POLYAREA *res;
poly_tree *cur_node;
for (cur_node = root; cur_node != NULL; cur_node = cur_node->next)
{
/* Process this element */
// printf ("Processing node %ld %s\n", cur_node->polygon->ID, cur_node->forward ? "FWD" : "BWD");
poly_Boolean_free (accumulate, cur_node->polyarea, &res, cur_node->forward ? PBO_UNITE : PBO_SUB);
accumulate = res;
/* And its children if it has them */
if (cur_node->child)
{
// printf ("Processing children\n");
accumulate = compute_polygon_recursive (cur_node->child, accumulate);
}
}
return accumulate;
}
static int
polycombine (int argc, char **argv, int x, int y)
{
POLYAREA *res;
bool forward;
bool outer;
POLYAREA *np;
POLYAREA *pa;
PLINE *pline;
VNODE *node;
PolygonType *Polygon;
LayerType *Layer = NULL;
poly_tree *root = NULL;
poly_tree *this_node;
/* First pass to combine the forward and backward contours */
VISIBLEPOLYGON_LOOP (PCB->Data);
{
if (!TEST_FLAG (SELECTEDFLAG, polygon))
continue;
/* Pick the layer of the first polygon we find selected */
if (Layer == NULL)
Layer = layer;
/* Only combine polygons on the same layer */
if (Layer != layer)
continue;
np = original_poly (polygon, &forward);
/* Build a poly_tree record */
this_node = calloc (1, sizeof (poly_tree));
this_node->polygon = polygon;
this_node->forward = forward;
this_node->polyarea = np;
/* Check where we should place the node in the tree */
root = insert_node_recursive (root, this_node);
//RemovePolygon (layer, polygon);
}
ENDALL_LOOP;
/* Now perform a traversal of the tree, computing a polygon */
res = compute_polygon_recursive (root, NULL);
SaveUndoSerialNumber ();
/* Second pass to remove the input polygons */
VISIBLEPOLYGON_LOOP (PCB->Data);
{
if (!TEST_FLAG (SELECTEDFLAG, polygon))
continue;
/* Only combine polygons on the same layer */
if (Layer != layer)
continue;
RemovePolygon (layer, polygon);
}
ENDALL_LOOP;
/* Now de-construct the resulting polygon into raw PCB polygons */
PolyToPolygonsOnLayer (PCB->Data, Layer, res,
string_to_pcbflags ("clearpoly", NULL));
RestoreUndoSerialNumber ();
IncrementUndoSerialNumber ();
Draw ();
return 0;
}
static HID_Action polycombine_action_list[] = {
{"PolyCombine", "???", polycombine,
NULL, NULL}
};
REGISTER_ACTIONS (polycombine_action_list)
void
pcb_plugin_init()
{
register_polycombine_action_list();
}
Attachment:
uc.pcb
Description: application/pcb-layout
Attachment:
uc_combined.pcb
Description: application/pcb-layout
_______________________________________________ geda-user mailing list geda-user@xxxxxxxxxxxxxx http://www.seul.org/cgi-bin/mailman/listinfo/geda-user