← Back to branch summary

~ubuntu-branches/ubuntu/maverick/gcompris/maverick

« back to all changes in this revision

Viewing changes to src/libart_lgpl/art_svp_point.c

  • Committer: Bazaar Package Importer
  • Author(s): Marc Gariepy, Marc Gariepy, Stephane Graber
  • Date: 2010-01-04 17:42:49 UTC
  • mfrom: (1.1.14 upstream)
  • Revision ID: james.westby@ubuntu.com-20100104174249-7bupatd9dtxyhvs4
Tags: 9.0-0ubuntu1
[Marc Gariepy]
* New upstream release (9.0).
* Remove cache.c from POTFILES to avoid FTBFS
* Remove unneeded rm in debian/rules (file no longer exists upstream)

[Stephane Graber]
* Bump Debian standards to 3.8.3
* Add patch system (dpatch)

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/libart_lgpl/art_svp_point.c
1
 
/* Libart_LGPL - library of basic graphic primitives
2
 
 * Copyright (C) 1999 Raph Levien
3
 
 *
4
 
 * This library is free software; you can redistribute it and/or
5
 
 * modify it under the terms of the GNU Library General Public
6
 
 * License as published by the Free Software Foundation; either
7
 
 * version 3 of the License, or (at your option) any later version.
8
 
 *
9
 
 * This library is distributed in the hope that it will be useful,
10
 
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11
 
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12
 
 * Library General Public License for more details.
13
 
 *
14
 
 * You should have received a copy of the GNU Library General Public
15
 
 * License along with this library; if not, see <http://www.gnu.org/licenses/>.
16
 
 * Boston, MA 02111-1307, USA.
17
 
 */
18
 
 
19
 
#include "config.h"
20
 
#include "art_svp_point.h"
21
 
 
22
 
#include <math.h>
23
 
#include "art_misc.h"
24
 
 
25
 
#include "art_svp.h"
26
 
 
27
 
/* Determine whether a point is inside, or near, an svp. */
28
 
 
29
 
/* return winding number of point wrt svp */
30
 
/**
31
 
 * art_svp_point_wind: Determine winding number of a point with respect to svp.
32
 
 * @svp: The svp.
33
 
 * @x: The X coordinate of the point.
34
 
 * @y: The Y coordinate of the point.
35
 
 *
36
 
 * Determine the winding number of the point @x, @y with respect to @svp.
37
 
 *
38
 
 * Return value: the winding number.
39
 
 **/
40
 
int
41
 
art_svp_point_wind (ArtSVP *svp, double x, double y)
42
 
{
43
 
  int i, j;
44
 
  int wind = 0;
45
 
 
46
 
  for (i = 0; i < svp->n_segs; i++)
47
 
    {
48
 
      ArtSVPSeg *seg = &svp->segs[i];
49
 
 
50
 
      if (seg->bbox.y0 > y)
51
 
        break;
52
 
 
53
 
      if (seg->bbox.y1 > y)
54
 
        {
55
 
          if (seg->bbox.x1 < x)
56
 
            wind += seg->dir ? 1 : -1;
57
 
          else if (seg->bbox.x0 <= x)
58
 
            {
59
 
              double x0, y0, x1, y1, dx, dy;
60
 
 
61
 
              for (j = 0; j < seg->n_points - 1; j++)
62
 
                {
63
 
                  if (seg->points[j + 1].y > y)
64
 
                    break;
65
 
                }
66
 
              x0 = seg->points[j].x;
67
 
              y0 = seg->points[j].y;
68
 
              x1 = seg->points[j + 1].x;
69
 
              y1 = seg->points[j + 1].y;
70
 
 
71
 
              dx = x1 - x0;
72
 
              dy = y1 - y0;
73
 
              if ((x - x0) * dy > (y - y0) * dx)
74
 
                wind += seg->dir ? 1 : -1;
75
 
            }
76
 
        }
77
 
    }
78
 
 
79
 
  return wind;
80
 
}
81
 
 
82
 
/**
83
 
 * art_svp_point_dist: Determine distance between point and svp.
84
 
 * @svp: The svp.
85
 
 * @x: The X coordinate of the point.
86
 
 * @y: The Y coordinate of the point.
87
 
 *
88
 
 * Determines the distance of the point @x, @y to the closest edge in
89
 
 * @svp. A large number is returned if @svp is empty.
90
 
 *
91
 
 * Return value: the distance.
92
 
 **/
93
 
double
94
 
art_svp_point_dist (ArtSVP *svp, double x, double y)
95
 
{
96
 
  int i, j;
97
 
  double dist_sq;
98
 
  double best_sq = -1;
99
 
 
100
 
  for (i = 0; i < svp->n_segs; i++)
101
 
    {
102
 
      ArtSVPSeg *seg = &svp->segs[i];
103
 
      for (j = 0; j < seg->n_points - 1; j++)
104
 
        {
105
 
          double x0 = seg->points[j].x;
106
 
          double y0 = seg->points[j].y;
107
 
          double x1 = seg->points[j + 1].x;
108
 
          double y1 = seg->points[j + 1].y;
109
 
 
110
 
          double dx = x1 - x0;
111
 
          double dy = y1 - y0;
112
 
 
113
 
          double dxx0 = x - x0;
114
 
          double dyy0 = y - y0;
115
 
 
116
 
          double dot = dxx0 * dx + dyy0 * dy;
117
 
 
118
 
          if (dot < 0)
119
 
            dist_sq = dxx0 * dxx0 + dyy0 * dyy0;
120
 
          else
121
 
            {
122
 
              double rr = dx * dx + dy * dy;
123
 
 
124
 
              if (dot > rr)
125
 
                dist_sq = (x - x1) * (x - x1) + (y - y1) * (y - y1);
126
 
              else
127
 
                {
128
 
                  double perp = (y - y0) * dx - (x - x0) * dy;
129
 
 
130
 
                  dist_sq = perp * perp / rr;
131
 
                }
132
 
            }
133
 
          if (best_sq < 0 || dist_sq < best_sq)
134
 
            best_sq = dist_sq;
135
 
        }
136
 
    }
137
 
 
138
 
  if (best_sq >= 0)
139
 
    return sqrt (best_sq);
140
 
  else
141
 
    return 1e12;
142
 
}
143