Got Questions? Get Answers.
Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
concave hull/polygon

Subject: concave hull/polygon

From: sayyad

Date: 21 Jul, 2009 06:24:01

Message: 1 of 9

hi,
i have set of 3d/2d points and I want to fit them inside concave polygon.There exists convex hull routine. Is there any routine available in matlab for concave polygon or non convex hull. I have read about fmincon for concave polygon but couldn't follow how it works.
thanx in adavance
regards,
shahzad

Subject: concave hull/polygon

From: ImageAnalyst

Date: 21 Jul, 2009 13:01:41

Message: 2 of 9

On Jul 21, 2:24 am, "sayyad " <shahb...@gmx.de> wrote:
> hi,
> i have set of 3d/2d points and I want to fit them inside  concave polygon.There exists convex hull routine. Is there any routine available in matlab for concave polygon  or non convex hull. I have read about fmincon for concave polygon but couldn't follow how it works.
> thanx in adavance
> regards,
> shahzad

--------------------------------------
Can you provide an example image to show what you mean by concave
polygon?
Maybe alpha shapes, balloons, snakes, etc. might work.

Subject: concave hull/polygon

From: sayyad

Date: 21 Jul, 2009 15:25:04

Message: 3 of 9

Algorithm that I need is exactly available at
http://get.dsi.uminho.pt/local/
Concave Hull algorithm version 0.9.1, 21.02.2008. ----------------------------------------
But as its in Java applet and I donot have idea how to integrate it in my matlab application/ to translate code in mat file.
regards,
shahzad

Subject: concave hull/polygon

From: sayyad

Date: 21 Jul, 2009 15:30:20

Message: 4 of 9

Algorithm that I need is exactly available at
http://get.dsi.uminho.pt/local/
Concave Hull algorithm version 0.9.1, 21.02.2008. ----------------------------------------
But as its in Java applet and I donot have idea how to integrate it in my matlab application/ to translate code in mat file.
regards,
shahzad

Subject: concave hull/polygon

From: John D'Errico

Date: 21 Jul, 2009 16:03:02

Message: 5 of 9

"sayyad " <shahbaba@gmx.de> wrote in message <h44muc$ilp$1@fred.mathworks.com>...
> Algorithm that I need is exactly available at
> http://get.dsi.uminho.pt/local/
> Concave Hull algorithm version 0.9.1, 21.02.2008. ----------------------------------------
> But as its in Java applet and I donot have idea how to integrate it in my matlab application/ to translate code in mat file.
> regards,
> shahzad

So then you will need to write it yourself.

Or use an alpha shape, which will solve the
same problems nicely.

John

Subject: concave hull/polygon

From: Luigi Giaccari

Date: 21 Jul, 2009 17:43:03

Message: 6 of 9

"sayyad " <shahbaba@gmx.de> wrote in message <h43mu1$2ku$1@fred.mathworks.com>...
> hi,
> i have set of 3d/2d points and I want to fit them inside concave polygon.There exists convex hull routine. Is there any routine available in matlab for concave polygon or non convex hull. I have read about fmincon for concave polygon but couldn't follow how it works.
> thanx in adavance
> regards,
> shahzad

Today is your lucky day.

Here is the solution:

2D : FInd delaunay edges, discover how on the Maltab help from r2009a

Follow this:

     doc
         demos
                  Mathematics
                                     Creating and editing delaunay triangulation
                                          Example 7(Example Seven: Curve Reconstruction from a Point Cloud)


3D you need a surface recostructor:

http://www.mathworks.com/matlabcentral/fileexchange/22185

http://www.mathworks.com/matlabcentral/fileexchange/22595

http://www.mathworks.com/matlabcentral/fileexchange/23447

http://www.mathworks.com/matlabcentral/fileexchange/24619


Apha shapes maybe good but sometimes they are not flexible enough beacuse the alpha parameter is fixed. A surface recostructor instead it is like an aplha shape with adaptive alpha parameter, more flexible an generally better.

http://giaccariluigi.altervista.org/blog/

Subject: concave hull/polygon

From: Alex James

Date: 6 Oct, 2010 10:08:04

Message: 7 of 9

> Today is your lucky day.
>
> Here is the solution:
>
> 2D : FInd delaunay edges, discover how on the Maltab help from r2009a
>
> Follow this:
>
> doc
> demos
> Mathematics
> Creating and editing delaunay triangulation
> Example 7(Example Seven: Curve Reconstruction from a Point Cloud)

Not sure if it's that it's raining in CA or that I'm still up at 3am, but I don't think today is my lucky day as you say.

When I plot the delaunay triangulation returned by matlab for my concave dataset (sort of a crescent), some of the triangles connect across the ends of the crescent in the concave region contrary to the desired result of the triangles following the edge of the crescent... matlab version, dataset, and test code below. Is this the desired functionality, or a bug?

