← Back to branch summary

~ubuntu-branches/ubuntu/vivid/grass/vivid-proposed

« back to all changes in this revision

Viewing changes to vector/v.delaunay/in_out.c

  • Committer: Package Import Robot
  • Author(s): Bas Couwenberg
  • Date: 2015-02-20 23:12:08 UTC
  • mfrom: (8.2.6 experimental)
  • Revision ID: package-import@ubuntu.com-20150220231208-1u6qvqm84v430b10
Tags: 7.0.0-1~exp1
* New upstream release.
* Update python-ctypes-ternary.patch to use if/else instead of and/or.
* Drop check4dev patch, rely on upstream check.
* Add build dependency on libpq-dev to grass-dev for libpq-fe.h.
* Drop patches applied upstream, refresh remaining patches.
* Update symlinks for images switched from jpg to png.

Show diffs side-by-side

added added

removed removed

Lines of Context:
vector/v.delaunay/in_out.c
 
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
#include <stdio.h>
 
46
#include <stdlib.h>
 
47
#include <math.h>
 
48
#include <unistd.h>
 
49
#include <grass/gis.h>
 
50
#include <grass/vector.h>
 
51
#include <grass/glocale.h>
 
52
#include "defs.h"
 
53
#include "data_types.h"
 
54
#include "memory.h"
 
55
#include "edge.h"
 
56
 
 
57
/* compare first according to x-coordinate, if equal then y-coordinate */
 
58
int cmp(const void *a, const void *b)
 
59
{
 
60
    struct vertex *p1 = (struct vertex *)a;
 
61
    struct vertex *p2 = (struct vertex *)b;
 
62
 
 
63
    if (p1->x < p2->x)
 
64
        return 1;
 
65
    else if (p1->x > p2->x)
 
66
        return -1;
 
67
    else {
 
68
        if (p1->y < p2->y)
 
69
            return 1;
 
70
        else if (p1->y > p2->y)
 
71
            return -1;
 
72
    }
 
73
    
 
74
    return 0;
 
75
}
 
76
 
 
77
void output_edges(unsigned int n, int mode3d, int type,
 
78
                  struct Map_info *Out)
 
79
{
 
80
    struct edge *e_start, *e;
 
81
    struct vertex *u, *v;
 
82
    unsigned int i;
 
83
    double x1, y1, z1, x2, y2, z2;
 
84
 
 
85
    static struct line_pnts *Points = NULL;
 
86
    static struct line_cats *Cats = NULL;
 
87
 
 
88
    if (!Points) {
 
89
        Points = Vect_new_line_struct();
 
90
        Cats = Vect_new_cats_struct();
 
91
    }
 
92
 
 
93
    G_message(_("Writing edges..."));
 
94
    for (i = 0; i < n; i++) {
 
95
        G_percent(i, n, 2);
 
96
        u = &(sites[i]);
 
97
        e_start = e = u->entry_pt;
 
98
        do {
 
99
            v = OTHER_VERTEX(e, u);
 
100
            if (cmp(u, v) == 1) {
 
101
                x1 = u->x;
 
102
                y1 = u->y;
 
103
                z1 = u->z;
 
104
                x2 = v->x;
 
105
                y2 = v->y;
 
106
                z2 = v->z;
 
107
 
 
108
                Vect_reset_line(Points);
 
109
 
 
110
                Vect_append_point(Points, x1, y1, z1);
 
111
                Vect_append_point(Points, x2, y2, z2);
 
112
                Vect_write_line(Out, type, Points, Cats);
 
113
            }
 
114
            e = NEXT(e, u);
 
115
        } while (!SAME_EDGE(e, e_start));
 
116
    }
 
117
    G_percent(1, 1, 1);
 
118
}
 
119
 
 
120
/* Print the ring of triangles about each vertex. */
 
121
 
 
122
void output_triangles(unsigned int n,
 
123
                      int mode3d, int type, struct Map_info *Out)
 
