From 4a676722037d9d6d7152c112fbaff1b6e85959d4 Mon Sep 17 00:00:00 2001
From: Edward Hennessy <[EMAIL PROTECTED]>
Date: Thu, 6 Nov 2008 03:16:39 -0800
Subject: [PATCH] Implemented distance selection mechaism for path objects
This patch implements the distance calculation to path objects that may
include both line segments and Bezier curves. Also, the distance from
a point to a line (o_line_shortest_distance()) is enhanced to handle the
case where both endpoints are equal.
---
libgeda/include/prototype_priv.h | 2 +-
libgeda/src/m_polygon.c | 46 ++++++++++++++++++++++++++++++-----
libgeda/src/o_line_basic.c | 36 +++++++++++++++++----------
libgeda/src/o_path_basic.c | 49 +++++++++++--------------------------
4 files changed, 78 insertions(+), 55 deletions(-)
diff --git a/libgeda/include/prototype_priv.h b/libgeda/include/prototype_priv.h
index 060c507..e23b0c6 100644
--- a/libgeda/include/prototype_priv.h
+++ b/libgeda/include/prototype_priv.h
@@ -62,7 +62,7 @@ void m_hatch_polygon(GArray *points, gint angle, gint pitch,
GArray *lines);
/* m_polygon.c */
gboolean m_polygon_interior_point(GArray *points, gint x, gint y);
-gdouble m_polygon_shortest_distance(GArray *points, gint x, gint y, gboolean
solid);
+gdouble m_polygon_shortest_distance(GArray *points, gint x, gint y, gboolean
closed);
/* m_transform.c */
void m_transform_combine(TRANSFORM *result, TRANSFORM *a, TRANSFORM *b );
diff --git a/libgeda/src/m_polygon.c b/libgeda/src/m_polygon.c
index 1618861..ffacd24 100644
--- a/libgeda/src/m_polygon.c
+++ b/libgeda/src/m_polygon.c
@@ -142,18 +142,50 @@ gboolean m_polygon_interior_point(GArray *points, gint x,
gint y)
}
/*! \brief Calculates the distance between the given point and the closest
- * point on the interior or perimeter of the polygon.
+ * point on the perimeter of the polygon.
*
- * \param [in] points The polygon, where polygon != NULL.
- * \param [in] x The x coordinate of the given point.
- * \param [in] y The y coordinate of the given point.
+ * \param points [in] The polygon, where polygon != NULL.
+ * \param x [in] The x coordinate of the given point.
+ * \param y [in] The y coordinate of the given point.
+ * \param closed [in] If TRUE, the function treats the polygon as a closed
+ * shape, creating a line between the first and last points, if needed. If
+ * the first and last points are equal, or inherintly closed, this parameter
+ * does not matter.
* \return The shortest distance from the polygon to the point. With an
* invalid parameter, this function returns G_MAXDOUBLE.
*/
-gdouble m_polygon_shortest_distance(GArray *points, gint x, gint y, gboolean
solid)
+gdouble m_polygon_shortest_distance(GArray *points, gint x, gint y, gboolean
closed)
{
- /* TODO Implement */
+ gdouble shortest = G_MAXDOUBLE;
+
+ if (points->len > 0) {
+ gint index = 0;
+ sPOINT point;
+
+ if (closed) {
+ point = g_array_index(points, sPOINT, points->len-1);
+ } else {
+ point = g_array_index(points, sPOINT, index++);
+ }
+
+ while (index < points->len) {
+ gdouble distance;
+ LINE line;
+
+ line.x[0] = point.x;
+ line.y[0] = point.y;
+
+ point = g_array_index(points, sPOINT, index++);
+
+ line.x[1] = point.x;
+ line.y[1] = point.y;
+
+ distance = o_line_shortest_distance(&line, x, y);
+
+ shortest = min(shortest, distance);
+ }
+ }
- return G_MAXDOUBLE;
+ return shortest;
}
diff --git a/libgeda/src/o_line_basic.c b/libgeda/src/o_line_basic.c
index c0fab50..86652da 100644
--- a/libgeda/src/o_line_basic.c
+++ b/libgeda/src/o_line_basic.c
@@ -1225,6 +1225,9 @@ double o_line_length(OBJECT *object)
* end point, this function returns the distance from the given point to the
* closest end point.
*
+ * If the line represents a single point (the endpoints are the same), this
+ * function calcualtes the distance to that point.
+ *
* \param [in] line The line of an OBJECT
* \param [in] x The x coordinate of the given point.
* \param [in] y The y coordinate of the given point.
@@ -1256,23 +1259,30 @@ gdouble o_line_shortest_distance(LINE *line, gint x,
gint y)
ldx = ((double) line->x[1]) - ((double) line->x[0]);
ldy = ((double) line->y[1]) - ((double) line->y[0]);
- /* calculate parametric value of perpendicular intersection */
- dx0 = ldx * ( x - lx0 );
- dy0 = ldy * ( y - ly0 );
+ if ( ldx == 0 && ldy == 0 ) {
+ /* if line is a point, just calculate distance to the point */
+ dx = x-lx0;
+ dy = y-ly0;
+
+ } else {
+ /* calculate parametric value of perpendicular intersection */
+ dx0 = ldx * ( x - lx0 );
+ dy0 = ldy * ( y - ly0 );
- t = (dx0 + dy0) / ((ldx*ldx) + (ldy*ldy));
+ t = (dx0 + dy0) / ((ldx*ldx) + (ldy*ldy));
- /* constrain the parametric value to a point on the line */
- t = max(t, 0);
- t = min(t, 1);
+ /* constrain the parametric value to a point on the line */
+ t = max(t, 0);
+ t = min(t, 1);
- /* calculate closest point on the line */
- cx = t * ldx + lx0;
- cy = t * ldy + ly0;
+ /* calculate closest point on the line */
+ cx = t * ldx + lx0;
+ cy = t * ldy + ly0;
- /* calculate distance to closest point */
- dx = x-cx;
- dy = y-cy;
+ /* calculate distance to closest point */
+ dx = x-cx;
+ dy = y-cy;
+ }
shortest_distance = sqrt( (dx*dx) + (dy*dy) );
diff --git a/libgeda/src/o_path_basic.c b/libgeda/src/o_path_basic.c
index 08b00b9..c6f6a41 100644
--- a/libgeda/src/o_path_basic.c
+++ b/libgeda/src/o_path_basic.c
@@ -1045,8 +1045,6 @@ void o_path_print(TOPLEVEL *toplevel, FILE *fp, OBJECT
*o_current,
/*! \brief Calculates the distance between the given point and the closest
* point on the given path segment.
*
- * \todo Support for bezier path segments.
- *
* \param [in] object The path OBJECT
* \param [in] x The x coordinate of the given point.
* \param [in] y The y coordinate of the given point.
@@ -1055,45 +1053,28 @@ void o_path_print(TOPLEVEL *toplevel, FILE *fp, OBJECT
*o_current,
*/
gdouble o_path_shortest_distance (OBJECT *object, gint x, gint y)
{
- PATH_SECTION *section;
- LINE line;
+ GArray *points;
gdouble shortest = G_MAXDOUBLE;
- int last_x = 0, last_y = 0;
- int i;
+ gboolean solid;
- for (i = 0; i < object->path->num_sections; i++) {
- section = &object->path->sections[i];
- switch (section->code) {
+ points = g_array_new(FALSE, FALSE, sizeof(sPOINT));
- case PATH_CURVETO:
- /* TODO: Shortest distance to a besier section of the path.
- * For now, pretend it is a straight line. */
- /* Fall through */
- case PATH_LINETO:
- line.x[0] = last_x;
- line.y[0] = last_y;
- line.x[1] = last_x = section->x3;
- line.y[1] = last_y = section->y3;
- shortest = MIN (shortest, o_line_shortest_distance (&line, x, y));
- break;
+ s_path_to_polygon(object->path, points);
- case PATH_MOVETO:
- case PATH_MOVETO_OPEN:
- last_x = section->x3;
- last_y = section->y3;
- break;
+ solid = object->fill_type != FILLING_HOLLOW; /* FIXME */
- case PATH_END:
- /* Need to consider the line back to the first point in the path */
- line.x[0] = last_x;
- line.y[0] = last_y;
- line.x[1] = last_x = object->path->sections[0].x3;
- line.y[1] = last_y = object->path->sections[0].y3;
- shortest = MIN (shortest, o_line_shortest_distance (&line, x, y));
- break;
- }
+ if (!solid) {
+ shortest = m_polygon_shortest_distance(points, x, y, FALSE);
+
+ } else if (m_polygon_interior_point(points, x, y)) {
+ shortest = 0;
+
+ } else {
+ shortest = m_polygon_shortest_distance(points, x, y, TRUE);
}
+ g_array_free(points, TRUE);
+
return shortest;
}
--
1.5.4.3
_______________________________________________
geda-dev mailing list
geda-dev@moria.seul.org
http://www.seul.org/cgi-bin/mailman/listinfo/geda-dev