version =
7.4.0.336 (R2007a)
rzdat =
    2.1843 -0.1313
    2.0384 -0.5620
    1.2944 -0.6484
    1.0573 -0.0562
    1.3544 0.5160
    2.1315 0.1851
    1.4951 -0.7340
    1.0928 -0.1790
    1.3364 0.4571
    2.1333 0.1181
    1.4294 -0.6628
    1.1202 -0.0144
    1.5909 0.5336
    1.9559 -0.6192
    1.2303 -0.5219
    1.1285 0.1470
    1.6749 0.5707
    1.9293 -0.6848
    1.2346 -0.5816
    1.0678 0.0306
    1.4411 0.5650
    2.1857 -0.0945
    1.4205 -0.7170
    1.0761 -0.1457
    1.3265 0.4689
    2.1108 0.2044
    1.4757 -0.7013
    1.1056 -0.0998
    1.4641 0.5108
    2.1074 -0.3487
    1.3072 -0.5870
    1.1256 0.0873
    1.6575 0.5536
    1.9143 -0.6796
    1.2201 -0.5389
    1.0970 0.1015
    1.5601 0.5861
    2.0859 -0.4738
    1.3224 -0.6681
    1.0602 -0.0792
    1.3442 0.5034
    2.1215 0.2032
    1.4959 -0.7288
    1.0955 -0.1666
    1.3587 0.4684
    2.1528 0.0281
    1.4009 -0.6457
    1.1234 0.0155
    1.6221 0.5373
    1.9231 -0.6550
    1.2174 -0.5108
    1.1270 0.1541
    1.6697 0.5758
    1.9439 -0.6757
    1.2435 -0.5972
    1.0615 0.0076
    1.4097 0.5530
    2.1804 0.0149
    1.4498 -0.7269
    1.0817 -0.1634
    1.3232 0.4600
    2.1101 0.1990
    1.4678 -0.6923
    1.1096 -0.0783
    1.4992 0.5196
    2.0670 -0.4470
    1.2826 -0.5682
    1.1263 0.1059
    1.6636 0.5586
    1.9177 -0.6821
    1.2237 -0.5511
    1.2237 -0.5511
    1.0877 0.0811
    1.5240 0.5830
    2.1266 -0.3739
    1.3498 -0.6842
    1.0641 -0.0991
    1.3380 0.4929
    2.1169 0.2074
    1.4915 -0.7217
    1.0980 -0.1491
    1.3860 0.4818
    2.1601 -0.0767
    1.3724 -0.6291
    1.1248 0.0394
    1.6391 0.5415
    1.9108 -0.6699
    1.2137 -0.5121
    1.1209 0.1472
    1.6479 0.5814
    1.9757 -0.6453
    1.2606 -0.6181
    1.0574 -0.0197
    1.3808 0.5373
    2.1592 0.1106
    1.4761 -0.7334
    1.0873 -0.1771
    1.3233 0.4540
    2.1140 0.1823
    1.4562 -0.6816
    1.1141 -0.0535
    1.5380 0.5267
    2.0195 -0.5336
    1.2584 -0.5478
    1.1273 0.1248
    1.6693 0.5640
    1.9220 -0.6841
    1.2280 -0.5642
    1.0785 0.0593
    1.4870 0.5769
    2.1620 -0.2547
    1.3799 -0.6995
    1.0690 -0.1193
    1.3329 0.4825
    2.1141 0.2062
    1.4847 -0.7129
    1.1009 -0.1278
    1.4191 0.4957
    2.1480 -0.1976
    1.3428 -0.6113
    1.1251 0.0611
    1.6484 0.5467
    1.9105 -0.6755
    1.2156 -0.5227
    1.1106 0.1288
    1.6106 0.5857
    2.0242 -0.5837
    1.2866 -0.6422
    1.0568 -0.0488
    1.3586 0.5202
    2.1360 0.1751
    1.4930 -0.7348
    1.0919 -0.1807
    1.3318 0.4550
    2.1276 0.1379
    1.4367 -0.6674
    1.1189 -0.0234
    1.5799 0.5323
    1.9687 -0.6041
    1.2356 -0.5269
    1.1284 0.1429
    1.6744 0.5693
    1.9272 -0.6853
    1.2329 -0.5778
    1.0700 0.0368
    1.4506 0.5679
    2.1836 -0.1281
    1.4118 -0.7135
    1.0746 -0.1402
    1.3278 0.4718
    2.1115 0.2048
    1.4776 -0.7038
    1.1046 -0.1058
    1.4544 0.5080
    2.1177 -0.3182
    1.3144 -0.5923
    1.1254 0.0818
    1.6556 0.5522
    1.9135 -0.6787
    1.2192 -0.5355
    1.0997 0.1072
    1.5705 0.5864
    2.0736 -0.4992
    1.3149 -0.6631
    1.0593 -0.0733
    1.3465 0.5066
    2.1236 0.2000
    1.4963 -0.7305
    1.0948 -0.1706
    1.3520 0.4651
    2.1483 0.0545
    1.4087 -0.6503
    1.1228 0.0080
    1.6151 0.5365
    1.9299 -0.6479
    1.2200 -0.5126
    1.1278 0.1535
    1.6725 0.5744
    1.9386 -0.6797
    1.2404 -0.5926
    1.0630 0.0141
    1.4179 0.5565
    2.1837 -0.0133
    1.4421 -0.7245
    1.0802 -0.1590
    1.3238 0.4622
    2.1099 0.2013
    1.4702 -0.6948
    1.1085 -0.0843
    1.4895 0.5174
    2.0786 -0.4217
    1.2891 -0.5733
    1.1261 0.1009
    1.6620 0.5572
    1.9167 -0.6815
    1.2227 -0.5477
    1.0902 0.0868
    1.5338 0.5842
    2.1159 -0.4028
    1.3422 -0.6800
    1.0630 -0.0937
    1.3395 0.4957
    2.1178 0.2071
    1.4931 -0.7238
    1.0973 -0.1543
    1.3780 0.4780
    2.1597 -0.0465
    1.3802 -0.6337
    1.1246 0.0332
    1.6355 0.5402
    1.9126 -0.6672
    1.2140 -0.5106
    1.1231 0.1505
    1.6557 0.5798
    1.9650 -0.6565
    1.2549 -0.6118
    1.0582 -0.0117
    1.3884 0.5419
    2.1660 0.0862
    1.4694 -0.7320
    1.0858 -0.1739
    1.3228 0.4553
    2.1123 0.1885
    1.4599 -0.6848
    1.1128 -0.0607
    1.5269 0.5251
    2.0331 -0.5112
    1.2650 -0.5536
    1.1269 0.1195
    1.6677 0.5625
    1.9209 -0.6834
    1.2269 -0.5607
    1.0810 0.0653
    1.4970 0.5789
    2.1533 -0.2884
    1.3715 -0.6955
    1.0676 -0.1137
    1.3343 0.4854
    2.1149 0.2065
    1.4866 -0.7153
    1.1001 -0.1337
    1.4098 0.4921
    2.1533 -0.1644
    1.3507 -0.6162
    1.1251 0.0554
    1.6463 0.5452
    1.9100 -0.6744
    1.2148 -0.5194
    1.1135 0.1343
    1.6213 0.5848
    2.0106 -0.6029
    1.2792 -0.6359
    1.0566 -0.0414
    1.3634 0.5245
    2.1413 0.1624
    1.4900 -0.7351
    1.0908 -0.1812
    1.3283 0.4538
    2.1228 0.1537
    1.4429 -0.6716
    1.1177 -0.0319
    1.5688 0.5310
    1.9818 -0.5876
    1.2413 -0.5322
    1.1281 0.1385
    1.6733 0.5679
    1.9255 -0.6853
    1.2315 -0.5741
    1.0721 0.0428
    1.4600 0.5706
    2.1799 -0.1612
    1.4033 -0.7100
    1.0731 -0.1347
    1.3292 0.4746
    2.1122 0.2051
    1.4794 -0.7062
    1.1035 -0.1115
    1.4450 0.5050
    2.1270 -0.2874
    1.3217 -0.5974
    1.1253 0.0764
    1.6537 0.5508
    1.9128 -0.6779
    1.2182 -0.5322
    1.1025 0.1129
    1.5808 0.5865
    2.0611 -0.5230
    1.3074 -0.6580
    1.0585 -0.0673
    1.3490 0.5099
    2.1260 0.1959
    1.4963 -0.7319
    1.0941 -0.1741
    1.3459 0.4619
    2.1432 0.0791
    1.4164 -0.6549
    1.1219 0.0001
    1.6072 0.5355
    1.9380 -0.6391
    1.2231 -0.5153
    1.1283 0.1519
    1.6741 0.5730
    1.9345 -0.6824
    1.2380 -0.5884
    1.0646 0.0202
    1.4261 0.5598
    2.1856 -0.0418
    1.4346 -0.7219
    1.0788 -0.1544
    1.3246 0.4645
    2.1100 0.2028
    1.4723 -0.6972
    1.1074 -0.0900
    1.4803 0.5151
    2.0894 -0.3963
    1.2955 -0.5783
    1.1259 0.0961
    1.6604 0.5560
    1.9158 -0.6809
    1.2217 -0.5445
    1.0926 0.0921
    1.5432 0.5851
    2.1054 -0.4294
    1.3351 -0.6758
    1.0619 -0.0886
    1.3410 0.4984
    2.1189 0.2062
    1.4943 -0.7257
    1.0967 -0.1590
    1.3708 0.4744
    2.1581 -0.0186
    1.3877 -0.6380
    1.1243 0.0271
    1.6313 0.5392
    1.9153 -0.6637
    1.2148 -0.5100
    1.1248 0.1526
    1.6618 0.5784
    1.9561 -0.6650
    1.2502 -0.6061
    1.0593 -0.0044
    1.3960 0.5461
    2.1721 0.0612
    1.4625 -0.7303
    1.0843 -0.1703
    1.3227 0.4568
    2.1112 0.1930
    1.4631 -0.6876
    1.1116 -0.0673
    1.5166 0.5231
    2.0459 -0.4886
    1.2714 -0.5590
    1.1267 0.1145
    1.6662 0.5611
    1.9198 -0.6829
    1.2257 -0.5572
    1.0834 0.0710
    1.5068 0.5805
    2.1442 -0.3202
    1.3635 -0.6915
    1.0663 -0.1084
    1.3356 0.4881
    2.1156 0.2068
    1.4884 -0.7177
    1.0993 -0.1394
    1.4010 0.4884
    2.1571 -0.1324
    1.3585 -0.6209
    1.1250 0.0497
    1.6440 0.5438
    1.9099 -0.6731
    1.2142 -0.5164
    1.1163 0.1394
    1.6314 0.5837
    1.9975 -0.6198
    1.2722 -0.6296
    1.0566 -0.0338
    1.3689 0.5289
    2.1472 0.1468
    1.4860 -0.7349
    1.0897 -0.1806
    1.3258 0.4533
    2.1189 0.1662
    1.4482 -0.6754
    1.1164 -0.0398
    1.5578 0.5296
    1.9951 -0.5697
    1.2472 -0.5377
    1.1278 0.1338
    1.6721 0.5665
    1.9241 -0.6850
    1.2302 -0.5706
    1.0743 0.0487
    1.4694 0.5730
    1.4694 0.5730
    2.1747 -0.1943
    1.3950 -0.7064
    1.0716 -0.1292
    1.3305 0.4774
    2.1129 0.2055
    1.4813 -0.7085
    1.1026 -0.1173
    1.4358 0.5019
    2.1353 -0.2562
    1.3290 -0.6023
    1.1252 0.0711
    1.6519 0.5493
    1.9119 -0.6771
    1.2173 -0.5288
    1.1053 0.1185
    1.5913 0.5864
    2.0483 -0.5455
    1.3001 -0.6527
    1.0577 -0.0611
    1.3519 0.5133
    2.1289 0.1904
    1.4958 -0.7332
    1.0934 -0.1771
    1.3403 0.4591
    2.1376 0.1020
    1.4239 -0.6594
    1.1210 -0.0080
    1.5983 0.5344
    1.9476 -0.6286
    1.2269 -0.5188
    1.1285 0.1494
    1.6748 0.5718
    1.9313 -0.6840
    1.2359 -0.5846
    1.0664 0.0261
    1.4344 0.5628
    2.1862 -0.0711
    1.4267 -0.7192
    1.0773 -0.1496
    1.3257 0.4669
    2.1104 0.2037
    1.4743 -0.6995
    1.1064 -0.0955
    1.4712 0.5128
    2.0997 -0.3700
    1.3020 -0.5831
    1.1257 0.0912
    1.6588 0.5546
    1.9150 -0.6802
    1.2208 -0.5414
    1.0951 0.0974
    1.5526 0.5858
    2.0946 -0.4546
    1.3280 -0.6715
    1.0609 -0.0834
    1.3427 0.5011
    2.1203 0.2047
    1.4952 -0.7275
    1.0961 -0.1633
    1.3639 0.4710
    2.1555 0.0078
    1.3950 -0.6423
    1.1239 0.0207
    1.6265 0.5381
    1.9192 -0.6593
    1.2161 -0.5101
    1.1262 0.1538
    1.6666 0.5769
    1.9488 -0.6716
    1.2462 -0.6010
    1.0604 0.0025
    1.4036 0.5500
    2.1771 0.0356
    1.4555 -0.7285
    1.0829 -0.1665
    1.3229 0.4586
    2.1105 0.1966
    1.4658 -0.6902
    1.1105 -0.0735
    1.5068 0.5213
    2.0578 -0.4657
    1.2776 -0.5642
    1.1264 0.1097
    1.6647 0.5596
    1.9187 -0.6824
    1.2246 -0.5538
    1.0858 0.0766
    1.5163 0.5821
    2.1346 -0.3504
    1.3558 -0.6875
    1.0651 -0.1032
    1.3369 0.4908
    2.1163 0.2071
    1.4901 -0.7199
    1.0985 -0.1448
    1.3926 0.4848
    2.1593 -0.1013
    1.3661 -0.6255
    1.1249 0.0441
    1.6414 0.5424
    1.9101 -0.6715
    1.2139 -0.5139
    1.1189 0.1439
    1.6408 0.5824
    1.9851 -0.6347
    1.2656 -0.6232
    1.0569 -0.0261
    1.3752 0.5335
    2.1537 0.1280
    1.4809 -0.7343
    1.0884 -0.1790
    1.3242 0.4535
    2.1159 0.1759
    1.4529 -0.6789
    1.1152 -0.0474
    1.5469 0.5282
    2.0085 -0.5504
    1.2532 -0.5432
    1.1275 0.1289
    1.6706 0.5651
    1.9229 -0.6845
    1.2290 -0.5671
    1.0766 0.0545
    1.4790 0.5752
    2.1682 -0.2274
    1.3866 -0.7028
    1.0702 -0.1238
    1.3318 0.4802
    2.1136 0.2058
    1.4832 -0.7109
    1.1017 -0.1230
    1.4266 0.4986
    2.1427 -0.2244
    1.3365 -0.6072
    1.1252 0.0657
    1.6500 0.5478
    1.9111 -0.6762
    1.2163 -0.5254
    1.1081 0.1241
    1.6018 0.5861
    1.6018 0.5861
    2.0353 -0.5668
    1.2927 -0.6471
    1.0571 -0.0546
    1.3553 0.5170
    2.1325 0.1830
    1.4946 -0.7342
    1.0926 -0.1794
    1.3354 0.4567
    2.1321 0.1226
    1.4310 -0.6639
    1.1199 -0.0163
    1.5886 0.5333
    1.9586 -0.6161
    1.2314 -0.5230
    1.1285 0.1462
    1.6748 0.5704
    1.9289 -0.6849
    1.2342 -0.5809
    1.0683 0.0319
    1.4431 0.5656
    2.1854 -0.1015
    1.4187 -0.7162
    1.0758 -0.1445
    1.3268 0.4695
    2.1110 0.2043
    1.4760 -0.7018
    1.1054 -0.1010
    1.4622 0.5103
    2.1096 -0.3427
    1.3086 -0.5880
    1.1255 0.0862
    1.6570 0.5533
    1.9142 -0.6793
    1.2199 -0.5383
    1.0975 0.1026
    1.5621 0.5862
    2.0836 -0.4789
    1.3210 -0.6670
    1.0600 -0.0780
    1.3447 0.5040
    2.1219 0.2025
    1.4959 -0.7291
    1.0954 -0.1673
    1.3575 0.4678
    2.1520 0.0331
    1.4023 -0.6465
    1.1233 0.0141
    1.6208 0.5373
    1.9243 -0.6537
    1.2179 -0.5111
    1.1272 0.1540
    1.6702 0.5755
    1.9429 -0.6765
    1.2429 -0.5964
    1.0617 0.0088
    1.4112 0.5536
    2.1810 0.0098
    1.4484 -0.7264
    1.0815 -0.1626
    1.3233 0.4605
    2.1101 0.1993
    1.4682 -0.6927
    1.1094 -0.0793
    1.4975 0.5192
    2.0691 -0.4426
    1.2837 -0.5691
    1.1262 0.1050
    1.6633 0.5584
    1.9176 -0.6819
    1.2236 -0.5506
    1.0881 0.0820
    1.5256 0.5833
    2.1248 -0.3788
    1.3485 -0.6835
    1.0639 -0.0981
    1.3383 0.4934
    2.1171 0.2072
    1.4917 -0.7220
    1.0979 -0.1500
    1.3847 0.4812
    2.1601 -0.0718
    1.3736 -0.6299
    1.1248 0.0384
    1.6385 0.5412
    1.9111 -0.6695
    1.2138 -0.5119
    1.1212 0.1477
    1.6491 0.5810
    1.9740 -0.6471
    1.2597 -0.6171
    1.0575 -0.0184
    1.3820 0.5380
    2.1603 0.1069
    1.4751 -0.7332
    1.0871 -0.1766
    1.3232 0.4543
    2.1138 0.1832
    1.4568 -0.6820
    1.1139 -0.0545
    1.5363 0.5266
    2.0216 -0.5303
    1.2594 -0.5487
    1.1272 0.1240
    1.6691 0.5637
    1.9219 -0.6839
    1.2279 -0.5638
    1.0789 0.0601
    1.4884 0.5772
    2.1608 -0.2595
    1.3786 -0.6990
    1.0688 -0.1185
    1.3332 0.4829
    2.1143 0.2061
    1.4849 -0.7132
    1.1008 -0.1286
    1.4178 0.4953
    2.1488 -0.1932
    1.3439 -0.6119
    1.1251 0.0603
    1.6481 0.5464
    1.9105 -0.6753
    1.2156 -0.5222
    1.1109 0.1295
    1.6120 0.5855
    1.6120 0.5855
    2.0224 -0.5862
    1.2856 -0.6414
    1.0568 -0.0479
    1.3592 0.5208
    2.1367 0.1735
    1.4926 -0.7348
    1.0917 -0.1807
    1.3314 0.4549
    2.1270 0.1400
    1.4374 -0.6680
    1.1188 -0.0244
    1.5785 0.5322
    1.9703 -0.6021
    1.2364 -0.5276
    1.1283 0.1424
    1.6742 0.5691
    1.9270 -0.6852
    1.2328 -0.5774
    1.0702 0.0375
    1.4517 0.5683
    2.1832 -0.1319
    1.4108 -0.7131
    1.0744 -0.1395
    1.3280 0.4721
    2.1116 0.2046
    1.4778 -0.7040
    1.1045 -0.1064
    1.4534 0.5077
    2.1187 -0.3149
    1.3152 -0.5928
    1.1254 0.0812
    1.6553 0.5519
    1.9135 -0.6785
    1.2190 -0.5352
    1.1000 0.1078
    1.5716 0.5864
    2.0723 -0.5017
    1.3141 -0.6625
    1.0592 -0.0727
    1.3468 0.5069
    2.1239 0.1995
    1.4963 -0.7305
    1.0948 -0.1709
    1.3515 0.4647
    2.1479 0.0568
    1.4094 -0.6508
    1.1227 0.0072
    1.6143 0.5363
    1.9306 -0.6471
    1.2202 -0.5129
    1.1279 0.1533
    1.6726 0.5743
    1.9382 -0.6799
    1.2402 -0.5923
    1.0632 0.0147
    1.4186 0.5568
    2.1839 -0.0159
    1.4415 -0.7243
    1.0801 -0.1585
    1.3239 0.4624
    2.1100 0.2012
    1.4703 -0.6950
    1.1084 -0.0847
    1.4887 0.5172
    2.0795 -0.4197
    1.2897 -0.5737
    1.1260 0.1005
    1.6619 0.5569
    1.9167 -0.6814
    1.2226 -0.5476
    1.0904 0.0871
    1.5345 0.5842
    2.1152 -0.4047
    1.3417 -0.6797
    1.0629 -0.0933
    1.3396 0.4959
    2.1179 0.2069
    1.4931 -0.7239
    1.0973 -0.1546
    1.3776 0.4778
    2.1597 -0.0447
    1.3807 -0.6340
    1.1246 0.0328
    1.6352 0.5401
    1.9128 -0.6669
    1.2141 -0.5106
    1.1232 0.1505
    1.6560 0.5797
    1.9645 -0.6569
    1.2546 -0.6114
    1.0583 -0.0113
    1.3888 0.5422
    2.1664 0.0847
    1.4690 -0.7319
    1.0857 -0.1736
    1.3228 0.4554
    2.1123 0.1885
    1.4600 -0.6849
    1.1128 -0.0610
    1.5264 0.5249
    2.0338 -0.5100
    1.2653 -0.5539
    1.1269 0.1192
    1.6676 0.5624
    1.9209 -0.6834
    1.2269 -0.5605
    1.0811 0.0655
    1.4975 0.5789
    2.1530 -0.2898
    1.3711 -0.6953
    1.0675 -0.1134
    1.3344 0.4855
    2.1150 0.2063
    1.4866 -0.7154
    1.1001 -0.1339
    1.4095 0.4920
    2.1535 -0.1633
    1.3510 -0.6164
    1.1251 0.0552
    1.6461 0.5451
    1.9101 -0.6743
    1.2149 -0.5193
    1.1136 0.1344
    1.6216 0.5847
    2.0102 -0.6033
    1.2790 -0.6357
    1.0566 -0.0412
    1.3636 0.5247
    2.1415 0.1618
    1.4899 -0.7350
    1.0908 -0.1811
    1.3283 0.4538
    2.1227 0.1539
    1.4430 -0.6716
    1.1177 -0.0320
    1.5685 0.5310
    1.9822 -0.5871
    1.2414 -0.5324
    1.1281 0.1383
    1.6733 0.5678
    1.9256 -0.6852
    1.2315 -0.5741
    1.0722 0.0429
    1.4602 0.5706
    2.1797 -0.1618
    1.4032 -0.7099
    1.0730 -0.1346
    1.3292 0.4747
    2.1123 0.2050
    1.4794 -0.7062
    1.1035 -0.1116
    1.4450 0.5050
    2.1270 -0.2871
    1.3218 -0.5974
    1.1253 0.0763
    1.6536 0.5508
    1.9128 -0.6778
    1.2182 -0.5322
    1.1025 0.1128
    1.5808 0.5866
    2.0611 -0.5230
    1.3074 -0.6579
    1.0585 -0.0673
    1.3491 0.5099
    2.1261 0.1957
    1.4962 -0.7319
    1.0942 -0.1741
    1.3460 0.4619
    2.1432 0.0789
    1.4163 -0.6549
    1.1219 0.0002
    1.6072 0.5354
    1.9380 -0.6391
    1.2231 -0.5153
    1.1283 0.1519
    1.6740 0.5731
    1.9346 -0.6823
    1.2380 -0.5885
    1.0646 0.0201
    1.4260 0.5597
    2.1856 -0.0415
    1.4345 -0.7220
    1.0788 -0.1544
    1.3247 0.4645
    2.1101 0.2026
    1.4722 -0.6971
    1.1074 -0.0898
    1.4804 0.5152
    2.0892 -0.3968
    1.2954 -0.5782
    1.1259 0.0961
    1.6604 0.5559
    1.9159 -0.6808
    1.2217 -0.5447
    1.0925 0.0919
    1.5430 0.5850
    2.1057 -0.4286
    1.3352 -0.6759
    1.0619 -0.0887
    1.3410 0.4983
    2.1189 0.2061
    1.4942 -0.7256
    1.0967 -0.1588
    1.3710 0.4746
    2.1582 -0.0196
    1.3874 -0.6379
    1.1243 0.0273
    1.6314 0.5392
    1.9153 -0.6637
    1.2148 -0.5101
    1.1247 0.1525
    1.6615 0.5783
    1.9565 -0.6646
    1.2504 -0.6064
    1.0592 -0.0047
    1.3957 0.5459
    2.1718 0.0622
    1.4627 -0.7304
    1.0844 -0.1704
    1.3227 0.4568
    2.1113 0.1927
    1.4628 -0.6875
    1.1117 -0.0669
    1.5172 0.5232
    2.0452 -0.4898
    1.2711 -0.5587
    1.1267 0.1147
    1.6662 0.5611
    1.9199 -0.6829
    1.2259 -0.5574
    1.2258 -0.5575
    1.0833 0.0706
    1.5062 0.5804
    2.1447 -0.3184
    1.3639 -0.6917
    1.0664 -0.1086
    1.3356 0.4880
    2.1157 0.2067
    1.4882 -0.7175
    1.0993 -0.1390
    1.4016 0.4887
    2.1569 -0.1345
    1.3579 -0.6207
    1.1250 0.0501
    1.6441 0.5438
    1.9100 -0.6732
    1.2143 -0.5167
    1.1161 0.1390
    1.6306 0.5837
    1.9985 -0.6186
    1.2727 -0.6301
    1.0566 -0.0344
    1.3685 0.5286
    2.1468 0.1479
    1.4863 -0.7349
    1.0898 -0.1806
    1.3261 0.4533
    2.1192 0.1652
    1.4478 -0.6751
    1.1165 -0.0392
    1.5586 0.5298
    1.9941 -0.5711
    1.2467 -0.5373
    1.1279 0.1341
    1.6721 0.5666
    1.9243 -0.6849
    1.2304 -0.5709
    1.0742 0.0481
    1.4687 0.5728
    2.1752 -0.1915
    1.3956 -0.7067
    1.0717 -0.1297
    1.3304 0.4772
    2.1129 0.2053
    1.4811 -0.7083
    1.1027 -0.1167
    1.4366 0.5022
    2.1346 -0.2591
    1.3284 -0.6019
    1.1252 0.0715
    1.6520 0.5495
    1.9121 -0.6771
    1.2174 -0.5292
    1.1050 0.1179
    1.5902 0.5865
    2.0496 -0.5433
    1.3008 -0.6532
    1.0578 -0.0617
    1.3516 0.5130
    2.1286 0.1909
    1.4959 -0.7330
    1.0935 -0.1768
    1.3409 0.4594
    2.1383 0.0996
    1.4230 -0.6590
    1.1211 -0.0071
    1.5993 0.5345
    1.9466 -0.6298
    1.2265 -0.5184
    1.1285 0.1497
    1.6747 0.5720
    1.9317 -0.6838
    1.2362 -0.5850
    1.0662 0.0255
    1.4335 0.5624
    2.1863 -0.0678
    1.4276 -0.7195
    1.0774 -0.1501
    1.3256 0.4667
    2.1104 0.2035
    1.4740 -0.6993
    1.1066 -0.0948
    1.4723 0.5131
    2.0985 -0.3732
    1.3012 -0.5826
    1.1257 0.0917
    1.6589 0.5548
    1.9151 -0.6802
    1.2209 -0.5418
    1.0947 0.0967
    1.5514 0.5856
    2.0960 -0.4514
    1.3289 -0.6721
    1.0611 -0.0840
    1.3425 0.5008
    2.1202 0.2048
    1.4951 -0.7271
    1.0961 -0.1627
    1.3649 0.4715
    2.1560 0.0042
    1.3940 -0.6417
    1.1239 0.0216
    1.6271 0.5383
    1.9187 -0.6599
    1.2159 -0.5101
    1.1260 0.1536
    1.6659 0.5771
    1.9499 -0.6707
    1.2467 -0.6017
    1.0603 0.0015
    1.4025 0.5495
    2.1764 0.0393
    1.4564 -0.7288
    1.0831 -0.1671
    1.3229 0.4583
    2.1106 0.1960
    1.4653 -0.6899
    1.1106 -0.0725
    1.5082 0.5216
    2.0561 -0.4692
    1.2767 -0.5634
    1.1265 0.1104
    1.6648 0.5599
    1.9189 -0.6824
    1.2248 -0.5544
    1.0854 0.0757
    1.5148 0.5818
    2.1361 -0.3457
    1.3570 -0.6881
    1.0653 -0.1040
    1.3368 0.4904
    2.1163 0.2069
    1.4898 -0.7195
    1.0987 -0.1439
    1.3940 0.4854
    2.1590 -0.1065
    1.3649 -0.6247
    1.1249 0.0450
    1.6418 0.5427
    1.9101 -0.6717
    1.2139 -0.5144
    1.1185 0.1431
    1.6392 0.5826
    1.9873 -0.6322
    1.2667 -0.6243
    1.0569 -0.0274
    1.3740 0.5327
    2.1526 0.1314
    1.4818 -0.7344
    1.0886 -0.1793
    1.3245 0.4534
    2.1164 0.1742
    1.4521 -0.6782
    1.1154 -0.0461
    1.5488 0.5285
    2.0061 -0.5540
    1.2521 -0.5423
    1.1276 0.1297
    1.6708 0.5653
    1.9232 -0.6845
    1.2293 -0.5678
    1.0762 0.0534
    1.4772 0.5748
    2.1695 -0.2212
    1.3882 -0.7035
    1.0704 -0.1248
    1.3316 0.4797
    2.1135 0.2056
    1.4827 -0.7105
    1.1018 -0.1219
    1.4284 0.4993
    2.1413 -0.2306
    1.3351 -0.6063
    1.1251 0.0667
    1.6503 0.5481
