1/* $Id$ $Revision$ */
2/* vim:set shiftwidth=4 ts=8: */
3
4/*************************************************************************
5 * Copyright (c) 2011 AT&T Intellectual Property
6 * All rights reserved. This program and the accompanying materials
7 * are made available under the terms of the Eclipse Public License v1.0
8 * which accompanies this distribution, and is available at
9 * http://www.eclipse.org/legal/epl-v10.html
10 *
11 * Contributors: See CVS logs. Details at http://www.graphviz.org/
12 *************************************************************************/
13
14#include "config.h"
15
16#include "SparseMatrix.h"
17#include "logic.h"
18#include "memory.h"
19#include "delaunay.h"
20
21SparseMatrix call_tri(int n, int dim, real * x)
22{
23 real one = 1;
24 int i, ii, jj;
25 SparseMatrix A;
26 SparseMatrix B;
27 int* edgelist = NULL;
28 real* xv = N_GNEW(n, real);
29 real* yv = N_GNEW(n, real);
30 int numberofedges;
31
32 for (i = 0; i < n; i++) {
33 xv[i] = x[i * 2];
34 yv[i] = x[i * 2 + 1];
35 }
36
37 if (n > 2) {
38 edgelist = delaunay_tri (xv, yv, n, &numberofedges);
39 } else {
40 numberofedges = 0;
41 }
42
43 A = SparseMatrix_new(n, n, 1, MATRIX_TYPE_REAL, FORMAT_COORD);
44 for (i = 0; i < numberofedges; i++) {
45 ii = edgelist[i * 2];
46 jj = edgelist[i * 2 + 1];
47 SparseMatrix_coordinate_form_add_entries(A, 1, &(ii), &(jj), &one);
48 }
49 if (n == 2) { /* if two points, add edge i->j */
50 ii = 0;
51 jj = 1;
52 SparseMatrix_coordinate_form_add_entries(A, 1, &(ii), &(jj), &one);
53 }
54 for (i = 0; i < n; i++) {
55 SparseMatrix_coordinate_form_add_entries(A, 1, &i, &i, &one);
56 }
57 B = SparseMatrix_from_coordinate_format(A);
58 SparseMatrix_delete(A);
59 A = SparseMatrix_symmetrize(B, FALSE);
60 SparseMatrix_delete(B);
61 B = A;
62
63 free (edgelist);
64 free (xv);
65 free (yv);
66 return B;
67}
68
69SparseMatrix call_tri2(int n, int dim, real * xx)
70{
71 real *x, *y;
72 v_data *delaunay;
73 int i, j;
74 SparseMatrix A;
75 SparseMatrix B;
76 real one = 1;
77 x = N_GNEW(n, real);
78 y = N_GNEW(n, real);
79
80 for (i = 0; i < n; i++) {
81 x[i] = xx[dim * i];
82 y[i] = xx[dim * i + 1];
83 }
84
85 delaunay = UG_graph(x, y, n, 0);
86
87 A = SparseMatrix_new(n, n, 1, MATRIX_TYPE_REAL, FORMAT_COORD);
88
89 for (i = 0; i < n; i++) {
90 for (j = 1; j < delaunay[i].nedges; j++) {
91 SparseMatrix_coordinate_form_add_entries(A, 1, &i,
92 &(delaunay[i].
93 edges[j]), &one);
94 }
95 }
96 for (i = 0; i < n; i++) {
97 SparseMatrix_coordinate_form_add_entries(A, 1, &i, &i, &one);
98 }
99 B = SparseMatrix_from_coordinate_format(A);
100 B = SparseMatrix_symmetrize(B, FALSE);
101 SparseMatrix_delete(A);
102
103 free (x);
104 free (y);
105 freeGraph (delaunay);
106
107 return B;
108
109}
110
111