libgeda/src/m_polygon.c

   1 /* gEDA - GPL Electronic Design Automation
   2  * libgeda - gEDA's library
   3  * Copyright (C) 1998-2010 Ales Hvezda
   4  * Copyright (C) 1998-2010 gEDA Contributors (see ChangeLog for details)
   5  *
   6  * This program is free software; you can redistribute it and/or modify
   7  * it under the terms of the GNU General Public License as published by
   8  * the Free Software Foundation; either version 2 of the License, or
   9  * (at your option) any later version.
  10  *
  11  * This program is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  * GNU General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with this program; if not, write to the Free Software
  18  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  19  */
  20 #include <config.h>
  21 #include <math.h>
  22 #include <string.h>
  23 #include <libgeda_priv.h>
  24
  25 /*! \brief Appends a bezier curve to the polygon
  26  *
  27  *  \param points [inout] The vertices of the polygon. This parameter must not
  28  *  be NULL.
  29  *  \param bezier [in] The bezier curve to append.
  30  *  \param segments [in] The number of segments to subdivide the bezier curve into.
  31  */
  32 void m_polygon_append_bezier (GArray *points, BEZIER *bezier, int segments)
  33 {
  34   m_polygon_append_point (points, bezier->x[0], bezier->y[0]);
  35
  36   if (segments > 1) {
  37     int i;
  38
  39     double a = 3 / (double) segments;
  40     double b = 6 / pow (segments, 2);
  41     double c = 6 / pow (segments, 3);
  42
  43     double x = bezier->x[0];
  44     double xd = a * (bezier->x[1] - bezier->x[0]);
  45     double xdd = b * (bezier->x[0] - 2 * bezier->x[1] + bezier->x[2]);
  46     double xddd = c * (3 * (bezier->x[1] - bezier->x[2]) + bezier->x[3] - bezier->x[0]);
  47
  48     double xdd_div2 = xdd / 2;
  49     double xddd_div2 = xddd / 2;
  50     double xddd_div6 = xddd / 6;
  51
  52     double y = bezier->y[0];
  53     double yd = a * (bezier->y[1] - bezier->y[0]);
  54     double ydd = b * (bezier->y[0] - 2 * bezier->y[1] + bezier->y[2]);
  55     double yddd = c * (3 * (bezier->y[1] - bezier->y[2]) + bezier->y[3] - bezier->y[0]);
  56
  57     double ydd_div2 = ydd / 2;
  58     double yddd_div2 = yddd / 2;
  59     double yddd_div6 = yddd / 6;
  60
  61     for (i=1; i < segments; i++) {
  62       x += xd + xdd_div2 + xddd_div6;
  63       xd += xdd + xddd_div2;
  64       xdd += xddd;
  65       xdd_div2 += xddd_div2;
  66
  67       y += yd + ydd_div2 + yddd_div6;
  68       yd += ydd + yddd_div2;
  69       ydd += yddd;
  70       ydd_div2 += yddd_div2;
  71
  72       m_polygon_append_point (points, round (x), round (y));
  73     }
  74   }
  75
  76   m_polygon_append_point (points, bezier->x[3], bezier->y[3]);
  77 }
  78
  79 /*! \brief Appends a point to the list of vertices in a polygon
  80  *
  81  *  \param points [inout] The vertices of the polygon. This parameter must not
  82  *  be NULL.
  83  *  \param x [in] The x coordinate of the point to append.
  84  *  \param y [in] The y coordinate of the point to append.
  85  */
  86 void m_polygon_append_point (GArray *points, int x, int y)
  87 {
  88   sPOINT point = { x, y };
  89
  90   point.x = x;
  91   point.y = y;
  92
  93   if (points->len == 0 ||
  94       memcmp (&g_array_index (points, sPOINT, points->len - 1),
  95               &point, sizeof (sPOINT)) != 0) {
  96     g_array_append_val (points, point);
  97   }
  98 }
  99
 100 /*! \brief Determines if a point lies inside a polygon
 101  *
 102  *  TODO Untested
 103  *
 104  *  \param points [in] The vertices of the polygon.  This function assumes the
 105  *  list of points represents a closed polygon.  If the first and last point do
 106  *  not match, the line segment between them is implied.  This parameter must
 107  *  not be NULL.
 108  *  \param x [in] The x coordinate of the given point.
 109  *  \param y [in] The y coordinate of the given point.
 110  *  \returns TRUE if the point lies inside the polygon, FALSE if the point lies
 111  *  outside the polygon.
 112  */
 113 gboolean m_polygon_interior_point (GArray *points, int x, int y)
 114 {
 115   int count = 0;
 116
 117   if (points->len > 0) {
 118     int i;
 119     sPOINT p1 = g_array_index (points, sPOINT, points->len - 1);
 120
 121     for (i=0; i < points->len; i++) {
 122       sPOINT p0 = p1;
 123       double xi;
 124
 125       p1 = g_array_index (points, sPOINT, i);
 126
 127       if (y < p0.y && y < p1.y)
 128         continue;
 129
 130       if (y >= p0.y && y >= p1.y)
 131         continue;
 132
 133       xi = ((double) (p1.x - p0.x)) * (y - p0.y) / (p1.y - p0.y) + p0.x;
 134
 135       if (x < xi)
 136         count++;
 137     }
 138   }
 139   return (count % 2) == 1;  /* odd */
 140 }
 141
 142 /*! \brief Calculates the distance between the given point and the closest
 143  *  point on the perimeter of the polygon.
 144  *
 145  *  \param [in] points The polygon, where polygon != NULL.
 146  *  \param [in] x      The x coordinate of the given point.
 147  *  \param [in] y      The y coordinate of the given point.
 148  *  \param [in] closed If TRUE, the function treats the polygon as a closed
 149  *  shape, creating a line between the first and last points, if needed.  If
 150  *  the first and last points are equal, or inherintly closed, this parameter
 151  *  does not matter.
 152  *  \return The shortest distance from the polygon to the point.  With an
 153  *  invalid parameter, this function returns G_MAXDOUBLE.
 154  */
 155 double m_polygon_shortest_distance (GArray *points, int x, int y, gboolean closed)
 156 {
 157   gdouble shortest = G_MAXDOUBLE;
 158
 159   if (points->len > 0) {
 160     int i = 0;
 161     sPOINT point;
 162
 163     if (closed) {
 164       point = g_array_index (points, sPOINT, points->len - 1);
 165     } else {
 166       point = g_array_index (points, sPOINT, i++);
 167     }
 168
 169     while (i < points->len) {
 170       double distance;
 171       LINE line;
 172
 173       line.x[0] = point.x;
 174       line.y[0] = point.y;
 175
 176       point = g_array_index (points, sPOINT, i++);
 177
 178       line.x[1] = point.x;
 179       line.y[1] = point.y;
 180
 181       distance = m_line_shortest_distance (&line, x, y);
 182
 183       shortest = min (shortest, distance);
 184     }
 185   }
 186
 187   return shortest;
 188 }
 189