Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Tính toán diện tích chồng lấp của hai ellipse
Tóm tắt
Chúng tôi trình bày một phương pháp để tìm diện tích chồng lấp giữa hai ellipse mà không phụ thuộc vào các đường cong trung gian. Công thức Gauss-Green được sử dụng để xác định diện tích đoạn giữa hai điểm trên một ellipse. Diện tích chồng lấp giữa hai ellipse được tính bằng cách kết hợp các diện tích của các đoạn thích hợp và các đa giác trong mỗi ellipse. Đối với bốn trong mười định hướng có thể của hai ellipse, phương pháp yêu cầu xác định số học các điểm giao nhau ngang. Các điểm giao nhau xấp xỉ có thể được xác định bằng cách giải đồng thời hai phương trình ellipse ngầm. Các phương pháp thay thế để tìm các điểm giao nhau ngang có sẵn bằng cách sử dụng các công cụ từ hình học đại số, chẳng hạn như giải quyết một bài toán Eigen liên quan đến ma trận đồng hành của hai đường cong ellipse ngầm. Các triển khai bằng C của một số lựa chọn thuật toán được phân tích về độ chính xác, độ tinh vi và tính ổn định với nhiều ellipse đầu vào khác nhau.
Từ khóa
#ellipse #diện tích chồng lấp #công thức Gauss-Green #hình học đại sốTài liệu tham khảo
Böröczky, K., Reitzner, M.: Approximation of smooth convex bodies by random circumscribed polytopes. Ann. Appl. Prob. 14(1), 239–273 (2004)
Boost The Boost. Polygon Library http://www.boost.org/doc/libs/1_54_0/libs/polygon/doc/index.htm
Busé, L., Khalil, H., Mourrain, B.: Resultant-based methods for plane curves intersection problems. Lecture notes in computer science, pp. 75–92 (2005)
Chraibi, M., Seyfried, A., Schadschneider, A.: Generalized centrifugal force model for pedestrian dynamics. Phys. Rev. E. 82(4), 046111 (2010)
Eberly, D.: The area of intersecting ellipses. Accessed at http://www.geometrictools.com/Documentation/AreaIntersectingEllipses.pdf (2010)
Elkadi, M., Mourrain, B.: Symbolic-numeric tools for solving polynomial equations and applications. In: Dickenstein, A., Emiris, I. (eds.) Solving Polynomial Equations: Foundations, Algorithms, and Applications, vol. 14 of Algorithms and Computation in Mathematics, pp. 125–168. Springer, Berlin (2005)
Etayo, F., Gonzalez-Vega, L., Del Rio, N.: A new approach to characterizing the relative position of two ellipses depending on one parameter. Comput. Aided Geom. Des. 23(4), 324–350 (2006)
Fu, P., Walton, O.R., Harvey, J.T.: Polyarc discrete element for efficiently simulating arbitrarily shaped 2D particles. Int. J. Numer. Methods Eng. 89(5), 599–617 (2012)
Gruber, P.M.: Asymptotic estimates for best and stepwise approximation of convex bodies IV. Forum Math. 10, 665–686 (1998)
Han, K., Feng, Y.T., Owen, D.R.J.: Polygon-based contact resolution for superquadrics. Int. J. Numer. Methods Eng. 66, 485–501 (2006)
Ludwig, M.: Asymptotic approximation of convex curves. Arch. Math. 63, 377–384 (1994)
Manocha, D., Demmel, J.: Algorithms for intersecting parametric and algebraic curves I: simple intersections. ACM Transactions on Graphics (TOG) 13(1), 73–100 (1994)
Mcnamee, J.M.: A 2002 update of the supplementary bibliography on roots of polynomials. J. Comput. Appl. Math. 142(2), 433–434 (2002)
Nonweiler, T.R.F.: CACM Algorithm 326: Roots of low order polynomials. Communications of the ACM. 11, 4, 269–270. Translated into C and programmed by M. Dow, ANUSF, Australian National University, Canberra, Australia. Accessed at http://www.netlib.org/toms/326 (1968)
Pan, V.Y.: Univariate polynomials: nearly optimal algorithms for numerical factorization and root-finding. J. Symb. Comput. 00, 1–33 (2002)
Pan, V.Y.: Solving a polynomial equation: some history and recent progress. SIAM Rev. 39(2), 187–220 (1997)
Press, W.H., Flannery, B.P., Teukolsky, S.A., Vetterling, W.T.: Numerical Recipes: the Art of Scientific Computing. Cambridge University Press, New York (1992)
Steiner, A., Buckley, A.: GSL Extension for solving quartic polynomials with gsl\_poly\_complex\_solve. Accessed at http://www.network-theory.co.uk/download/gslextras/Quartic/ (2004)
Zeng, Z.: Algorithm 835. ACM Trans. Math. Softw. 30(2), 218–236 (2004)