aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorFranz Zotter <fzotter@users.sourceforge.net>2012-08-26 21:54:47 +0000
committerFranz Zotter <fzotter@users.sourceforge.net>2012-08-26 21:54:47 +0000
commit61320bee183402bdbaec93705b76606183ad7bd3 (patch)
treea3d6abf2412a989ac289198cf525708d5e071d31
parent04be907cbba161af7eda231f8a6a1856fc3a6042 (diff)
qhull algorithm works fine now
svn path=/trunk/externals/iem/iemmatrix/; revision=16173
-rw-r--r--src/mtx_qhull/test.obj562
-rw-r--r--src/mtx_qhull/test_write_conv_hull_obj.pd45
-rw-r--r--src/mtx_qhull/zhull.c252
3 files changed, 228 insertions, 631 deletions
diff --git a/src/mtx_qhull/test.obj b/src/mtx_qhull/test.obj
index 27d5b09..366da0d 100644
--- a/src/mtx_qhull/test.obj
+++ b/src/mtx_qhull/test.obj
@@ -1,536 +1,26 @@
-v -1.29956 0.335546 0.669732
-v 0.335546 0.669732 -1.29956
-v 1.29956 -0.335546 0.669732
-v 0.669732 -1.29956 0.335546
-v -0.335546 0.669732 1.29956
-v 0.669732 1.29956 -0.335546
-v -0.335546 -0.669732 -1.29956
-v -0.669732 1.29956 0.335546
-v 0.335546 -0.669732 1.29956
-v -0.669732 -1.29956 -0.335546
-v -1.29956 -0.335546 -0.669732
-v 1.29956 0.335546 -0.669732
-v -1.21027 -0.692637 -0.552728
-v -0.692637 -0.552728 -1.21027
-v 1.21027 0.692637 -0.552728
-v -0.552728 -1.21027 -0.692637
-v 0.692637 -0.552728 1.21027
-v -0.552728 1.21027 0.692637
-v 0.692637 0.552728 -1.21027
-v 0.552728 1.21027 -0.692637
-v -0.692637 0.552728 1.21027
-v 0.552728 -1.21027 0.692637
-v -1.21027 0.692637 0.552728
-v 1.21027 -0.692637 0.552728
-v -0.202263 -0.060033 1.48509
-v -0.060033 1.48509 -0.202263
-v 0.202263 0.060033 1.48509
-v 1.48509 -0.202263 -0.060033
-v 0.060033 1.48509 0.202263
-v 1.48509 0.202263 0.060033
-v 0.060033 -1.48509 -0.202263
-v -1.48509 0.202263 -0.060033
-v -0.060033 -1.48509 0.202263
-v -1.48509 -0.202263 0.060033
-v -0.202263 0.060033 -1.48509
-v 0.202263 -0.060033 -1.48509
-v 0.074691 -0.419607 -1.43818
-v -0.419607 -1.43818 0.074691
-v -0.074691 0.419607 -1.43818
-v -1.43818 0.074691 -0.419607
-v 0.419607 -1.43818 -0.074691
-v -1.43818 -0.074691 0.419607
-v 0.419607 1.43818 0.074691
-v 1.43818 -0.074691 -0.419607
-v -0.419607 1.43818 -0.074691
-v 1.43818 0.074691 0.419607
-v 0.074691 0.419607 1.43818
-v -0.074691 -0.419607 1.43818
-v 0.308206 -0.289353 1.4392
-v -0.289353 1.4392 0.308206
-v -0.308206 0.289353 1.4392
-v 1.4392 0.308206 -0.289353
-v 0.289353 1.4392 -0.308206
-v 1.4392 -0.308206 0.289353
-v 0.289353 -1.4392 0.308206
-v -1.4392 -0.308206 -0.289353
-v -0.289353 -1.4392 -0.308206
-v -1.4392 0.308206 0.289353
-v 0.308206 0.289353 -1.4392
-v -0.308206 -0.289353 -1.4392
-v -0.418357 1.15801 -0.856735
-v 1.15801 -0.856735 -0.418357
-v 0.418357 -1.15801 -0.856735
-v -0.856735 -0.418357 1.15801
-v -1.15801 -0.856735 0.418357
-v -0.856735 0.418357 -1.15801
-v -1.15801 0.856735 -0.418357
-v 0.856735 0.418357 1.15801
-v 1.15801 0.856735 0.418357
-v 0.856735 -0.418357 -1.15801
-v -0.418357 -1.15801 0.856735
-v 0.418357 1.15801 0.856735
-v 1.36855 -0.589797 -0.170943
-v -0.589797 -0.170943 1.36855
-v -1.36855 0.589797 -0.170943
-v -0.170943 1.36855 -0.589797
-v 0.589797 -0.170943 -1.36855
-v -0.170943 -1.36855 0.589797
-v 0.589797 0.170943 1.36855
-v 0.170943 -1.36855 -0.589797
-v -0.589797 0.170943 -1.36855
-v 0.170943 1.36855 0.589797
-v 1.36855 0.589797 0.170943
-v -1.36855 -0.589797 0.170943
-v 1.27299 -0.019365 -0.793166
-v -0.019365 -0.793166 1.27299
-v -1.27299 0.019365 -0.793166
-v -0.793166 1.27299 -0.019365
-v 0.019365 -0.793166 -1.27299
-v -0.793166 -1.27299 0.019365
-v 0.019365 0.793166 1.27299
-v 0.793166 -1.27299 -0.019365
-v -0.019365 0.793166 -1.27299
-v 0.793166 1.27299 0.019365
-v 1.27299 0.019365 0.793166
-v -1.27299 -0.019365 0.793166
-v -1.04378 0.316747 1.02966
-v 0.316747 1.02966 -1.04378
-v 1.04378 -0.316747 1.02966
-v 1.02966 -1.04378 0.316747
-v -0.316747 1.02966 1.04378
-v 1.02966 1.04378 -0.316747
-v -0.316747 -1.02966 -1.04378
-v -1.02966 1.04378 0.316747
-v 0.316747 -1.02966 1.04378
-v -1.02966 -1.04378 -0.316747
-v -1.04378 -0.316747 -1.02966
-v 1.04378 0.316747 -1.02966
-v -0.392577 -0.872445 1.1553
-v -0.872445 1.1553 -0.392577
-v 0.392577 0.872445 1.1553
-v 1.1553 -0.392577 -0.872445
-v 0.872445 1.1553 0.392577
-v 1.1553 0.392577 0.872445
-v 0.872445 -1.1553 -0.392577
-v -1.1553 0.392577 -0.872445
-v -0.872445 -1.1553 0.392577
-v -1.1553 -0.392577 0.872445
-v -0.392577 0.872445 -1.1553
-v 0.392577 -0.872445 -1.1553
-v 0.759204 1.05149 0.753644
-v 1.05149 0.753644 0.759204
-v -0.759204 -1.05149 0.753644
-v 0.753644 0.759204 1.05149
-v -1.05149 0.753644 -0.759204
-v 0.753644 -0.759204 -1.05149
-v -1.05149 -0.753644 0.759204
-v -0.753644 -0.759204 1.05149
-v 1.05149 -0.753644 -0.759204
-v -0.753644 0.759204 -1.05149
-v 0.759204 -1.05149 -0.753644
-v -0.759204 1.05149 -0.753644
-v -0.661122 0.903363 0.998425
-v 0.903363 0.998425 -0.661122
-v 0.661122 -0.903363 0.998425
-v 0.998425 -0.661122 0.903363
-v -0.903363 0.998425 0.661122
-v 0.998425 0.661122 -0.903363
-v -0.903363 -0.998425 -0.661122
-v -0.998425 0.661122 0.903363
-v 0.903363 -0.998425 0.661122
-v -0.998425 -0.661122 -0.903363
-v -0.661122 -0.903363 -0.998425
-v 0.661122 0.903363 -0.998425
-v -1.33539 -0.440278 0.522396
-v -0.440278 0.522396 -1.33539
-v 1.33539 0.440278 0.522396
-v 0.522396 -1.33539 -0.440278
-v 0.440278 0.522396 1.33539
-v 0.522396 1.33539 0.440278
-v 0.440278 -0.522396 -1.33539
-v -0.522396 1.33539 -0.440278
-v -0.440278 -0.522396 1.33539
-v -0.522396 -1.33539 0.440278
-v -1.33539 0.440278 -0.522396
-v 1.33539 -0.440278 -0.522396
-v 0.992958 0.047085 1.12331
-v 0.047085 1.12331 0.992958
-v -0.992958 -0.047085 1.12331
-v 1.12331 0.992958 0.047085
-v -0.047085 1.12331 -0.992958
-v 1.12331 -0.992958 -0.047085
-v -0.047085 -1.12331 0.992958
-v -1.12331 -0.992958 0.047085
-v 0.047085 -1.12331 -0.992958
-v -1.12331 0.992958 -0.047085
-v 0.992958 -0.047085 -1.12331
-v -0.992958 0.047085 -1.12331
-v -0.188599 -1.31655 -0.69364
-v -1.31655 -0.69364 -0.188599
-v 0.188599 1.31655 -0.69364
-v -0.69364 -0.188599 -1.31655
-v 1.31655 -0.69364 0.188599
-v -0.69364 0.188599 1.31655
-v 1.31655 0.69364 -0.188599
-v 0.69364 0.188599 -1.31655
-v -1.31655 0.69364 0.188599
-v 0.69364 -0.188599 1.31655
-v -0.188599 1.31655 0.69364
-v 0.188599 -1.31655 0.69364
-f 71 78 163
-f 78 71 154
-f 57 38 10
-f 86 153 109
-f 163 86 109
-f 71 163 109
-f 57 10 16
-f 55 4 22
-f 4 141 22
-f 107 172 14
-f 55 78 33
-f 154 38 33
-f 78 154 33
-f 154 117 90
-f 38 154 90
-f 10 38 90
-f 154 71 123
-f 117 154 123
-f 78 55 180
-f 163 78 180
-f 55 22 180
-f 129 62 131
-f 126 129 131
-f 63 126 131
-f 143 14 7
-f 74 159 64
-f 153 74 64
-f 118 127 64
-f 159 118 64
-f 146 35 81
-f 53 20 171
-f 53 171 76
-f 53 76 26
-f 26 45 29
-f 5 47 91
-f 101 5 91
-f 158 101 91
-f 29 45 50
-f 57 16 169
-f 126 63 120
-f 151 126 120
-f 89 151 120
-f 89 7 37
-f 151 89 37
-f 162 62 73
-f 109 153 128
-f 71 109 128
-f 123 71 128
-f 127 123 128
-f 64 127 128
-f 153 64 128
-f 122 147 69
-f 150 94 43
-f 29 150 43
-f 26 29 43
-f 53 26 43
-f 86 9 48
-f 153 86 48
-f 93 146 119
-f 159 74 174
-f 101 18 133
-f 5 101 133
-f 21 5 133
-f 174 74 51
-f 21 174 51
-f 5 21 51
-f 47 5 51
-f 117 123 65
-f 123 127 65
-f 16 10 139
-f 143 16 139
-f 35 37 60
-f 81 35 60
-f 172 81 60
-f 14 172 60
-f 7 14 60
-f 37 7 60
-f 94 102 6
-f 43 94 6
-f 53 43 6
-f 20 53 6
-f 94 150 113
-f 27 79 149
-f 47 27 149
-f 91 47 149
-f 127 118 145
-f 65 127 145
-f 10 90 106
-f 139 10 106
-f 143 139 142
-f 14 143 142
-f 107 14 142
-f 122 69 121
-f 124 122 121
-f 72 124 121
-f 150 72 121
-f 113 150 121
-f 69 113 121
-f 172 107 168
-f 81 172 168
-f 119 146 130
-f 61 119 130
-f 61 130 132
-f 104 88 166
-f 177 104 166
-f 88 110 166
-f 110 132 67
-f 166 110 67
-f 86 163 105
-f 9 86 105
-f 180 22 105
-f 163 180 105
-f 118 159 96
-f 145 118 96
-f 62 129 156
-f 73 62 156
-f 17 136 99
-f 136 3 99
-f 9 17 49
-f 48 9 49
-f 27 48 49
-f 79 27 49
-f 76 171 161
-f 61 76 161
-f 119 61 161
-f 93 119 161
-f 72 150 82
-f 158 72 82
-f 29 50 82
-f 150 29 82
-f 57 169 80
-f 104 177 23
-f 90 117 164
-f 106 90 164
-f 170 106 164
-f 117 65 164
-f 147 30 83
-f 69 147 83
-f 65 145 84
-f 164 65 84
-f 170 164 84
-f 145 34 84
-f 146 81 66
-f 130 146 66
-f 168 116 66
-f 81 168 66
-f 107 142 11
-f 116 155 125
-f 66 116 125
-f 130 66 125
-f 132 130 125
-f 67 132 125
-f 155 67 125
-f 73 156 28
-f 79 49 178
-f 157 79 178
-f 99 157 178
-f 17 99 178
-f 49 17 178
-f 158 82 179
-f 101 158 179
-f 18 101 179
-f 50 18 179
-f 82 50 179
-f 63 131 148
-f 80 63 148
-f 83 30 52
-f 175 83 52
-f 104 23 137
-f 133 18 137
-f 84 34 56
-f 170 84 56
-f 11 142 13
-f 56 11 13
-f 170 56 13
-f 106 170 13
-f 139 106 13
-f 142 139 13
-f 156 85 44
-f 28 156 44
-f 30 28 44
-f 52 30 44
-f 62 162 115
-f 131 62 115
-f 148 131 115
-f 92 148 115
-f 162 92 115
-f 2 59 39
-f 93 2 39
-f 146 93 39
-f 35 146 39
-f 1 96 97
-f 174 21 97
-f 159 174 97
-f 96 159 97
-f 89 120 165
-f 80 169 165
-f 63 80 165
-f 120 63 165
-f 162 73 173
-f 122 124 68
-f 79 157 68
-f 149 79 68
-f 124 149 68
-f 17 9 135
-f 136 17 135
-f 141 136 135
-f 22 141 135
-f 105 22 135
-f 9 105 135
-f 57 80 31
-f 38 57 31
-f 33 38 31
-f 80 148 31
-f 168 107 87
-f 116 168 87
-f 155 116 87
-f 107 11 87
-f 23 1 140
-f 137 23 140
-f 133 137 140
-f 21 133 140
-f 97 21 140
-f 1 97 140
-f 73 28 54
-f 173 73 54
-f 155 32 75
-f 67 155 75
-f 166 67 75
-f 177 166 75
-f 96 1 42
-f 145 96 42
-f 34 145 42
-f 32 34 42
-f 2 144 19
-f 59 2 19
-f 144 138 19
-f 155 87 40
-f 32 155 40
-f 34 32 40
-f 56 34 40
-f 11 56 40
-f 87 11 40
-f 85 167 108
-f 19 138 108
-f 88 104 8
-f 45 88 8
-f 50 45 8
-f 18 50 8
-f 137 18 8
-f 104 137 8
-f 102 94 160
-f 175 102 160
-f 83 175 160
-f 69 83 160
-f 113 69 160
-f 94 113 160
-f 91 149 111
-f 158 91 111
-f 72 158 111
-f 124 72 111
-f 149 124 111
-f 2 93 98
-f 144 2 98
-f 20 144 98
-f 171 20 98
-f 161 171 98
-f 93 161 98
-f 175 52 15
-f 102 175 15
-f 147 122 114
-f 68 157 114
-f 122 68 114
-f 55 33 41
-f 4 55 41
-f 92 4 41
-f 148 92 41
-f 31 148 41
-f 33 31 41
-f 77 167 70
-f 151 77 70
-f 126 151 70
-f 129 126 70
-f 102 15 134
-f 6 102 134
-f 20 6 134
-f 144 20 134
-f 138 144 134
-f 15 138 134
-f 147 114 95
-f 99 3 95
-f 157 99 95
-f 114 157 95
-f 77 151 36
-f 59 77 36
-f 39 59 36
-f 35 39 36
-f 37 35 36
-f 151 37 36
-f 76 61 152
-f 26 76 152
-f 45 26 152
-f 88 45 152
-f 110 88 152
-f 132 110 152
-f 61 132 152
-f 162 173 100
-f 92 162 100
-f 4 92 100
-f 141 4 100
-f 77 59 176
-f 167 77 176
-f 108 167 176
-f 19 108 176
-f 59 19 176
-f 129 70 112
-f 156 129 112
-f 85 156 112
-f 167 85 112
-f 70 167 112
-f 141 100 24
-f 136 141 24
-f 3 136 24
-f 54 3 24
-f 173 54 24
-f 100 173 24
-f 7 89 103
-f 143 7 103
-f 16 143 103
-f 169 16 103
-f 165 169 103
-f 89 165 103
-f 108 138 12
-f 85 108 12
-f 44 85 12
-f 52 44 12
-f 15 52 12
-f 138 15 12
-f 74 153 25
-f 51 74 25
-f 47 51 25
-f 27 47 25
-f 48 27 25
-f 153 48 25
-f 147 95 46
-f 30 147 46
-f 28 30 46
-f 54 28 46
-f 3 54 46
-f 95 3 46
-f 1 23 58
-f 42 1 58
-f 32 42 58
-f 75 32 58
-f 177 75 58
-f 23 177 58
+v 1.5 0 0
+v 1.14907 0.964181 0
+v 0.260474 1.47721 0
+v -0.749998 1.29904 0
+v -1.40954 0.513033 0
+v -1.40954 -0.513027 0
+v -0.750004 -1.29904 0
+v 0.260467 -1.47721 0
+v 1.14906 -0.964187 0
+v 0 0 1.5
+f 2 1 9
+f 3 2 9
+f 4 3 9
+f 5 4 9
+f 6 5 9
+f 7 6 9
+f 8 7 9
+f 6 7 10
+f 5 6 10
+f 4 5 10
+f 3 4 10
+f 2 3 10
+f 1 2 10
+f 9 1 10
+f 8 9 10
+f 7 8 10
diff --git a/src/mtx_qhull/test_write_conv_hull_obj.pd b/src/mtx_qhull/test_write_conv_hull_obj.pd
index f73dff1..4efb87b 100644
--- a/src/mtx_qhull/test_write_conv_hull_obj.pd
+++ b/src/mtx_qhull/test_write_conv_hull_obj.pd
@@ -83,7 +83,7 @@
#X obj -9 358 color 0.9 0.9 0.9;
#X obj 335 426 mtx_* 1.5;
#X obj -10 338 ortho;
-#X obj 137 309 tgl 15 0 empty empty empty 17 7 0 10 -262144 -1 -1 0
+#X obj 137 309 tgl 15 0 empty empty empty 17 7 0 10 -262144 -1 -1 1
1;
#X obj 112 358 f;
#X obj 167 358 % 360;
@@ -116,13 +116,12 @@
#X msg 48 70 1.5 6;
#X msg 97 66 2 14;
#X msg 46 88 2.5 12;
-#X floatatom 396 171 5 0 0 0 - - -;
-#X obj 378 199 t b f;
+#X floatatom 323 249 5 0 0 0 - - -;
+#X obj 317 269 t b f;
#X obj -18 163 mtx_rand;
#X msg -7 141 200 3;
#X obj 237 319 mtx_qhull 500;
#X msg -123 202 read Rls.mtx \, bang;
-#X msg 68 150 matrix 4 3 0 0 0 1 0 0 0 1 0 1 1 0;
#X msg 100 85 2.5 20;
#X obj 107 239 mtx_size;
#X obj 42 235 t b a a;
@@ -177,8 +176,12 @@
#X connect 17 0 13 0;
#X connect 18 0 17 1;
#X connect 19 0 1 0;
-#X restore 251 176 pd makepolygon;
-#X msg 323 150 5;
+#X restore 376 163 pd makepolygon;
+#X obj 387 207 mtx_concat;
+#X msg 432 186 matrix 1 3 0 0 1;
+#X obj 386 184 t a b;
+#X msg 48 161 matrix 5 3 0 0 0 1 0 0 0 1 0 1 1 0 0.5 0.5 0;
+#X msg 322 136 9;
#X connect 1 0 2 0;
#X connect 2 0 1 0;
#X connect 3 0 4 0;
@@ -222,7 +225,7 @@
#X connect 35 0 37 0;
#X connect 36 0 37 0;
#X connect 37 0 38 0;
-#X connect 38 0 55 0;
+#X connect 38 0 54 0;
#X connect 39 0 50 0;
#X connect 39 1 32 0;
#X connect 40 0 41 0;
@@ -238,18 +241,22 @@
#X connect 48 0 38 0;
#X connect 49 0 48 0;
#X connect 50 0 27 0;
-#X connect 50 0 62 0;
+#X connect 50 0 61 0;
#X connect 51 0 38 0;
-#X connect 52 0 38 0;
-#X connect 53 0 37 0;
-#X connect 54 0 56 0;
-#X connect 55 0 10 0;
-#X connect 55 1 33 0;
-#X connect 55 2 54 0;
+#X connect 52 0 37 0;
+#X connect 53 0 55 0;
+#X connect 54 0 10 0;
+#X connect 54 1 33 0;
+#X connect 54 2 53 0;
+#X connect 55 0 56 0;
#X connect 56 0 57 0;
-#X connect 57 0 58 0;
-#X connect 60 0 61 0;
-#X connect 61 0 38 0;
-#X connect 61 0 59 0;
+#X connect 59 0 60 0;
+#X connect 60 0 38 0;
+#X connect 60 0 58 0;
+#X connect 62 0 65 0;
#X connect 63 0 38 0;
-#X connect 64 0 63 0;
+#X connect 64 0 63 1;
+#X connect 65 0 63 0;
+#X connect 65 1 64 0;
+#X connect 66 0 38 0;
+#X connect 67 0 62 0;
diff --git a/src/mtx_qhull/zhull.c b/src/mtx_qhull/zhull.c
index 5730160..1cd52f0 100644
--- a/src/mtx_qhull/zhull.c
+++ b/src/mtx_qhull/zhull.c
@@ -65,18 +65,23 @@ facet_t *getFacetByPointer(const entry_t ptr) {
}
void getHorizonEdgeByIndex(index_t *corners,
- const list_t horizon_fcts, const list_t horizon_fcts_edges,
- const index_t index) {
+ const list_t horizon_fcts, const list_t horizon_fcts_edges,
+ const list_t other_horizon_edges, const index_t index) {
index_t i=(index+getLength(horizon_fcts_edges))
%getLength(horizon_fcts_edges);
facet_t *f = getFacetByIndex(horizon_fcts,i);
index_t j=getEntry(horizon_fcts_edges,i);
- corners[0]=getEntry(f->corners, j);
- if (getLength(f->corners)>0)
- corners[1]=getEntry(f->corners, (j+1) % getLength(f->corners));
- else
- corners[1]=corners[0];
+ if (f==0) {
+ corners[0]=getEntry(horizon_fcts_edges,i);
+ corners[1]=getEntry(other_horizon_edges,i);
+ } else {
+ corners[0]=getEntry(f->corners, j);
+ if (getLength(f->corners)>0)
+ corners[1]=getEntry(f->corners, (j+1) % getLength(f->corners));
+ else
+ corners[1]=corners[0];
+ }
}
@@ -199,7 +204,8 @@ void dividePointsBetweenNewFacets (
if (getLength(point_inside_facet_list)>0) {
for (j=0; j<getLength(point_inside_facet_list); j++) {
f=getFacetByIndex(point_inside_facet_list,j);
- appendToList(&(f->insideset),getEntry(assoc,i));
+ if (notInList(getEntry(assoc,i),f->insideset))
+ appendToList(&(f->insideset),getEntry(assoc,i));
}
appendListToList(&(zh->facets_with_insidepoints),point_inside_facet_list);
uniquefyListEntries(&(zh->facets_with_insidepoints));
@@ -262,13 +268,20 @@ void zhullInitialFacets(zhull_t *zh) {
}
void printHorizonEdges(list_t *horizon_fcts,
- list_t *horizon_fcts_edges) {
+ list_t *horizon_fcts_edges,
+ list_t *other_horizon_edges) {
index_t i;
index_t c1[2];
+ list_t list_for_printing=emptyList();
- printf("horizon edges: ");
+ printf("horizon : ");
+ printList(*horizon_fcts);
+ printList(*horizon_fcts_edges);
+ printList(*other_horizon_edges);
+ printf("\n horizon edges: ");
for (i=0; i<getLength(*horizon_fcts_edges); i++) {
- getHorizonEdgeByIndex(c1, *horizon_fcts, *horizon_fcts_edges, i);
+ getHorizonEdgeByIndex(c1, *horizon_fcts, *horizon_fcts_edges,
+ *other_horizon_edges, i);
printf(", %d->%d",c1[0],c1[1]);
}
printf("\n");
@@ -276,7 +289,8 @@ void printHorizonEdges(list_t *horizon_fcts,
void sortHorizonEdges(list_t *horizon_fcts,
- list_t *horizon_fcts_edges) {
+ list_t *horizon_fcts_edges,
+ list_t *other_horizon_edges) {
index_t i,j;
facet_t *fi;
index_t ei;
@@ -286,20 +300,44 @@ void sortHorizonEdges(list_t *horizon_fcts,
if (getLength(*horizon_fcts_edges)==0)
return;
for (i=0; i<getLength(*horizon_fcts_edges)-1; i++) {
- getHorizonEdgeByIndex(c1, *horizon_fcts, *horizon_fcts_edges, i);
+ getHorizonEdgeByIndex(c1, *horizon_fcts, *horizon_fcts_edges,
+ *other_horizon_edges, i);
for (j=i+1; j<getLength(*horizon_fcts_edges); j++) {
- getHorizonEdgeByIndex(c2, *horizon_fcts, *horizon_fcts_edges, j);
- if (c1[1]==c2[0]) { //found edge continuation: swap positions
+ getHorizonEdgeByIndex(c2, *horizon_fcts, *horizon_fcts_edges,
+ *other_horizon_edges, j);
+ if ((c1[1]==c2[0])&&(c1[0]!=c2[1])) {
+ //found edge continuation w/o u-turn: swap positions
ei=getEntry(*horizon_fcts,j);
setEntry(*horizon_fcts,j,getEntry(*horizon_fcts,i+1));
setEntry(*horizon_fcts,i+1,ei);
ei=getEntry(*horizon_fcts_edges,j);
setEntry(*horizon_fcts_edges,j,getEntry(*horizon_fcts_edges,i+1));
setEntry(*horizon_fcts_edges,i+1,ei);
+ ei=getEntry(*other_horizon_edges,j);
+ setEntry(*other_horizon_edges,j,getEntry(*other_horizon_edges,i+1));
+ setEntry(*other_horizon_edges,i+1,ei);
break;
}
- // HIER MUSS MEHR LOGIK HINEIN: HORIZONT KANN
- // FEHLER BEINHALTEN
+ }
+ if (j==getLength(*horizon_fcts_edges)) {
+ // edge continuation requires u-turn
+ for (j=i+1; j<getLength(*horizon_fcts_edges); j++) {
+ getHorizonEdgeByIndex(c2, *horizon_fcts, *horizon_fcts_edges,
+ *other_horizon_edges, j);
+ if (c1[1]==c2[0]) {
+ //found edge continuation w/o return: swap positions
+ ei=getEntry(*horizon_fcts,j);
+ setEntry(*horizon_fcts,j,getEntry(*horizon_fcts,i+1));
+ setEntry(*horizon_fcts,i+1,ei);
+ ei=getEntry(*horizon_fcts_edges,j);
+ setEntry(*horizon_fcts_edges,j,getEntry(*horizon_fcts_edges,i+1));
+ setEntry(*horizon_fcts_edges,i+1,ei);
+ ei=getEntry(*other_horizon_edges,j);
+ setEntry(*other_horizon_edges,j,getEntry(*other_horizon_edges,i+1));
+ setEntry(*other_horizon_edges,i+1,ei);
+ break;
+ }
+ }
}
}
}
@@ -309,84 +347,126 @@ void removeVisibleFacetsGetHorizonAndAvailablePoints(
facet_t *f,
list_t *horizon_fcts,
list_t *horizon_fcts_edges,
+ list_t *other_horizon_edges,
list_t *avail_points) {
- index_t i,j,k;
+ index_t j,k;
facet_t *n;
float d;
list_t visible_fcts = emptyList();
list_t fcts_to_visit = emptyList();
list_t fcts_visited = emptyList();
+// list_t list_for_printing = emptyList();
*avail_points = emptyList();
*horizon_fcts = emptyList();
*horizon_fcts_edges = emptyList();
+ *other_horizon_edges = emptyList();
- i=0;
+ d=distancePointPlane(getPoint(zh->pts,point_index),f->plane);
+// printf("distance %5.2f\n",d);
appendToList(&fcts_to_visit,(entry_t)f);
- if (getLength(fcts_to_visit)==0)
- return;
- do {
- f=getFacetByIndex(fcts_to_visit,0);
- d=distancePointPlane(getPoint(zh->pts,point_index),f->plane);
- if (d>=TOL_OUTSIDEPOINT) { // visible facet
+ if (d>=TOL_OUTSIDEPOINT) {
+ while (getLength(fcts_to_visit)>0) {
+ // visiting only visible facets
+ // horizon: edges to invisible or coincident neighbors
+ f=getFacetByIndex(fcts_to_visit,0);
appendToList(&visible_fcts,(entry_t)f);
appendListToList(avail_points, f->outsideset);
for (j=0; j<getLength(f->neighbors); j++) {
n=getFacetByIndex(f->neighbors,j);
d=distancePointPlane(getPoint(zh->pts,point_index),n->plane);
- if (d>=TOL_INSIDEPOINT)
+ if (d>=TOL_OUTSIDEPOINT) { // visit visible neighbors
appendToList(&fcts_to_visit,(entry_t)n);
- else {
- // invisible neighbor: horizon edge found
+ }
+ else { // horizon: coincident or invisible neighbors
k=getEntry(f->corners,(j+1)%getLength(f->corners));
k=findValueInList(k,n->corners);
appendToList(horizon_fcts,(entry_t)n);
appendToList(horizon_fcts_edges,k);
- }
+ appendToList(other_horizon_edges,getNumPoints(zh->pts));
+ }
}
- }
- else if (d>=TOL_INSIDEPOINT) { // coincident facet
- for (j=0; j<getLength(f->neighbors); j++) {
- // is point outside polygon? searching edges.
- d=distancePointLineOnPlane(getPoint(zh->pts,point_index),
- getLine(zh,f,j),f->plane);
- if (d>=TOL_OUTSIDEPOINT) { // point outside edge: register horizon edge
- appendToList(horizon_fcts,(entry_t)f);
- appendToList(horizon_fcts_edges,j);
- // exceptional: initial facet with opposing normal
- if (innerProduct(f->plane.normal, getFacetByIndex(f->neighbors,j)->plane.normal)<
- -1.0f+TOL_OUTSIDEPOINT)
- appendToList(&fcts_to_visit,(entry_t)
- getFacetByIndex(f->neighbors,j));
- } // otherwise point is discared
+ removeValueFromList(&fcts_to_visit,(entry_t)f);
+ appendToList(&fcts_visited,(entry_t)f);
+ removeValueListFromList(&fcts_to_visit,fcts_visited);
+ }
+// printf("removing facets\n");
+// list_for_printing=findValueListInList(visible_fcts,zh->facets);
+// printList(list_for_printing);
+// freeList(&list_for_printing);
+ removeFacetByPointerList(zh,visible_fcts);
+ freeList(&visible_fcts);
+ freeList(&fcts_to_visit);
+ freeList(&fcts_visited);
+ sortHorizonEdges(horizon_fcts, horizon_fcts_edges, other_horizon_edges);
+// printHorizonEdges(horizon_fcts,horizon_fcts_edges,other_horizon_edges);
+ }
+ else if (d>=TOL_INSIDEPOINT) {
+ // all coincident surfaces shall be removed
+ // horizon might not be defined by facets
+ while (getLength(fcts_to_visit)>0) {
+ f=getFacetByIndex(fcts_to_visit,0);
+ appendToList(&visible_fcts,(entry_t)f);
+ appendListToList(avail_points, f->outsideset);
+ appendListToList(avail_points, f->insideset);
+ for (j=0;j<getLength(f->neighbors);j++) {
+ n=getFacetByIndex(f->neighbors,j);
+ d=distancePointPlane(getPoint(zh->pts,point_index),n->plane);
+ if (d>=TOL_INSIDEPOINT) { // coincident facet
+ if (notInList((entry_t)n,visible_fcts))
+ appendToList(&fcts_to_visit,(entry_t)n);
+ if ((innerProduct(f->plane.normal,n->plane.normal)<
+ -1.0f+TOL_DEGENERATE)&&
+ (distancePointLineOnPlane(getPoint(zh->pts,point_index),
+ getLine(zh,f,j),
+ f->plane)<TOL_INSIDEPOINT)) {
+ // coincident facets with opposite surface orientation
+ // yield an edge to keep despite all facets will be removed
+ // as soon as edge is invisible to point
+ appendToList(horizon_fcts,0);
+ appendToList(other_horizon_edges,
+ getEntry(f->corners,j));
+ appendToList(horizon_fcts_edges,
+ getEntry(f->corners,(j+1)%getLength(f->corners)));
+ }
+ }
+ else { // invisible facet forms horizon that persists
+ k=getEntry(f->corners,(j+1)%getLength(f->corners));
+ k=findValueInList(k,n->corners);
+ appendToList(horizon_fcts,(entry_t)n);
+ appendToList(horizon_fcts_edges,k);
+ appendToList(other_horizon_edges,getNumPoints(zh->pts));
+ }
}
+ removeValueFromList(&fcts_to_visit,(entry_t)f);
+ appendToList(&fcts_visited,(entry_t)f);
+ removeValueListFromList(&fcts_to_visit,fcts_visited);
}
- appendToList(&fcts_visited,(entry_t)f);
- removeValueListFromList(&fcts_to_visit,fcts_visited);
- } while (getLength(fcts_to_visit)>0);
-
-// printf("removing facets");
-// indices_for_printing=findValueListInList(visible_fcts, zh->facets);
-// printList(indices_for_printing);
-// freeList(&indices_for_printing);
- removeFacetByPointerList(zh,visible_fcts);
- freeList(&visible_fcts);
- freeList(&fcts_to_visit);
- sortHorizonEdges(horizon_fcts, horizon_fcts_edges);
-// printHorizonEdges(horizon_fcts, horizon_fcts_edges);
+// printf("removing facets\n");
+// list_for_printing=findValueListInList(visible_fcts,zh->facets);
+// printList(list_for_printing);
+// freeList(&list_for_printing);
+ removeFacetByPointerList(zh,visible_fcts);
+ sortHorizonEdges(horizon_fcts, horizon_fcts_edges,other_horizon_edges);
+// printHorizonEdges(horizon_fcts,horizon_fcts_edges,other_horizon_edges);
+ freeList(&visible_fcts);
+ freeList(&fcts_to_visit);
+ freeList(&fcts_visited);
+ }
}
void initNewFacets(zhull_t *zh, index_t point_index,
list_t new_facets, list_t horizon_fcts,
- list_t horizon_fcts_edges) {
+ list_t horizon_fcts_edges, list_t other_horizon_edges) {
index_t i,j;
entry_t array[3];
array[0]=point_index;
for (i=0; i<getLength(new_facets); i++) {
// corners
- getHorizonEdgeByIndex(array,horizon_fcts, horizon_fcts_edges,i);
+ getHorizonEdgeByIndex(array,horizon_fcts, horizon_fcts_edges,
+ other_horizon_edges,i);
array[2]=array[1];
array[1]=array[0];
array[0]=array[2];
@@ -401,19 +481,35 @@ void initNewFacets(zhull_t *zh, index_t point_index,
j=(i+1) % getLength(horizon_fcts);
array[2]=getEntry(new_facets,j);
// old neighbor
- array[0]=getEntry(horizon_fcts,i);
+ if (getEntry(horizon_fcts,i)!=0) {
+ array[0]=getEntry(horizon_fcts,i);
+ setEntry(getFacetByIndex(horizon_fcts,i)->neighbors,
+ getEntry(horizon_fcts_edges,i), getEntry(new_facets,i));
+ }
+ else {
+ // registring at new neighbor where there
+ // is no old one: degenerate 2D case
+ for (j=0;j<getLength(horizon_fcts_edges);j++) {
+ if ((getEntry(horizon_fcts_edges,i)==getEntry(other_horizon_edges,j))&&
+ (getEntry(horizon_fcts_edges,j)==getEntry(other_horizon_edges,i)))
+ break;
+ }
+ array[0]=getEntry(new_facets,j);
+ setEntry(getFacetByIndex(new_facets,j)->neighbors,
+ 0, getEntry(new_facets,i));
+ }
+
getFacetByIndex(new_facets,i)->neighbors=
initList(array,3);
- removeValueFromList(&(getFacetByIndex(horizon_fcts,i)->insideset),point_index);
- if (getLength(getFacetByIndex(horizon_fcts,i)->insideset)==0) {
- removeValueFromList(&(zh->facets_with_insidepoints),(entry_t)getFacetByIndex(horizon_fcts,i));
+ // removing inside points at (potential) horizon facet if point index is one
+ if (getFacetByIndex(horizon_fcts,i)!=0) {
+ removeValueFromList(&(getFacetByIndex(horizon_fcts,i)->insideset),point_index);
+ if (getLength(getFacetByIndex(horizon_fcts,i)->insideset)==0) {
+ removeValueFromList(&(zh->facets_with_insidepoints),(entry_t)getFacetByIndex(horizon_fcts,i));
+ }
}
- // registering at old neighbor:
- setEntry(getFacetByIndex(horizon_fcts,i)->neighbors,
- getEntry(horizon_fcts_edges,i), getEntry(new_facets,i));
-
// initializing normal vectors and lists
getFacetByIndex(new_facets,i)->plane =
planeFromListedPoints(zh->pts,
@@ -426,14 +522,14 @@ void initNewFacets(zhull_t *zh, index_t point_index,
void makePyramidFacetsToHorizon(zhull_t *zh, index_t point_index,
list_t horizon_fcts, list_t horizon_fcts_edges,
- list_t avail_points) {
+ list_t other_horizon_edges, list_t avail_points) {
list_t new_facets = appendNewFacets(zh, getLength(horizon_fcts_edges));
// printf("making new pyramid of %d facets\n",getLength(horizon_fcts_edges));
- initNewFacets(zh,point_index,new_facets,horizon_fcts,horizon_fcts_edges);
- // printf("available points: ");
- // printList(avail_points);
- // printf("new facets : ");
- // printList(new_facets);
+ initNewFacets(zh,point_index,new_facets,horizon_fcts,horizon_fcts_edges,other_horizon_edges);
+/* printf("available points: ");
+ printList(avail_points);
+ printf("new facets : ");
+ printList(new_facets);*/
dividePointsBetweenNewFacets(zh, avail_points, new_facets);
freeList(&new_facets);
}
@@ -446,6 +542,7 @@ void calculateZHull(zhull_t *zh,int maxit) {
int cnt=0;
list_t horizon_fcts=emptyList();
list_t horizon_fcts_edges=emptyList();
+ list_t other_horizon_edges=emptyList();
list_t available_points=emptyList();
if (maxit>MAXIT)
maxit=MAXIT;
@@ -468,15 +565,17 @@ void calculateZHull(zhull_t *zh,int maxit) {
f=getFacetByIndex(zh->facets_with_outsidepoints,fli);
pi=f->farthest_outside_point;
}
+// printf("point %d\n",pi);
removeVisibleFacetsGetHorizonAndAvailablePoints(zh,pi,f,
- &horizon_fcts, &horizon_fcts_edges,
+ &horizon_fcts, &horizon_fcts_edges,&other_horizon_edges,
&available_points);
removeValueFromList(&available_points, pi);
makePyramidFacetsToHorizon(zh,pi,horizon_fcts,horizon_fcts_edges,
- available_points);
+ other_horizon_edges,available_points);
// printZhull(zh);
freeList(&horizon_fcts);
freeList(&horizon_fcts_edges);
+ freeList(&other_horizon_edges);
freeList(&available_points);
fli++;
}
@@ -486,7 +585,7 @@ void calculateZHull(zhull_t *zh,int maxit) {
void printZhull(const zhull_t * const zh) {
index_t fi;
list_t indices = emptyList();
- printf("zhull from %d points\n", getNumPoints(zh->pts));
+/* printf("zhull from %d points\n", getNumPoints(zh->pts));
printf("facets with outsidepoints: ");
indices=findValueListInList(zh->facets_with_outsidepoints,zh->facets);
printList(indices);
@@ -495,6 +594,7 @@ void printZhull(const zhull_t * const zh) {
indices=findValueListInList(zh->facets_with_insidepoints,zh->facets);
printList(indices);
freeList(&indices);
+ */
printf("zhull has %d facets\n", getLength(zh->facets));
for (fi=0; fi<getLength(zh->facets); fi++) {
printf("facet %d<%d>: ",fi,getFacetByIndex(zh->facets,fi));