pgRouting
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
alpha.c
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 FILE: alpha.c
3 
4 Copyright (c) 2006 Anton A. Patrushev, Orkney, Inc.
5 Mail: project@pgrouting.org
6 
7 ------
8 
9 This program is free software; you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation; either version 2 of the License, or
12 (at your option) any later version.
13 
14 This program is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
18 
19 You should have received a copy of the GNU General Public License
20 along with this program; if not, write to the Free Software
21 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
22 
23 ********************************************************************PGR-GNU*/
24 
25 #include "postgres.h"
26 #include "executor/spi.h"
27 #include "funcapi.h"
28 #include "catalog/pg_type.h"
29 #if PGSQL_VERSION > 92
30 #include "access/htup_details.h"
31 #endif
32 
33 #include "../../common/src/pgr_types.h"
34 #include "alpha_driver.h"
35 
36 #include "fmgr.h"
37 
38 
39 /*
40  * Define this to have profiling enabled
41  */
42 // #define PROFILE
43 
44 
45 PGDLLEXPORT
46 Datum alphashape(PG_FUNCTION_ARGS);
47 
48 #undef DEBUG
49 #include "../../common/src/debug_macro.h"
50 
51 // The number of tuples to fetch from the SPI cursor at each iteration
52 #define TUPLIMIT 1000
53 
54 static char *
55 text2char(text *in) {
56  char *out = palloc(VARSIZE(in));
57 
58  memcpy(out, VARDATA(in), VARSIZE(in) - VARHDRSZ);
59  out[VARSIZE(in) - VARHDRSZ] = '\0';
60  return out;
61 }
62 
63 static int
64 finish(int code, int ret) {
65  code = SPI_finish();
66  if (code != SPI_OK_FINISH) {
67  elog(ERROR, "couldn't disconnect from SPI");
68  return -1;
69  }
70  return ret;
71 }
72 
73 
74 typedef struct vertex_columns {
75  int id;
76  int x;
77  int y;
79 
80 
81 
82 static int
83 fetch_vertices_columns(SPITupleTable *tuptable,
85  vertex_columns->id = SPI_fnumber(SPI_tuptable->tupdesc, "id");
86  vertex_columns->x = SPI_fnumber(SPI_tuptable->tupdesc, "x");
87  vertex_columns->y = SPI_fnumber(SPI_tuptable->tupdesc, "y");
88 
89  if (vertex_columns->id == SPI_ERROR_NOATTRIBUTE ||
90  vertex_columns->x == SPI_ERROR_NOATTRIBUTE ||
91  vertex_columns->y == SPI_ERROR_NOATTRIBUTE) {
92  elog(ERROR, "Error, query must return columns "
93  "'id', 'x' and 'y'");
94  return -1;
95  }
96 
97  if (SPI_gettypeid(SPI_tuptable->tupdesc, vertex_columns->id) != INT4OID ||
98  SPI_gettypeid(SPI_tuptable->tupdesc, vertex_columns->x) != FLOAT8OID ||
99  SPI_gettypeid(SPI_tuptable->tupdesc, vertex_columns->y) != FLOAT8OID) {
100  elog(ERROR,
101  "Error, column 'id' must be of type int4, 'x' and 'y' must be of type float8");
102  return -1;
103  }
104 
105  return 0;
106 }
107 
108 static void
109 fetch_vertex(HeapTuple *tuple, TupleDesc *tupdesc,
110  vertex_columns_t *vertex_columns, vertex_t *target_vertex) {
111  Datum binval;
112  bool isnull;
113 
114  binval = SPI_getbinval(*tuple, *tupdesc, vertex_columns->x, &isnull);
115  if (isnull)
116  elog(ERROR, "x contains a null value");
117  target_vertex->x = DatumGetFloat8(binval);
118 
119  binval = SPI_getbinval(*tuple, *tupdesc, vertex_columns->y, &isnull);
120  if (isnull)
121  elog(ERROR, "y contains a null value");
122  target_vertex->y = DatumGetFloat8(binval);
123 }
124 
125 static int compute_alpha_shape(char* sql, float8 alpha, vertex_t **res, size_t *res_count) {
126  int SPIcode;
127  void *SPIplan;
128  Portal SPIportal;
129  bool moredata = TRUE;
130  uint32_t ntuples;
131  vertex_t *vertices = NULL;
132  uint32_t total_tuples = 0;
133 #ifndef _MSC_VER
134  vertex_columns_t vertex_columns = {.id = -1, .x = -1, .y = -1};
135 #else // _MSC_VER
136  vertex_columns_t vertex_columns = {-1, -1, -1};
137 #endif // _MSC_VER
138  char *err_msg;
139  int ret = -1;
140 
141  PGR_DBG("start alpha_shape\n");
142 
143  SPIcode = SPI_connect();
144  if (SPIcode != SPI_OK_CONNECT) {
145  elog(ERROR, "alpha_shape: couldn't open a connection to SPI");
146  return -1;
147  }
148 
149  SPIplan = SPI_prepare(sql, 0, NULL);
150  if (SPIplan == NULL) {
151  elog(ERROR, "alpha_shape: couldn't create query plan via SPI");
152  return -1;
153  }
154 
155  if ((SPIportal = SPI_cursor_open(NULL, SPIplan, NULL, NULL, true)) == NULL) {
156  elog(ERROR, "alpha_shape: SPI_cursor_open('%s') returns NULL", sql);
157  return -1;
158  }
159 
160  while (moredata == TRUE) {
161  SPI_cursor_fetch(SPIportal, TRUE, TUPLIMIT);
162 
163  if (vertex_columns.id == -1) {
164  if (fetch_vertices_columns(SPI_tuptable, &vertex_columns) == -1)
165  return finish(SPIcode, ret);
166  }
167 
168  ntuples = SPI_processed;
169  total_tuples += ntuples;
170  if (!vertices)
171  vertices = palloc(total_tuples * sizeof(vertex_t));
172  else
173  vertices = repalloc(vertices, total_tuples * sizeof(vertex_t));
174 
175  if (vertices == NULL) {
176  elog(ERROR, "Out of memory");
177  return finish(SPIcode, ret);
178  }
179 
180  if (ntuples > 0) {
181  uint32_t t;
182  SPITupleTable *tuptable = SPI_tuptable;
183  TupleDesc tupdesc = SPI_tuptable->tupdesc;
184 
185  for (t = 0; t < ntuples; t++) {
186  HeapTuple tuple = tuptable->vals[t];
187  fetch_vertex(&tuple, &tupdesc, &vertex_columns,
188  &vertices[total_tuples - ntuples + t]);
189  }
190  SPI_freetuptable(tuptable);
191  } else {
192  moredata = FALSE;
193  }
194  }
195 
196 
197  // if (total_tuples < 2) //this was the buggy code of the pgrouting project.
198  // TODO(someone): report this as a bug to the pgrouting project
199  // the CGAL alpha-shape function crashes if called with less than three points!!!
200 
201  if (total_tuples < 3) {
202  elog(ERROR, "Less than 3 vertices. Alpha shape calculation needs at least 3 vertices.");
203  return finish(SPIcode, ret);
204  }
205  if (total_tuples == 1) {
206  elog(ERROR, "Distance is too short. only 1 vertex for alpha shape calculation. alpha shape calculation needs at least 3 vertices.");
207  }
208  if (total_tuples == 2) {
209  elog(ERROR, "Distance is too short. only 2 vertices for alpha shape calculation. alpha shape calculation needs at least 3 vertices.");
210  }
211  if (total_tuples < 3) {
212  // elog(ERROR, "Distance is too short ....");
213  return finish(SPIcode, ret);
214  }
215 
216  PGR_DBG("Calling CGAL alpha-shape\n");
217 
218  ret = alpha_shape(vertices, total_tuples, alpha, res, res_count, &err_msg);
219 
220  if (ret < 0) {
221  // elog(ERROR, "Error computing shape: %s", err_msg);
222  ereport(ERROR, (errcode(ERRCODE_E_R_E_CONTAINING_SQL_NOT_PERMITTED), errmsg("%s", err_msg)));
223  }
224 
225  return finish(SPIcode, ret);
226 }
227 
229 
230 PGDLLEXPORT
231 Datum alphashape(PG_FUNCTION_ARGS) {
232  FuncCallContext *funcctx;
233  uint32_t call_cntr;
234  uint32_t max_calls;
235  TupleDesc tuple_desc;
236  vertex_t *res = 0;
237 
238  /* stuff done only on the first call of the function */
239  if (SRF_IS_FIRSTCALL()) {
240  MemoryContext oldcontext;
241  size_t res_count;
242 
243 
244  /* create a function context for cross-call persistence */
245  funcctx = SRF_FIRSTCALL_INIT();
246 
247  /* switch to memory context appropriate for multiple function calls */
248  oldcontext = MemoryContextSwitchTo(funcctx->multi_call_memory_ctx);
249 
250  compute_alpha_shape(text2char(PG_GETARG_TEXT_P(0)),
251  PG_GETARG_FLOAT8(1), &res, &res_count);
252 
253  /* total number of tuples to be returned */
254  PGR_DBG("Conting tuples number\n");
255  funcctx->max_calls = (uint32_t)res_count;
256  funcctx->user_fctx = res;
257 
258  PGR_DBG("Total count %lu", res_count);
259 
260  if (get_call_result_type(fcinfo, NULL, &tuple_desc) != TYPEFUNC_COMPOSITE)
261  ereport(ERROR,
262  (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
263  errmsg("function returning record called in context "
264  "that cannot accept type record")));
265 
266  funcctx->tuple_desc = BlessTupleDesc(tuple_desc);
267 
268  MemoryContextSwitchTo(oldcontext);
269  }
270 
271  /* stuff done on every call of the function */
272  PGR_DBG("Strange stuff doing\n");
273  funcctx = SRF_PERCALL_SETUP();
274 
275  call_cntr = funcctx->call_cntr;
276  max_calls = funcctx->max_calls;
277  tuple_desc = funcctx->tuple_desc;
278  res = (vertex_t*) funcctx->user_fctx;
279 
280  PGR_DBG("Trying to allocate some memory\n");
281 
282  if (call_cntr < max_calls) {
283  /* do when there is more left to send */
284  HeapTuple tuple;
285  Datum result;
286  Datum *values;
287  bool* nulls;
288  double x;
289  double y;
290 
291  /* This will work for some compilers. If it crashes with segfault, try to change the following block with this one
292 
293  values = palloc(3 * sizeof(Datum));
294  nulls = palloc(3 * sizeof(char));
295 
296  values[0] = call_cntr;
297  nulls[0] = ' ';
298  values[1] = Float8GetDatum(res[call_cntr].x);
299  nulls[1] = ' ';
300  values[2] = Float8GetDatum(res[call_cntr].y);
301  nulls[2] = ' ';
302  */
303 
304  values = palloc(2 * sizeof(Datum));
305  nulls = palloc(2 * sizeof(bool));
306 
307  x = res[call_cntr].x;
308  y = res[call_cntr].y;
309  if (x == DBL_MAX && y == DBL_MAX) {
310  values[0] = 0;
311  values[1] = 0;
312  nulls[0] = true;
313  nulls[1] = true;
314  } else {
315  values[0] = Float8GetDatum(x);
316  values[1] = Float8GetDatum(y);
317  nulls[0] = false;
318  nulls[1] = false;
319  }
320 
321  PGR_DBG("Heap making\n");
322 
323  tuple = heap_form_tuple(tuple_desc, values, nulls);
324 
325  PGR_DBG("Datum making\n");
326 
327  /* make the tuple into a datum */
328  result = HeapTupleGetDatum(tuple);
329 
330  PGR_DBG("Trying to free some memory\n");
331 
332  /* clean up (this is not really necessary) */
333  pfree(values);
334  pfree(nulls);
335 
336  SRF_RETURN_NEXT(funcctx, result);
337  } else {
338  /* do when there is no more left */
339  if (res) free(res);
340  SRF_RETURN_DONE(funcctx);
341  }
342 }
PGDLLEXPORT Datum alphashape(PG_FUNCTION_ARGS)
Definition: alpha.c:231
double y
Definition: alpha_driver.h:35
static int finish(int code, int ret)
Definition: alpha.c:64
#define PGR_DBG(...)
Definition: debug_macro.h:33
PG_FUNCTION_INFO_V1(alphashape)
static int fetch_vertices_columns(SPITupleTable *tuptable, vertex_columns_t *vertex_columns)
Definition: alpha.c:83
static void fetch_vertex(HeapTuple *tuple, TupleDesc *tupdesc, vertex_columns_t *vertex_columns, vertex_t *target_vertex)
Definition: alpha.c:109
double float8
Definition: dijkstra.h:47
#define TUPLIMIT
Definition: alpha.c:52
struct vertex_columns vertex_columns_t
char * err_msg
Definition: BDATester.cpp:50
static char * text2char(text *in)
Definition: alpha.c:55
static int compute_alpha_shape(char *sql, float8 alpha, vertex_t **res, size_t *res_count)
Definition: alpha.c:125
int alpha_shape(vertex_t *vertices, size_t count, double alpha, vertex_t **res, size_t *res_count, char **err_msg)
double x
Definition: alpha_driver.h:34