diary
rzdat
rzdat =
    1.3544 0.5160
    1.3364 0.4571
    1.5909 0.5336
    1.6749 0.5707
    1.4411 0.5650
    1.3265 0.4689
    1.4641 0.5108
    1.6575 0.5536
    1.5601 0.5861
    1.3442 0.5034
    1.3587 0.4684
    1.6221 0.5373
    1.6697 0.5758
    1.4097 0.5530
    1.3232 0.4600
    1.4992 0.5196
    1.6636 0.5586
    1.5240 0.5830
    1.3380 0.4929
    1.3860 0.4818
    1.6391 0.5415
    1.6479 0.5814
    1.3808 0.5373
    1.3233 0.4540
    1.5380 0.5267
    1.6693 0.5640
    1.4870 0.5769
    1.3329 0.4825
    1.4191 0.4957
    1.6484 0.5467
    1.6106 0.5857
    1.3586 0.5202
    1.3318 0.4550
    1.5799 0.5323
    1.6744 0.5693
    1.4506 0.5679
    1.3278 0.4718
    1.4544 0.5080
    1.6556 0.5522
    1.5705 0.5864
    1.3465 0.5066
    1.3520 0.4651
    1.6151 0.5365
    1.6725 0.5744
    1.4179 0.5565
    1.3238 0.4622
    1.4895 0.5174
    1.6620 0.5572
    1.5338 0.5842
    1.3395 0.4957
    1.3780 0.4780
    1.6355 0.5402
    1.6557 0.5798
    1.3884 0.5419
    1.3228 0.4553
    1.5269 0.5251
    1.6677 0.5625
    1.4970 0.5789
    1.3343 0.4854
    1.4098 0.4921
    1.6463 0.5452
    1.6213 0.5848
    1.3634 0.5245
    1.3283 0.4538
    1.5688 0.5310
    1.6733 0.5679
    1.4600 0.5706
    1.3292 0.4746
    1.4450 0.5050
    1.6537 0.5508
    1.5808 0.5865
    1.3490 0.5099
    1.3459 0.4619
    1.6072 0.5355
    1.6741 0.5730
    1.4261 0.5598
    1.3246 0.4645
    1.4803 0.5151
    1.6604 0.5560
    1.5432 0.5851
    1.3410 0.4984
    1.3708 0.4744
    1.6313 0.5392
    1.6618 0.5784
    1.3960 0.5461
    1.3227 0.4568
    1.5166 0.5231
    1.6662 0.5611
    1.5068 0.5805
    1.3356 0.4881
    1.4010 0.4884
    1.6440 0.5438
    1.6314 0.5837
    1.3689 0.5289
    1.3258 0.4533
    1.5578 0.5296
    1.6721 0.5665
    1.4694 0.5730
    1.4694 0.5730
    1.3305 0.4774
    1.4358 0.5019
    1.6519 0.5493
    1.5913 0.5864
    1.3519 0.5133
    1.3403 0.4591
    1.5983 0.5344
    1.6748 0.5718
    1.4344 0.5628
    1.3257 0.4669
    1.4712 0.5128
    1.6588 0.5546
    1.5526 0.5858
    1.3427 0.5011
    1.3639 0.4710
    1.6265 0.5381
    1.6666 0.5769
    1.4036 0.5500
    1.3229 0.4586
    1.5068 0.5213
    1.6647 0.5596
    1.5163 0.5821
    1.3369 0.4908
    1.3926 0.4848
    1.6414 0.5424
    1.6408 0.5824
    1.3752 0.5335
    1.3242 0.4535
    1.5469 0.5282
    1.6706 0.5651
    1.4790 0.5752
    1.3318 0.4802
    1.4266 0.4986
    1.6500 0.5478
    1.6018 0.5861
    1.6018 0.5861
    1.3553 0.5170
    1.3354 0.4567
    1.5886 0.5333
    1.6748 0.5704
    1.4431 0.5656
    1.3268 0.4695
    1.4622 0.5103
    1.6570 0.5533
    1.5621 0.5862
    1.3447 0.5040
    1.3575 0.4678
    1.6208 0.5373
    1.6702 0.5755
    1.4112 0.5536
    1.3233 0.4605
    1.4975 0.5192
    1.6633 0.5584
    1.5256 0.5833
    1.3383 0.4934
    1.3847 0.4812
    1.6385 0.5412
    1.6491 0.5810
    1.3820 0.5380
    1.3232 0.4543
    1.5363 0.5266
    1.6691 0.5637
    1.4884 0.5772
    1.3332 0.4829
    1.4178 0.4953
    1.6481 0.5464
    1.6120 0.5855
    1.6120 0.5855
    1.3592 0.5208
    1.3314 0.4549
    1.5785 0.5322
    1.6742 0.5691
    1.4517 0.5683
    1.3280 0.4721
    1.4534 0.5077
    1.6553 0.5519
    1.5716 0.5864
    1.3468 0.5069
    1.3515 0.4647
    1.6143 0.5363
    1.6726 0.5743
    1.4186 0.5568
    1.3239 0.4624
    1.4887 0.5172
    1.6619 0.5569
    1.5345 0.5842
    1.3396 0.4959
    1.3776 0.4778
    1.6352 0.5401
    1.6560 0.5797
    1.3888 0.5422
    1.3228 0.4554
    1.5264 0.5249
    1.6676 0.5624
    1.4975 0.5789
    1.3344 0.4855
    1.4095 0.4920
    1.6461 0.5451
    1.6216 0.5847
    1.3636 0.5247
    1.3283 0.4538
    1.5685 0.5310
    1.6733 0.5678
    1.4602 0.5706
    1.3292 0.4747
    1.4450 0.5050
    1.6536 0.5508
    1.5808 0.5866
    1.3491 0.5099
    1.3460 0.4619
    1.6072 0.5354
    1.6740 0.5731
    1.4260 0.5597
    1.3247 0.4645
    1.4804 0.5152
    1.6604 0.5559
    1.5430 0.5850
    1.3410 0.4983
    1.3710 0.4746
    1.6314 0.5392
    1.6615 0.5783
    1.3957 0.5459
    1.3227 0.4568
    1.5172 0.5232
    1.6662 0.5611
    1.5062 0.5804
    1.3356 0.4880
    1.4016 0.4887
    1.6441 0.5438
    1.6306 0.5837
    1.3685 0.5286
    1.3261 0.4533
    1.5586 0.5298
    1.6721 0.5666
    1.4687 0.5728
    1.3304 0.4772
    1.4366 0.5022
    1.6520 0.5495
    1.5902 0.5865
    1.3516 0.5130
    1.3409 0.4594
    1.5993 0.5345
    1.6747 0.5720
    1.4335 0.5624
    1.3256 0.4667
    1.4723 0.5131
    1.6589 0.5548
    1.5514 0.5856
    1.3425 0.5008
    1.3649 0.4715
    1.6271 0.5383
    1.6659 0.5771
    1.4025 0.5495
    1.3229 0.4583
    1.5082 0.5216
    1.6648 0.5599
    1.5148 0.5818
    1.3368 0.4904
    1.3940 0.4854
    1.6418 0.5427
    1.6392 0.5826
    1.3740 0.5327
    1.3245 0.4534
    1.5488 0.5285
    1.6708 0.5653
    1.4772 0.5748
    1.3316 0.4797
    1.4284 0.4993
    1.6503 0.5481
