improved zapper using psfind
[feisty_meow.git] / graphiq / library / geometric / polygon.cpp
1
2
3
4 /*****************************************************************************\
5 *                                                                             *
6 *  Name   : polygon                                                           *
7 *  Author : Chris Koeritz                                                     *
8 *                                                                             *
9 *******************************************************************************
10 * Copyright (c) 1992-$now By Author.  This program is free software; you can  *
11 * redistribute it and/or modify it under the terms of the GNU General Public  *
12 * License as published by the Free Software Foundation; either version 2 of   *
13 * the License or (at your option) any later version.  This is online at:      *
14 *     http://www.fsf.org/copyleft/gpl.html                                    *
15 * Please send any updates to: fred@gruntose.com                               *
16 \*****************************************************************************/
17
18 #include "polygon.h"
19
20 #include <basis/array.h>
21
22 using namespace basis;
23
24 namespace geometric {
25
26 bool polygon::inside(const cartesian_point &to_check)
27 {
28   int right_intersect_count = 0;
29   for (int i = 0; i < length(); i++) {
30     cartesian_point vert_1 = get(i);
31     cartesian_point vert_2 = get( (i + 1) % length() );
32     if ( (to_check.y() < minimum(vert_1.y(), vert_2.y()))
33         || (to_check.y() > maximum(vert_1.y(), vert_2.y())) ) continue;
34     double x_intersect;
35     if (vert_2.x() == vert_1.x()) {
36       x_intersect = vert_2.x();
37     } else {
38       double m = (vert_2.y() - vert_1.y()) / (vert_2.x() - vert_1.x());
39       x_intersect = 1.0 / m * (to_check.y() - vert_1.y() + m * vert_1.x());
40     }
41     if (x_intersect > to_check.x()) right_intersect_count++;
42   }
43   return !!(right_intersect_count % 2);
44 }
45
46 }
47
48
49
50