1 /*************************************************************** 2 * 3 * MODULE: v.delaunay 4 * 5 * AUTHOR(S): Martin Pavlovsky (Google SoC 2008, Paul Kelly mentor) 6 * Based on "dct" by Geoff Leach, Department of Computer 7 * Science, RMIT. 8 * 9 * PURPOSE: Creates a Delaunay triangulation vector map 10 * 11 * COPYRIGHT: (C) RMIT 1993 12 * (C) 2008-2009 by the GRASS Development Team 13 * 14 * This program is free software under the GNU General 15 * Public License (>=v2). Read the file COPYING that 16 * comes with GRASS for details. 17 * 18 * The following notices apply to portions of the code originally 19 * derived from work by Geoff Leach of RMIT: 20 * 21 * Author: Geoff Leach, Department of Computer Science, RMIT. 22 * email: gl@cs.rmit.edu.au 23 * 24 * Date: 6/10/93 25 * 26 * Version 1.0 27 * 28 * Copyright (c) RMIT 1993. All rights reserved. 29 * 30 * License to copy and use this software purposes is granted provided 31 * that appropriate credit is given to both RMIT and the author. 32 * 33 * License is also granted to make and use derivative works provided 34 * that appropriate credit is given to both RMIT and the author. 35 * 36 * RMIT makes no representations concerning either the merchantability 37 * of this software or the suitability of this software for any particular 38 * purpose. It is provided "as is" without express or implied warranty 39 * of any kind. 40 * 41 * These notices must be retained in any copies of any part of this software. 42 * 43 **************************************************************/ 44 45 #ifndef GEOM_PRIMITIVES_H 46 #define GEOM_PRIMITIVES_H 47 48 #ifndef TRUE 49 #define TRUE 1 50 #endif 51 #ifndef FALSE 52 #define FALSE 0 53 #endif 54 55 #define CREATE_VECTOR(p1, p2, dx, dy) ((dx) = (p2)->x - (p1)->x, (dy) = (p2)->y - (p1)->y) 56 57 #define DOT_PRODUCT_2V(a1, a2, b1, b2) ((a1) * (b1) + (a2) * (b2)) 58 59 #define CROSS_PRODUCT_2V(a1, a2, b1, b2) ((a1) * (b2) - (a2) * (b1)) 60 /* 61 cross-product around p2 62 ((p2->x - p1->x) * (p3->y - p2->y) - (p2->y - p1->y) * (p3->x - p2->x)) 63 64 around p1 65 */ 66 #define CROSS_PRODUCT_3P(p1, p2, p3) (((p2)->x - (p1)->x) * ((p3)->y - (p1)->y) - ((p2)->y - (p1)->y) * ((p3)->x - (p1)->x)) 67 68 /* predicate testing if p3 is to the left of the line through p1 and p2 */ 69 #define LEFT_OF(p1, p2, p3) (CROSS_PRODUCT_3P(p1, p2, p3) > 0) 70 71 /* predicate testing if p3 is to the right of the line through p1 and p2 */ 72 #define RIGHT_OF(p1, p2, p3) (CROSS_PRODUCT_3P(p1, p2, p3) < 0) 73 74 #endif 75