figure,triplot(delaunay(rzdat(:,1),rzdat(:,2)),rzdat(:,1),rzdat(:,2))

Subject: concave hull/polygon

From: Alex James

Date: 6 Oct, 2010 10:21:06

Message: 8 of 9

FWIW I'm pretty sure the triangulation returned by the version of matlab I'm using is actually not a delaunay triangulation, as the circumcircles defined by a set of three points appear to enclose _many_ more than the three points defining that circle.

Doh.

Subject: concave hull/polygon

From: Steven_Lord

Date: 7 Oct, 2010 01:51:54

Message: 9 of 9



"Alex James" <alex.n.james@gmail.com> wrote in message
news:i8hhq4$fme$1@fred.mathworks.com...
>> Today is your lucky day.
>>
>> Here is the solution:
>>
>> 2D : FInd delaunay edges, discover how on the Maltab help from r2009a
>>
>> Follow this:
>>
>> doc
>> demos
>> Mathematics
>> Creating and editing delaunay
>> triangulation
>> Example 7(Example Seven: Curve
>> Reconstruction from a Point Cloud)
>
> Not sure if it's that it's raining in CA or that I'm still up at 3am, but
> I don't think today is my lucky day as you say.
>
> When I plot the delaunay triangulation returned by matlab for my concave
> dataset (sort of a crescent), some of the triangles connect across the
> ends of the crescent in the concave region contrary to the desired result
> of the triangles following the edge of the crescent... matlab version,
> dataset, and test code below. Is this the desired functionality, or a bug?

