TriangulationUtil.cs 4.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145
  1. /* Poly2Tri
  2. * Copyright (c) 2009-2010, Poly2Tri Contributors
  3. * http://code.google.com/p/poly2tri/
  4. *
  5. * All rights reserved.
  6. *
  7. * Redistribution and use in source and binary forms, with or without modification,
  8. * are permitted provided that the following conditions are met:
  9. *
  10. * * Redistributions of source code must retain the above copyright notice,
  11. * this list of conditions and the following disclaimer.
  12. * * Redistributions in binary form must reproduce the above copyright notice,
  13. * this list of conditions and the following disclaimer in the documentation
  14. * and/or other materials provided with the distribution.
  15. * * Neither the name of Poly2Tri nor the names of its contributors may be
  16. * used to endorse or promote products derived from this software without specific
  17. * prior written permission.
  18. *
  19. * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  20. * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  21. * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  22. * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
  23. * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  24. * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  25. * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  26. * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  27. * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  28. * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  29. * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  30. */
  31. namespace Veldrid.Common.Poly2Tri.Triangulation
  32. {
  33. /**
  34. * @author Thomas Åhlén, thahlen@gmail.com
  35. */
  36. public class TriangulationUtil {
  37. public static double EPSILON = 1e-12;
  38. /// <summary>
  39. /// Requirements:
  40. /// 1. a,b and c form a triangle.
  41. /// 2. a and d is know to be on opposite side of bc
  42. /// <code>
  43. /// a
  44. /// +
  45. /// / \
  46. /// / \
  47. /// b/ \c
  48. /// +-------+
  49. /// / B \
  50. /// / \
  51. /// </code>
  52. /// Facts:
  53. /// d has to be in area B to have a chance to be inside the circle formed by a,b and c
  54. /// d is outside B if orient2d(a,b,d) or orient2d(c,a,d) is CW
  55. /// This preknowledge gives us a way to optimize the incircle test
  56. /// </summary>
  57. /// <param name="pa">triangle point, opposite d</param>
  58. /// <param name="pb">triangle point</param>
  59. /// <param name="pc">triangle point</param>
  60. /// <param name="pd">point opposite a</param>
  61. /// <returns>true if d is inside circle, false if on circle edge</returns>
  62. public static bool SmartIncircle( TriangulationPoint pa, TriangulationPoint pb, TriangulationPoint pc, TriangulationPoint pd ) {
  63. double pdx = pd.X;
  64. double pdy = pd.Y;
  65. double adx = pa.X - pdx;
  66. double ady = pa.Y - pdy;
  67. double bdx = pb.X - pdx;
  68. double bdy = pb.Y - pdy;
  69. double adxbdy = adx * bdy;
  70. double bdxady = bdx * ady;
  71. double oabd = adxbdy - bdxady;
  72. // oabd = orient2d(pa,pb,pd);
  73. if (oabd <= 0) return false;
  74. double cdx = pc.X - pdx;
  75. double cdy = pc.Y - pdy;
  76. double cdxady = cdx * ady;
  77. double adxcdy = adx * cdy;
  78. double ocad = cdxady - adxcdy;
  79. // ocad = orient2d(pc,pa,pd);
  80. if (ocad <= 0) return false;
  81. double bdxcdy = bdx * cdy;
  82. double cdxbdy = cdx * bdy;
  83. double alift = adx * adx + ady * ady;
  84. double blift = bdx * bdx + bdy * bdy;
  85. double clift = cdx * cdx + cdy * cdy;
  86. double det = alift * (bdxcdy - cdxbdy) + blift * ocad + clift * oabd;
  87. return det > 0;
  88. }
  89. public static bool InScanArea( TriangulationPoint pa, TriangulationPoint pb, TriangulationPoint pc, TriangulationPoint pd ) {
  90. double pdx = pd.X;
  91. double pdy = pd.Y;
  92. double adx = pa.X - pdx;
  93. double ady = pa.Y - pdy;
  94. double bdx = pb.X - pdx;
  95. double bdy = pb.Y - pdy;
  96. double adxbdy = adx * bdy;
  97. double bdxady = bdx * ady;
  98. double oabd = adxbdy - bdxady;
  99. // oabd = orient2d(pa,pb,pd);
  100. if (oabd <= 0) {
  101. return false;
  102. }
  103. double cdx = pc.X - pdx;
  104. double cdy = pc.Y - pdy;
  105. double cdxady = cdx * ady;
  106. double adxcdy = adx * cdy;
  107. double ocad = cdxady - adxcdy;
  108. // ocad = orient2d(pc,pa,pd);
  109. if (ocad <= 0) {
  110. return false;
  111. }
  112. return true;
  113. }
  114. /// Forumla to calculate signed area
  115. /// Positive if CCW
  116. /// Negative if CW
  117. /// 0 if collinear
  118. /// A[P1,P2,P3] = (x1*y2 - y1*x2) + (x2*y3 - y2*x3) + (x3*y1 - y3*x1)
  119. /// = (x1-x3)*(y2-y3) - (y1-y3)*(x2-x3)
  120. public static Orientation Orient2d( TriangulationPoint pa, TriangulationPoint pb, TriangulationPoint pc ) {
  121. double detleft = (pa.X - pc.X) * (pb.Y - pc.Y);
  122. double detright = (pa.Y - pc.Y) * (pb.X - pc.X);
  123. double val = detleft - detright;
  124. if (val > -EPSILON && val < EPSILON) {
  125. return Orientation.Collinear;
  126. } else if (val > 0) {
  127. return Orientation.CCW;
  128. }
  129. return Orientation.CW;
  130. }
  131. }
  132. }