Changeset 9945 for branches/HeuristicLab.Analysis.AlgorithmBehavior/MIConvexHull/ConvexHull/ConvexHullInternal.cs
- Timestamp:
- 09/10/13 21:06:55 (11 years ago)
- Location:
- branches/HeuristicLab.Analysis.AlgorithmBehavior
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/HeuristicLab.Analysis.AlgorithmBehavior
-
Property
svn:global-ignores
set to
HeuristicLab.Analysis.AlgorithmBehavior.sln.DotSettings.user
-
Property
svn:global-ignores
set to
-
branches/HeuristicLab.Analysis.AlgorithmBehavior/MIConvexHull/ConvexHull/ConvexHullInternal.cs
r9730 r9945 42 42 VertexBuffer BeyondBuffer; 43 43 List<ConvexFaceInternal> AffectedFaceBuffer; 44 List<DeferredFace> ConeFaceBuffer; 45 Stack<DeferredFace> ConeFaceStack; 46 HashSet<VertexWrap> SingularVertices; 44 47 45 48 const int ConnectorTableSize = 2017; … … 69 72 EmptyBuffer = new VertexBuffer(); 70 73 AffectedFaceBuffer = new List<ConvexFaceInternal>(); 74 ConeFaceBuffer = new List<DeferredFace>(); 75 ConeFaceStack = new Stack<DeferredFace>(); 76 SingularVertices = new HashSet<VertexWrap>(); 71 77 BeyondBuffer = new VertexBuffer(); 72 78 … … 130 136 /// <param name="face"></param> 131 137 /// <returns></returns> 132 private voidCalculateFacePlane(ConvexFaceInternal face)138 private bool CalculateFacePlane(ConvexFaceInternal face) 133 139 { 134 140 var vertices = face.Vertices; … … 136 142 FindNormalVector(vertices, normal); 137 143 138 if (double.IsNaN(normal[0])) ThrowSingular(); 144 if (double.IsNaN(normal[0])) 145 { 146 return false; 147 //ThrowSingular(); 148 } 139 149 140 150 double offset = 0.0; … … 157 167 } 158 168 else face.IsNormalFlipped = false; 169 170 return true; 159 171 } 160 172 … … 318 330 319 331 /// <summary> 332 /// Creates a new deferred face. 333 /// </summary> 334 /// <param name="face"></param> 335 /// <param name="faceIndex"></param> 336 /// <param name="pivot"></param> 337 /// <param name="pivotIndex"></param> 338 /// <param name="oldFace"></param> 339 /// <returns></returns> 340 DeferredFace GetDeferredFace(ConvexFaceInternal face, int faceIndex, ConvexFaceInternal pivot, int pivotIndex, ConvexFaceInternal oldFace) 341 { 342 var ret = ConeFaceStack.Count > 0 ? ConeFaceStack.Pop() : new DeferredFace(); 343 344 ret.Face = face; 345 ret.FaceIndex = faceIndex; 346 ret.Pivot = pivot; 347 ret.PivotIndex = pivotIndex; 348 ret.OldFace = oldFace; 349 350 return ret; 351 } 352 353 /// <summary> 320 354 /// Connect faces using a connector. 321 355 /// </summary> … … 326 360 var list = ConnectorTable[index]; 327 361 328 int count = 0;329 362 for (var current = list.First; current != null; current = current.Next) 330 363 { … … 347 380 /// Removes the faces "covered" by the current vertex and adds the newly created ones. 348 381 /// </summary> 349 private void CreateCone() 350 { 351 var oldFaces = AffectedFaceBuffer; 352 382 private bool CreateCone() 383 { 353 384 var currentVertexIndex = CurrentVertex.Index; 354 355 for (int fIndex = 0; fIndex < oldFaces.Count; fIndex++) 356 { 357 var oldFace = oldFaces[fIndex]; 385 ConeFaceBuffer.Clear(); 386 387 for (int fIndex = 0; fIndex < AffectedFaceBuffer.Count; fIndex++) 388 { 389 var oldFace = AffectedFaceBuffer[fIndex]; 358 390 359 391 // Find the faces that need to be updated … … 368 400 ++updateCount; 369 401 } 370 }371 372 // Recycle the face for future use373 if (updateCount == 0)374 {375 // If the face is present in the unprocessed list, remove it376 UnprocessedFaces.Remove(oldFace);377 378 RecycleFace(oldFace);379 RecycledFaceStack.Push(oldFace);380 402 } 381 403 … … 402 424 VertexWrap[] vertices; 403 425 404 // Recycle the oldFace 405 if (i == updateCount - 1) 406 { 407 RecycleFace(oldFace); 408 newFace = oldFace; 409 vertices = newFace.Vertices; 410 oldVertexIndex = vertices[forbidden].Index; 411 } 412 else // Pop a face from the recycled stack or create a new one 413 { 414 newFace = GetNewFace(); 415 vertices = newFace.Vertices; 416 for (int j = 0; j < Dimension; j++) vertices[j] = oldFace.Vertices[j]; 417 oldVertexIndex = vertices[forbidden].Index; 418 } 426 newFace = GetNewFace(); 427 vertices = newFace.Vertices; 428 for (int j = 0; j < Dimension; j++) vertices[j] = oldFace.Vertices[j]; 429 oldVertexIndex = vertices[forbidden].Index; 419 430 420 431 int orderedPivotIndex; … … 450 461 vertices[orderedPivotIndex] = CurrentVertex; 451 462 452 CalculateFacePlane(newFace); 453 newFace.AdjacentFaces[orderedPivotIndex] = adjacentFace; 454 adjacentFace.AdjacentFaces[oldFaceAdjacentIndex] = newFace; 455 456 // let there be a connection. 457 for (int j = 0; j < Dimension; j++) 463 if (!CalculateFacePlane(newFace)) 458 464 { 459 if (j == orderedPivotIndex) continue; 460 var connector = GetNewConnector(); 461 connector.Update(newFace, j, Dimension); 462 ConnectFace(connector); 465 return false; 463 466 } 464 465 // This could slightly help... 466 if (adjacentFace.VerticesBeyond.Count < oldFace.VerticesBeyond.Count) 467 { 468 FindBeyondVertices(newFace, adjacentFace.VerticesBeyond, oldFace.VerticesBeyond); 469 } 470 else 471 { 472 FindBeyondVertices(newFace, oldFace.VerticesBeyond, adjacentFace.VerticesBeyond); 473 } 474 475 // This face will definitely lie on the hull 476 if (newFace.VerticesBeyond.Count == 0) 477 { 478 ConvexFaces.Add(newFace); 479 UnprocessedFaces.Remove(newFace); 480 EmptyBufferStack.Push(newFace.VerticesBeyond); 481 newFace.VerticesBeyond = EmptyBuffer; 482 } 483 else // Add the face to the list 484 { 485 UnprocessedFaces.Add(newFace); 486 } 487 } 467 468 ConeFaceBuffer.Add(GetDeferredFace(newFace, orderedPivotIndex, adjacentFace, oldFaceAdjacentIndex, oldFace)); 469 } 470 } 471 472 return true; 473 } 474 475 /// <summary> 476 /// Commits a cone and adds a vertex to the convex hull. 477 /// </summary> 478 void CommitCone() 479 { 480 // Add the current vertex. 481 ConvexHull.Add(CurrentVertex); 482 483 // Fill the adjacency. 484 for (int i = 0; i < ConeFaceBuffer.Count; i++) 485 { 486 var face = ConeFaceBuffer[i]; 487 488 var newFace = face.Face; 489 var adjacentFace = face.Pivot; 490 var oldFace = face.OldFace; 491 var orderedPivotIndex = face.FaceIndex; 492 493 newFace.AdjacentFaces[orderedPivotIndex] = adjacentFace; 494 adjacentFace.AdjacentFaces[face.PivotIndex] = newFace; 495 496 // let there be a connection. 497 for (int j = 0; j < Dimension; j++) 498 { 499 if (j == orderedPivotIndex) continue; 500 var connector = GetNewConnector(); 501 connector.Update(newFace, j, Dimension); 502 ConnectFace(connector); 503 } 504 505 // This could slightly help... 506 if (adjacentFace.VerticesBeyond.Count < oldFace.VerticesBeyond.Count) 507 { 508 FindBeyondVertices(newFace, adjacentFace.VerticesBeyond, oldFace.VerticesBeyond); 509 } 510 else 511 { 512 FindBeyondVertices(newFace, oldFace.VerticesBeyond, adjacentFace.VerticesBeyond); 513 } 514 515 // This face will definitely lie on the hull 516 if (newFace.VerticesBeyond.Count == 0) 517 { 518 ConvexFaces.Add(newFace); 519 UnprocessedFaces.Remove(newFace); 520 EmptyBufferStack.Push(newFace.VerticesBeyond); 521 newFace.VerticesBeyond = EmptyBuffer; 522 } 523 else // Add the face to the list 524 { 525 UnprocessedFaces.Add(newFace); 526 } 527 528 // recycle the object. 529 ConeFaceStack.Push(face); 530 } 531 532 // Recycle the affected faces. 533 for (int fIndex = 0; fIndex < AffectedFaceBuffer.Count; fIndex++) 534 { 535 var face = AffectedFaceBuffer[fIndex]; 536 UnprocessedFaces.Remove(face); 537 RecycleFace(face); 538 RecycledFaceStack.Push(face); 488 539 } 489 540 } … … 698 749 void UpdateCenter() 699 750 { 700 for (int i = 0; i < Dimension; i++) Center[i] *= (ConvexHull.Count - 1); 701 double f = 1.0 / ConvexHull.Count; 751 var count = ConvexHull.Count + 1; 752 for (int i = 0; i < Dimension; i++) Center[i] *= (count - 1); 753 double f = 1.0 / count; 702 754 for (int i = 0; i < Dimension; i++) Center[i] = f * (Center[i] + CurrentVertex.PositionData[i]); 755 } 756 757 /// <summary> 758 /// Removes the last vertex from the center. 759 /// </summary> 760 void RollbackCenter() 761 { 762 var count = ConvexHull.Count + 1; 763 for (int i = 0; i < Dimension; i++) Center[i] *= count; 764 double f = 1.0 / (count - 1); 765 for (int i = 0; i < Dimension; i++) Center[i] = f * (Center[i] - CurrentVertex.PositionData[i]); 703 766 } 704 767 … … 715 778 { 716 779 CurrentVertex = vertex; 780 // update center must be called before adding the vertex. 781 UpdateCenter(); 717 782 ConvexHull.Add(CurrentVertex); 718 UpdateCenter();719 783 InputVertices.Remove(vertex); 720 784 … … 767 831 for (int i = 2; i <= Dimension; i++) 768 832 { 769 double maximum = 0.000 1;833 double maximum = 0.000001; 770 834 VertexWrap maxPoint = null; 771 835 for (int j = 0; j < extremes.Count; j++) … … 817 881 double GetSimplexVolume(VertexWrap pivot, List<VertexWrap> initialPoints) 818 882 { 819 var dim = initialPoints.Count; 820 var m = nDMatrix; 821 822 for (int i = 0; i < dim; i++) 823 { 824 var pts = initialPoints[i]; 825 for (int j = 0; j < dim; j++) m[i, j] = pts.PositionData[j] - pivot.PositionData[j]; 826 } 827 828 return Math.Abs(StarMath.determinantDestructive(m, dim)); 883 var initPtsNum = initialPoints.Count; 884 //var m = nDMatrix; 885 var sum = 0.0; 886 887 for (int i = 0; i < initPtsNum; i++) 888 { 889 var initPt = initialPoints[i]; 890 for (int j = 0; j < Dimension; j++) 891 sum += (initPt.PositionData[j] - pivot.PositionData[j]) 892 * (initPt.PositionData[j] - pivot.PositionData[j]); 893 } 894 895 return sum; 829 896 } 830 897 … … 878 945 879 946 /// <summary> 947 /// Handles singular vertex. 948 /// </summary> 949 void HandleSingular() 950 { 951 RollbackCenter(); 952 SingularVertices.Add(CurrentVertex); 953 954 // This means that all the affected faces must be on the hull and that all their "vertices beyond" are singular. 955 for (int fIndex = 0; fIndex < AffectedFaceBuffer.Count; fIndex++) 956 { 957 var face = AffectedFaceBuffer[fIndex]; 958 var vb = face.VerticesBeyond; 959 for (int i = 0; i < vb.Count; i++) 960 { 961 SingularVertices.Add(vb[i]); 962 } 963 964 ConvexFaces.Add(face); 965 UnprocessedFaces.Remove(face); 966 EmptyBufferStack.Push(face.VerticesBeyond); 967 face.VerticesBeyond = EmptyBuffer; 968 } 969 } 970 971 /// <summary> 880 972 /// Fins the convex hull. 881 973 /// </summary> … … 890 982 var currentFace = UnprocessedFaces.First; 891 983 CurrentVertex = currentFace.FurthestVertex; 892 ConvexHull.Add(CurrentVertex);984 893 985 UpdateCenter(); 894 986 … … 897 989 898 990 // Create the cone from the currentVertex and the affected faces horizon. 899 CreateCone(); 991 if (!SingularVertices.Contains(CurrentVertex) && CreateCone()) CommitCone(); 992 else HandleSingular(); 900 993 901 994 // Need to reset the tags
Note: See TracChangeset
for help on using the changeset viewer.