*snip*

The union of all the triangles that make up the Delaunay triangulation of
the set of points is the _convex hull_ of that set of points. If your
dataset is not convex, then the expected behavior is that some of the
triangles would lie outside your concave region.

http://en.wikipedia.org/wiki/Delaunay_triangulation#Properties

The same set of points may make up multiple different shapes. After all,
are these points:

x = [0 1 2 2 0];
y = [0 1 0 2 2];
plot(x, y, 'o')

% supposed to form:

subplot(2, 2, 1)
iv = [1 3 4 5 1];
plot(x(iv), y(iv), '-');
axis([-1 3 -1 3])

% or this?

subplot(2, 2, 2)
iv = [1 2 3 4 5 1];
plot(x(iv), y(iv), '-');
axis([-1 3 -1 3])

% or this?

subplot(2, 2, 3)
iv = [1 3 2 4 5 1];
plot(x(iv), y(iv), '-');
axis([-1 3 -1 3])

% or even this?

subplot(2, 2, 4)
iv = [1 2 3 4 2 5 1];
plot(x(iv), y(iv), '-');
axis([-1 3 -1 3])

If, as in your other post in this thread, you believe you've found a set of
data for which DELAUNAY is not working correctly, send it to Technical
Support and explain what you believe is incorrect.

--
Steve Lord
slord@mathworks.com
comp.soft-sys.matlab (CSSM) FAQ: http://matlabwiki.mathworks.com/MATLAB_FAQ
To contact Technical Support use the Contact Us link on
http://www.mathworks.com

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us