124
{
 
125
    struct edge *e_start, *e, *next;
 
126
    struct vertex *u, *v, *w;
 
127
    unsigned int i;
 
128
    struct vertex *temp;
 
129
 
 
130
    struct line_pnts *Points = Vect_new_line_struct();
 
131
    struct line_cats *Cats = Vect_new_cats_struct();
 
132
 
 
133
    double x1, y1, z1, x2, y2, z2, x3, y3, z3;
 
134
 
 
135
    for (i = 0; i < n; i++) {
 
136
        u = &(sites[i]);
 
137
        e_start = e = u->entry_pt;
 
138
        do {
 
139
            v = OTHER_VERTEX(e, u);
 
140
            if (cmp(u, v) == 1) {
 
141
                next = NEXT(e, u);
 
142
                w = OTHER_VERTEX(next, u);
 
143
                if (cmp(u, w) == 1)
 
144
                    if (SAME_EDGE(NEXT(next, w), PREV(e, v))) {
 
145
                        /* Triangle. */
 
146
                        if (cmp(w, v) == 1) {
 
147
                            temp = v;
 
148
                            v = w;
 
149
                            w = temp;
 
150
                        }
 
151
                        x1 = u->x;
 
152
                        y1 = u->y;
 
153
                        x2 = v->x;
 
154
                        y2 = v->y;
 
155
                        x3 = w->x;
 
156
                        y3 = w->y;
 
157
                        z1 = u->z;
 
158
                        z2 = v->z;
 
159
                        z3 = w->z;
 
160
 
 
161
                        Vect_reset_line(Points);
 
162
                        Vect_append_point(Points, x1, y1, z1);
 
163
                        Vect_append_point(Points, x2, y2, z2);
 
164
                        Vect_write_line(Out, type, Points, Cats);
 
165
 
 
166
                        Vect_reset_line(Points);
 
167
                        Vect_append_point(Points, x2, y2, z2);
 
168
                        Vect_append_point(Points, x3, y3, z3);
 
169
                        Vect_write_line(Out, type, Points, Cats);
 
170
 
 
171
                        Vect_reset_line(Points);
 
172
                        Vect_append_point(Points, x3, y3, z3);
 
173
                        Vect_append_point(Points, x1, y1, z1);
 
174
                        Vect_write_line(Out, type, Points, Cats);
 
175
                    }
 
176
            }
 
177
            /* Next edge around u. */
 
178
            e = NEXT(e, u);
 
179
        } while (!SAME_EDGE(e, e_start));
 
180
    }
 
181
}
 
182
 
 
183
void remove_duplicates(unsigned int *size)
 
184
{
 
185
    unsigned int n = *size;
 
186
    unsigned int prev = 0;
 
187
    unsigned int next;
 
188
 
 
189
    if (n > 0) {
 
190
        for (next = 1; next < n; next++) {
 
191
            if (sites[prev].x != sites[next].x ||
 
192
                sites[prev].y != sites[next].y)
 
193
                sites[++prev] = sites[next];
 
194
        }
 
195
        *size = prev + 1;
 
196
    }
 
197
}
 
198
 
 
199
/* returns number of sites read */
 
200
int read_sites(int mode3d, int complete_map, struct Map_info* map_in,
 
201
               struct bound_box Box, int field)
 
202
{
 
203
    int nlines, line, nsites;
 
204
    struct line_pnts *Points;
 
205
    struct line_cats *Cats;
 
206
    
 
207
    Points = Vect_new_line_struct();
 
208
    Cats = Vect_new_cats_struct();
 
209
 
 
210
    nlines = Vect_get_num_lines(map_in);
 
211
    alloc_sites(nlines);
 
212
    
 
213
    nsites = 0;
 
214
    G_message(_("Reading point features..."));
 
215
    for (line = 1; line <= nlines; line++) {
 
216
        int type;
 
217
 
 
218
        G_percent(line, nlines, 2);
 
219
        type = Vect_read_line(map_in, Points, Cats, line);
 
220
        if (!(type & GV_POINTS))
 
221
            continue;
 
222
        
 
223
        if (field != -1 && Vect_cat_get(Cats, field, NULL) == 0)
 
224
            continue;
 
225
        
 
226
        if (!complete_map) {
 
227
            if (!Vect_point_in_box(Points->x[0], Points->y[0], 0.0, &Box))
 
228
                continue;
 
229
        }
 
230
        sites[nsites].x = Points->x[0];
 
231
        sites[nsites].y = Points->y[0];
 
232
        if (mode3d) {
 
233
            G_debug(3, "Points->z[0]: %f", Points->z[0]);
 
234
            sites[nsites].z = Points->z[0];
 
235
        }
 
236
        else {
 
237
            sites[nsites].z = 0.0;
 
238
        }
 
239
        /* Initialise entry edge vertices. */
 
240
        sites[nsites].entry_pt = NULL;
 
241
 
 
242
        nsites++;
 
243
#if 0
 
244
        /* number 100 was arbitrarily chosen */
 
245
        if (nsites == allocated && line != nlines){
 
246
            allocated += 100;
 
247
            realloc_sites(allocated);
 
248
        }
 
249
#endif
 
250
    }
 
251
    if (nsites != nlines)
 
252
        realloc_sites(nsites);
 
253
    alloc_edges(nsites);
 
254
 
 
255
    Vect_destroy_line_struct(Points);
 
256
    Vect_destroy_cats_struct(Cats);
 
257
 
 
258
    return nsites;
 
259
}