1 /*
2 * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
3 * http://code.google.com/p/poly2tri/
4 *
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without modification,
8 * are permitted provided that the following conditions are met:
9 *
10 * * Redistributions of source code must retain the above copyright notice,
11 * this list of conditions and the following disclaimer.
12 * * Redistributions in binary form must reproduce the above copyright notice,
13 * this list of conditions and the following disclaimer in the documentation
14 * and/or other materials provided with the distribution.
15 * * Neither the name of Poly2Tri nor the names of its contributors may be
16 * used to endorse or promote products derived from this software without specific
17 * prior written permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
23 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
24 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
25 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
26 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
27 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
28 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
29 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 */
31
32 #ifndef UTILS_H
33 #define UTILS_H
34
35 // Otherwise #defines like M_PI are undeclared under Visual Studio
36 #define _USE_MATH_DEFINES
37
38 #include <exception>
39 #include <math.h>
40
41 namespace p2t {
42
43 const double PI_3div4 = 3 * M_PI / 4;
44 const double EPSILON = 1e-15;
45
46 enum Orientation { CW, CCW, COLLINEAR };
47
48 /**
49 * Forumla to calculate signed area<br>
50 * Positive if CCW<br>
51 * Negative if CW<br>
52 * 0 if collinear<br>
53 * <pre>
54 * A[P1,P2,P3] = (x1*y2 - y1*x2) + (x2*y3 - y2*x3) + (x3*y1 - y3*x1)
55 * = (x1-x3)*(y2-y3) - (y1-y3)*(x2-x3)
56 * </pre>
57 */
Orient2d(Point & pa,Point & pb,Point & pc)58 Orientation Orient2d(Point& pa, Point& pb, Point& pc)
59 {
60 double detleft = (pa.x - pc.x) * (pb.y - pc.y);
61 double detright = (pa.y - pc.y) * (pb.x - pc.x);
62 double val = detleft - detright;
63 if (val > -EPSILON && val < EPSILON) {
64 return COLLINEAR;
65 } else if (val > 0) {
66 return CCW;
67 }
68 return CW;
69 }
70
InScanArea(Point & pa,Point & pb,Point & pc,Point & pd)71 bool InScanArea(Point& pa, Point& pb, Point& pc, Point& pd)
72 {
73 double pdx = pd.x;
74 double pdy = pd.y;
75 double adx = pa.x - pdx;
76 double ady = pa.y - pdy;
77 double bdx = pb.x - pdx;
78 double bdy = pb.y - pdy;
79
80 double adxbdy = adx * bdy;
81 double bdxady = bdx * ady;
82 double oabd = adxbdy - bdxady;
83
84 if (oabd <= EPSILON) {
85 return false;
86 }
87
88 double cdx = pc.x - pdx;
89 double cdy = pc.y - pdy;
90
91 double cdxady = cdx * ady;
92 double adxcdy = adx * cdy;
93 double ocad = cdxady - adxcdy;
94
95 if (ocad <= EPSILON) {
96 return false;
97 }
98
99 return true;
100 }
101
102 }
103
104 #endif
105
106