From 61320bee183402bdbaec93705b76606183ad7bd3 Mon Sep 17 00:00:00 2001 From: Franz Zotter Date: Sun, 26 Aug 2012 21:54:47 +0000 Subject: qhull algorithm works fine now svn path=/trunk/externals/iem/iemmatrix/; revision=16173 --- src/mtx_qhull/test.obj | 562 ++---------------------------- src/mtx_qhull/test_write_conv_hull_obj.pd | 45 ++- src/mtx_qhull/zhull.c | 252 ++++++++++---- 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; jinsideset),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%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; ipts,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; jneighbors); 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; jneighbors); 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;jneighbors);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)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; ineighbors, + 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;jneighbors, + 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; fifacets); fi++) { printf("facet %d<%d>: ",fi,getFacetByIndex(zh->facets,fi)); -- cgit v1.2.1