From 24a4818486105abe585381b5c85e42a4a58c9d1d Mon Sep 17 00:00:00 2001
From: ehennes <[EMAIL PROTECTED]>
Date: Wed, 8 Oct 2008 20:15:48 -0700
Subject: [PATCH] Added functionality to hatch arbitrary polygons.
Added functions to hatch arbitrary polygons. This patch also includes functions
with similar signatures to hatch boxes and circles. This patch also includes
geometric transformations, which is required by the hatching functions.
---
libgeda/include/prototype_priv.h | 17 +++
libgeda/include/struct.h | 16 ++
libgeda/src/Makefile.am | 2 +
libgeda/src/m_basic.c | 5 -
libgeda/src/m_hatch.c | 293 ++++++++++++++++++++++++++++++++++++++
libgeda/src/m_transform.c | 209 +++++++++++++++++++++++++++
6 files changed, 537 insertions(+), 5 deletions(-)
create mode 100644 libgeda/src/m_hatch.c
create mode 100644 libgeda/src/m_transform.c
diff --git a/libgeda/include/prototype_priv.h b/libgeda/include/prototype_priv.h
index 659f6c4..6fc0100 100644
--- a/libgeda/include/prototype_priv.h
+++ b/libgeda/include/prototype_priv.h
@@ -51,6 +51,23 @@ SCM g_get_line_width(SCM object_smob);
void g_init_page_smob(void);
SCM g_get_page_filename(SCM page_smob);
+/* m_hatch.c */
+void m_hatch_box(BOX *box, gint angle, gint pitch, GArray *lines);
+void m_hatch_circle(CIRCLE *circle, gint angle, gint pitch, GArray *lines);
+void m_hatch_polygon(GArray *points, gint angle, gint pitch, GArray *lines);
+
+/* m_transform.c */
+void m_transform_combine(TRANSFORM *result, TRANSFORM *a, TRANSFORM *b );
+void m_transform_init(TRANSFORM *transform);
+void m_transform_invert(TRANSFORM *transform, TRANSFORM *inverse);
+void m_transform_line(TRANSFORM *transform, LINE *line );
+void m_transform_lines(TRANSFORM *transform, GArray *lines);
+void m_transform_point(TRANSFORM *transform, gint *x, gint *y);
+void m_transform_points(TRANSFORM *transform, GArray *points);
+void m_transform_rotate(TRANSFORM *transform, gdouble angle);
+void m_transform_scale(TRANSFORM *transform, gdouble factor);
+void m_transform_translate(TRANSFORM *transform, gdouble dx, gdouble dy);
+
/* o_arc_basic.c */
OBJECT *o_arc_read(TOPLEVEL *toplevel, OBJECT *object_list, char buf[],
unsigned int release_ver, unsigned int fileformat_ver);
char *o_arc_save(OBJECT *object);
diff --git a/libgeda/include/struct.h b/libgeda/include/struct.h
index 087c3eb..4445e03 100644
--- a/libgeda/include/struct.h
+++ b/libgeda/include/struct.h
@@ -36,6 +36,8 @@ typedef struct st_arc ARC;
typedef struct st_box BOX;
typedef struct st_picture PICTURE;
typedef struct st_text TEXT;
+typedef struct st_point POINT;
+typedef struct st_transform TRANSFORM;
typedef struct st_object OBJECT;
typedef struct st_page PAGE;
@@ -94,6 +96,11 @@ struct st_line {
};
+struct st_point {
+ gint x;
+ gint y;
+};
+
/* pb20011014 - name the grips */
#define LINE_END1 0
#define LINE_END2 1
@@ -331,6 +338,15 @@ struct st_stretch
STRETCH *next;
};
+/** A structure to store a 2D affine transform.
+ *
+ * The transforms get stored in a 3x3 matrix. Code assumes the bottom row to
+ * remain constant at [0 0 1].
+ */
+struct st_transform {
+ gdouble m[2][3]; /* m[row][column] */
+};
+
struct st_undo {
/* one of these is used, depending on if you are doing in-memory */
diff --git a/libgeda/src/Makefile.am b/libgeda/src/Makefile.am
index bcae051..8f1274c 100644
--- a/libgeda/src/Makefile.am
+++ b/libgeda/src/Makefile.am
@@ -25,6 +25,8 @@ libgeda_la_SOURCES = \
i_vars.c \
libgeda.c \
m_basic.c \
+ m_hatch.c \
+ m_transform.c \
o_arc_basic.c \
o_attrib.c \
o_basic.c \
diff --git a/libgeda/src/m_basic.c b/libgeda/src/m_basic.c
index b0b5ea9..c8cc63f 100644
--- a/libgeda/src/m_basic.c
+++ b/libgeda/src/m_basic.c
@@ -372,11 +372,6 @@ struct st_halfspace {
int bottom;
};
-/*! \brief */
-struct st_point {
- int x, y;
-};
-
/* \note
* encode_halfspace and clip are part of the cohen-sutherland clipping
* algorithm. They are used to determine if an object is visible or not
diff --git a/libgeda/src/m_hatch.c b/libgeda/src/m_hatch.c
new file mode 100644
index 0000000..26dc3a6
--- /dev/null
+++ b/libgeda/src/m_hatch.c
@@ -0,0 +1,293 @@
+/* gEDA - GPL Electronic Design Automation
+ * libgeda - gEDA's library
+ * Copyright (C) 1998-2008 Ales Hvezda
+ * Copyright (C) 1998-2008 gEDA Contributors (see ChangeLog for details)
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111 USA
+ */
+#include <config.h>
+#include <math.h>
+#include <string.h>
+#include <libgeda_priv.h>
+
+typedef struct st_sweep_event SWEEP_EVENT;
+typedef struct st_sweep_status SWEEP_STATUS;
+
+struct st_sweep_status {
+ gint x; /* current x coordinate */
+ gint y1; /* ending y coordinate */
+ gdouble m1; /* inverse slope: y/x */
+ gdouble b1; /* x intercept */
+};
+
+struct st_sweep_event {
+ gint y0; /* starting y coordinate */
+ SWEEP_STATUS status;
+};
+
+static gint compare_events(gconstpointer a, gconstpointer b);
+static gint compare_status(gconstpointer a, gconstpointer b);
+
+/** \brief Compares two sweep events
+ *
+ * Compares two sweep events for ordering the event queue. The prototype
+ * and behavior are consistant with GCompareFunc.
+ *
+ * \param a [in] The first sweep event.
+ * \param a [in] The second sweep event.
+ * \return A negative value if the first is less than the second, zero if the
+ * first equals the second, and a positive value if the first is greater than
+ * the second.
+ */
+static gint compare_events(gconstpointer a, gconstpointer b)
+{
+ SWEEP_EVENT *event_a = (SWEEP_EVENT*) a;
+ SWEEP_EVENT *event_b = (SWEEP_EVENT*) b;
+
+ return (event_a->y0 - event_b->y0);
+}
+
+/** \brief Compares two sweep status structs
+ *
+ * Compares two sweep status for ordering the sweep status. The prototype
+ * and behavior are consistant with GCompareFunc.
+ *
+ * \param a [in] The first sweep status.
+ * \param a [in] The second sweep status.
+ * \return A negative value if the first is less than the second, zero if the
+ * first equals the second, and a positive value if the first is greater than
+ * the second.
+ */
+static gint compare_status(gconstpointer a, gconstpointer b)
+{
+ SWEEP_STATUS *status_a = (SWEEP_STATUS*) a;
+ SWEEP_STATUS *status_b = (SWEEP_STATUS*) b;
+
+ return (status_b->x - status_a->x);
+}
+
+/** \brief Calculates line segments to hatch a box shape
+ *
+ * This function appends new line segments to the lines GArray. For creating
+ * a hatch pattern, the GArray must be cleared before calling this function.
+ * For creating cross hatch patterns, this function can be called multiple
+ * times with a different angle or pitch while passing the same lines GArray.
+ *
+ * \param box [in] The box shape to hatch.
+ * \param angle [in] The angle of the hatch lines with respect to the x axis.
+ * \param pitch [in] The distance between hatch lines
+ * \param lines [inout] A GArray of LINE to contain the new hatch line
+ * segments. This function appends new line segments to the GArray and leaves
+ * existing GArray contents unchanged.
+ */
+void m_hatch_box(BOX *box, gint angle, gint pitch, GArray *lines)
+{
+ GArray *corners;
+ POINT point;
+
+ g_return_if_fail(box!=NULL);
+ g_return_if_fail(lines!=NULL);
+
+ corners = g_array_sized_new(FALSE, FALSE, sizeof(POINT), 4);
+
+ point.x = box->upper_x;
+ point.y = box->upper_y;
+ g_array_append_val(corners, point);
+
+ point.x = box->lower_x;
+ point.y = box->upper_y;
+ g_array_append_val(corners, point);
+
+ point.x = box->lower_x;
+ point.y = box->lower_y;
+ g_array_append_val(corners, point);
+
+ point.x = box->upper_x;
+ point.y = box->lower_y;
+ g_array_append_val(corners, point);
+
+ m_hatch_polygon(corners, angle, pitch, lines);
+
+ g_array_free(corners, TRUE);
+}
+
+/** \brief Calculates line segments to hatch a circle.
+ *
+ * This function appends new line segments to the lines GArray. For creating
+ * a hatch pattern, the GArray must be cleared before calling this function.
+ * For creating cross hatch patterns, this function can be called multiple
+ * times with a different angle or pitch while passing the same lines GArray.
+ *
+ * \param circle [in] The circle shape to hatch.
+ * \param angle [in] The angle of the hatch lines with respect to the x axis.
+ * \param pitch [in] The distance between hatch lines
+ * \param lines [inout] A GArray of LINE to contain the new hatch line
+ * segments. This function appends new line segments to the GArray and leaves
+ * existing GArray contents unchanged.
+ */
+void m_hatch_circle(CIRCLE *circle, gint angle, gint pitch, GArray *lines)
+{
+ gint radius;
+ gint sweep_y;
+ TRANSFORM transform;
+
+ g_return_if_fail(circle!=NULL);
+ g_return_if_fail(lines!=NULL);
+
+ m_transform_init(&transform);
+ m_transform_rotate(&transform, angle);
+ m_transform_scale(&transform, 0.01);
+ m_transform_translate(&transform, circle->center_x, circle->center_y );
+
+ radius = 100 * circle->radius;
+ /* FIXME Not the best way to calculate the initial sweep line */
+ sweep_y = -radius;
+
+ while ( sweep_y < radius ) {
+ LINE line;
+ gint x = round(sqrt(radius*radius - sweep_y*sweep_y));
+
+ line.x[0] = -x;
+ line.y[0] = sweep_y;
+ line.x[1] = x;
+ line.y[1] = sweep_y;
+
+ m_transform_line(&transform, &line);
+ g_array_append_val(lines, line);
+
+ sweep_y += 100 * pitch;
+ }
+}
+
+/** \brief Calculates line segments to hatch an arbitrary polygon.
+ *
+ * This function appends new line segments to the lines GArray. For creating
+ * a hatch pattern, the GArray must be cleared before calling this function.
+ * For creating cross hatch patterns, this function can be called multiple
+ * times with a different angle or pitch while passing the same lines GArray.
+ *
+ * \param points [in] The endpoints of the arbitrary closed polygon to hatch.
+ * \param angle [in] The angle of the hatch lines with respect to the x axis.
+ * \param pitch [in] The distance between hatch lines. This value must be
+ * greater than zero.
+ * \param lines [inout] A GArray of LINE to contain the new hatch line
+ * segments. This function appends new line segments to the GArray and leaves
+ * existing GArray contents unchanged.
+ */
+void m_hatch_polygon(GArray *points, gint angle, gint pitch, GArray *lines)
+{
+ GArray *events;
+ TRANSFORM inverse;
+ GArray *points2;
+ GArray *status;
+ gint sweep_y;
+ TRANSFORM transform;
+
+ g_return_if_fail(points!=NULL);
+ g_return_if_fail(pitch>0);
+ g_return_if_fail(lines!=NULL);
+
+ events = g_array_new(FALSE, FALSE, sizeof(SWEEP_EVENT));
+ points2 = g_array_sized_new(FALSE, FALSE, sizeof(POINT), points->len);
+ status = g_array_new(FALSE, FALSE, sizeof(SWEEP_STATUS));
+
+ m_transform_init(&transform);
+ m_transform_scale(&transform, 10);
+ m_transform_rotate(&transform, angle);
+ m_transform_invert(&transform, &inverse);
+
+ g_array_append_vals(points2, points->data, points->len);
+ m_transform_points(&transform, points2);
+
+ /* build list of sweep events */
+ if ( points2->len > 1 ) {
+ gint index;
+ POINT *p0 = &g_array_index(points2, POINT, points2->len-1);
+ for (index=0; index<points2->len; index++) {
+ POINT *p1 = &g_array_index(points2, POINT, index);
+ if ( p0->y != p1->y ) {
+ SWEEP_EVENT event;
+ event.y0 = min(p0->y, p1->y);
+ event.status.y1 = max(p0->y, p1->y);
+ event.status.m1 = (gdouble)( p1->x - p0->x ) / (gdouble)( p1->y -
p0->y );
+ event.status.b1 = p0->x - event.status.m1 * p0->y;
+ g_array_append_val(events, event);
+ }
+ p0 = p1;
+ }
+ }
+
+ /* sort sweep events in ascending order by starting y coordinate */
+ g_array_sort(events, compare_events);
+
+ /* FIXME Not the best way to calculate the initial sweep line */
+ if ( events->len > 0 ) {
+ sweep_y = g_array_index(events, SWEEP_EVENT, 0).y0;
+ }
+
+ while ( events->len > 0 || status->len > 0 ) {
+ gint index;
+
+ /* add new segments that intersect the sweep line */
+ index = 0;
+ while ( index < events->len ) {
+ SWEEP_EVENT *event = &g_array_index(events, SWEEP_EVENT, index);
+ if ( sweep_y >= event->y0 ) {
+ SWEEP_STATUS st = event->status;
+ g_array_append_val(status, st);
+ g_array_remove_index(events, index);
+ } else {
+ index++;
+ }
+ }
+
+ /* remove status no longer intersecting sweep line */
+ index = status->len;
+ while ( index-- > 0 ) {
+ if ( sweep_y > g_array_index(status, SWEEP_STATUS, index).y1 ) {
+ g_array_remove_index_fast(status, index);
+ }
+ }
+
+ /* (re)calculate x coordinates at sweep line */
+ for (index=0; index<status->len; index++) {
+ SWEEP_STATUS *st = &g_array_index(status, SWEEP_STATUS, index);
+ st->x = st->m1 * sweep_y + st->b1;
+ }
+
+ /* sort the sweep status in ascending order by x coordinate */
+ g_array_sort(status, compare_status);
+
+ /* draw hatch segments */
+ index = 0;
+ while ( index+1 < status->len ) {
+ LINE line;
+ line.x[0] = g_array_index(status, SWEEP_STATUS, index ).x;
+ line.y[0] = sweep_y;
+ line.x[1] = g_array_index(status, SWEEP_STATUS, index+1 ).x;
+ line.y[1] = sweep_y;
+ m_transform_line(&inverse, &line);
+ g_array_append_val(lines, line);
+ index += 2;
+ }
+
+ sweep_y += 10 * pitch;
+ }
+
+ g_array_free(events, TRUE);
+ g_array_free(points2, TRUE);
+ g_array_free(status, TRUE);
+}
+
diff --git a/libgeda/src/m_transform.c b/libgeda/src/m_transform.c
new file mode 100644
index 0000000..8c028fd
--- /dev/null
+++ b/libgeda/src/m_transform.c
@@ -0,0 +1,209 @@
+/* gEDA - GPL Electronic Design Automation
+ * libgeda - gEDA's library
+ * Copyright (C) 1998-2008 Ales Hvezda
+ * Copyright (C) 1998-2008 gEDA Contributors (see ChangeLog for details)
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111 USA
+ */
+#include <config.h>
+#include <math.h>
+#include <libgeda_priv.h>
+
+/** \brief Combines two transformations
+ *
+ * Combines two matricies using matrix multiplication: a*b.
+ *
+ * \param result [out] The resulting transformation. If either operand is
+ * NULL, the contents of the result remain unaltered.
+ * \param transform0 [in] The first operand.
+ * \param transform1 [in] The second operand.
+ */
+void m_transform_combine(TRANSFORM *result, TRANSFORM *a, TRANSFORM *b )
+{
+ g_return_if_fail(result!=NULL);
+ g_return_if_fail(a!=NULL);
+ g_return_if_fail(b!=NULL);
+
+ result->m[0][0] = a->m[0][0] * b->m[0][0] + a->m[0][1] * b->m[1][0];
+ result->m[0][1] = a->m[0][0] * b->m[0][1] + a->m[0][1] * b->m[1][1];
+ result->m[0][2] = a->m[0][0] * b->m[0][2] + a->m[0][1] * b->m[1][2] +
a->m[0][2];
+ result->m[1][0] = a->m[1][0] * b->m[0][0] + a->m[1][1] * b->m[1][0];
+ result->m[1][1] = a->m[1][0] * b->m[0][1] + a->m[1][1] * b->m[1][1];
+ result->m[1][2] = a->m[1][0] * b->m[0][2] + a->m[1][1] * b->m[1][2] +
a->m[1][2];
+}
+
+/** \brief Initialize a transform with the identity matrix.
+ *
+ * \param transform [out] The transform to initialize with the identity
matrix.
+ */
+void m_transform_init(TRANSFORM *transform)
+{
+ g_return_if_fail(transform!=NULL);
+
+ transform->m[0][0] = 1;
+ transform->m[0][1] = 0;
+ transform->m[0][2] = 0;
+ transform->m[1][0] = 0;
+ transform->m[1][1] = 1;
+ transform->m[1][2] = 0;
+}
+
+/** \brief Calculates the inverse transform
+ *
+ * \param transform [in] The given matrix
+ * \param inverse [out] The inverse of the given matrix.
+ */
+void m_transform_invert(TRANSFORM *transform, TRANSFORM *inverse)
+{
+ gdouble d;
+
+ g_return_if_fail(transform!=NULL);
+ g_return_if_fail(inverse!=NULL);
+
+ d = transform->m[0][0]*transform->m[1][1] -
transform->m[1][0]*transform->m[0][1];
+
+ inverse->m[0][0] = transform->m[1][1] / d;
+ inverse->m[0][1] = -transform->m[0][1] / d;
+ inverse->m[0][2] = ( transform->m[0][1]*transform->m[1][2] -
transform->m[1][1]*transform->m[0][2] ) / d;
+ inverse->m[1][0] = -transform->m[1][0] / d;
+ inverse->m[1][1] = transform->m[0][0] / d;
+ inverse->m[1][2] = -( transform->m[0][0]*transform->m[1][2] -
transform->m[1][0]*transform->m[0][2] ) / d;
+}
+
+/** \brief Transforms a line segment
+ *
+ * \param transform [in] The transform function.
+ * \param line [inout] The line to transform.
+ */
+void m_transform_line(TRANSFORM *transform, LINE *line)
+{
+ g_return_if_fail(transform!=NULL);
+ g_return_if_fail(line!=NULL);
+
+ m_transform_point(transform, &(line->x[0]), &(line->y[0]));
+ m_transform_point(transform, &(line->x[1]), &(line->y[1]));
+}
+
+/** \brief Transforms multiple line segments
+ *
+ * \param transform [in] The transform function.
+ * \param line [inout] The GArray of LINE to transform.
+ */
+void m_transform_lines(TRANSFORM *transform, GArray *lines)
+{
+ gint index;
+
+ g_return_if_fail(transform!=NULL);
+ g_return_if_fail(lines!=NULL);
+
+ for (index=0; index<lines->len; index++) {
+ LINE *line = &g_array_index(lines, LINE, index);
+ m_transform_line(transform, line);
+ }
+}
+
+/** \brief Transforms a point
+ *
+ * \param x [inout] The x coordinate to transform.
+ * \param y [inout] The y coordinate to transform.
+ * \param transform [in] The transform function.
+ */
+void m_transform_point(TRANSFORM *transform, gint *x, gint *y)
+{
+ gdouble tx;
+ gdouble ty;
+
+ g_return_if_fail(transform!=NULL);
+ g_return_if_fail(x!=NULL);
+ g_return_if_fail(y!=NULL);
+
+ tx = *x;
+ ty = *y;
+
+ *x = round(transform->m[0][0] * tx + transform->m[0][1] * ty +
transform->m[0][2]);
+ *y = round(transform->m[1][0] * tx + transform->m[1][1] * ty +
transform->m[1][2]);
+}
+
+/** \brief Transforms a polyline or polygon
+ *
+ * \param transform [in] The transform function.
+ * \param line [inout] The GArray of POINT to transform.
+ */
+void m_transform_points(TRANSFORM *transform, GArray *points)
+{
+ gint index;
+
+ g_return_if_fail(transform!=NULL);
+ g_return_if_fail(points!=NULL);
+
+ for (index=0; index<points->len; index++) {
+ POINT *point = &g_array_index(points, POINT, index);
+ m_transform_point(transform, &(point->x), &(point->y));
+ }
+}
+
+/** \brief Adds a rotation to the transformation
+ *
+ * \param transform [inout] The given matrix
+ * \param angle [in] The angle to rotate
+ */
+void m_transform_rotate(TRANSFORM *transform, gdouble angle)
+{
+ gdouble r = G_PI*angle/180.0;
+ gdouble c = cos(r);
+ gdouble s = sin(r);
+ TRANSFORM temp;
+
+ g_return_if_fail(transform!=NULL);
+
+ temp = *transform;
+
+ transform->m[0][0] = temp.m[0][0] * c + temp.m[0][1] * s;
+ transform->m[0][1] = temp.m[0][0] * -s + temp.m[0][1] * c;
+ transform->m[1][0] = temp.m[1][0] * c + temp.m[1][1] * s;
+ transform->m[1][1] = temp.m[1][0] * -s + temp.m[1][1] * c;
+}
+
+/** \brief Adds a scaling to the transformation
+ *
+ * \param transform [inout] The given matrix
+ * \param factor [in] The amount to scale the transform. This parameter must
+ * not be zero, or the matrix becomes singular.
+ */
+void m_transform_scale(TRANSFORM *transform, gdouble factor)
+{
+ g_return_if_fail(transform!=NULL);
+ g_return_if_fail(factor!=0);
+
+ transform->m[0][0] *= factor;
+ transform->m[0][1] *= factor;
+ transform->m[1][0] *= factor;
+ transform->m[1][1] *= factor;
+}
+
+/** \brief Adds a translation to the transformation
+ *
+ * \param transform [inout] The given matrix.
+ * \param dx [in] The amount to translate on the x axis.
+ * \param dy [in] The amount to translate on the y axis.
+ */
+void m_transform_translate(TRANSFORM *transform, gdouble dx, gdouble dy)
+{
+ g_return_if_fail(transform!=NULL);
+
+ transform->m[0][2] += dx;
+ transform->m[1][2] += dy;
+}
+
--
1.5.4.3
_______________________________________________
geda-dev mailing list
[email protected]
http://www.seul.org/cgi-bin/mailman/listinfo/geda-dev
