4430
правок
Разработка геометрических алгоритмов: различия между версиями
Материал из WEGA
Разработка геометрических алгоритмов (посмотреть исходный код)
Версия от 12:56, 1 февраля 2019
, 1 февраля 2019→Открытые вопросы
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 59: | Строка 59: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Несмотря на значительный прогресс в области сертифицированной реализации эффективных геометрических алгоритмов, существующие теоретические алгоритмические решения для многих задач по-прежнему требуют адаптации или редизайна, чтобы быть достаточно полезными на практике. Одним из примеров ситуации, когда прогресс может иметь значительный резонанс, могла бы стать разработка эффективных декомпозиций для криволинейных геометрических объектов (например, расположений) на плоскости и в более высоких размерностях. Как упоминалось ранее, подходящие способы декомпозиции оказывают значительное влияние на практическую эффективность геометрических алгоритмов. | |||
Сертифицированные геометрические вычисления с фиксированной точностью уступают традиционным точным вычислениям в отношении доступных отказоустойчивых программных продуктов, и продвижение в этом направлении представляется серьезной проблемой. К примеру, создание сертифицированного аналога CGAL с плавающей запятой является крайне желанной (и при этом весьма сложной) целью. | |||
Еще одним инструментом, нехватка которого серьезно ощутима, является непротиворечивое и эффективное округление геометрических объектов. Как уже упоминалось ранее, существует достаточно удовлетворительное решение для многоугольных объектов на плоскости. Однако пока не разработано хороших техник для криволинейных объектов на плоскости и для объектов более высоких размерностей (как линейных, так и криволинейных). | |||
== Ссылка на код == | |||
http://www.cgal.org | |||
== См. также == | |||
* [[LEDA: Библиотека эффективных алгоритмов]] | |||
* [[Отказоустойчивые геометрические вычисления]] | |||
== Литература == | |||
Статьи по данной теме публиковали такие конференции, как симпозиум ACM по вычислительной геометрии (ACM Symposium on Computational Geometry, SoCG), семинар по разработке и экспериментальному выполнению алгоритмов (Workshop on Algorithm Engineering and Experiments, ALENEX), секция разработки и применения приложений Европейского симпозиума по алгоритмам (Engineering and Applications Track of the European Symposium on Algorithms, ESA), его предшественник и семинар по экспериментальным алгоритмам (Workshop on Experimental Algorithms, WEA). Материалы по теме можно найти в следующих журналах: «Журнал ACM по экспериментальной алгоритмике» (ACM Journal on Experimental Algorithmics), «Вычислительная геометрия: теория и применение» (Computational Geometry: Theory and Applications) и «Международный журнал по вычислительной геометрии и ее применению» (International Journal of Computational Geometry and Applications). Широкий спектр важных аспектов геометрических вычислений получил освещение в сборнике под редакцией Буассона и Тейо [6] под названием «Эффективная вычислительная геометрия для кривых и поверхностей». | |||
1. Сайт проекта CGAL. http://www.cgal.org/. По состоянию на 6 апреля 2008 г. | |||
2. Сайт библиотеки CORE. http://www.cs.nyu.edu/exact/core/. По состоянию на 6 апреля 2008 г. | |||
3. Сайт GMP. http://gmplib.org/. По состоянию на 6 апреля 2008 г. | |||
4. Agarwal, P.K., Flato, E., Halperin, D.: Polygon decomposition for efficient construction of Minkowski sums. Comput. Geom. Theor.Appl. 21 (1-2), 39-61 (2002) | |||
5. Barber, C.B., Dobkin, D.P., Huhdanpaa, H.T.: Imprecision in QHULL. http://www.qhull.org/html/qh-impre.htm. Accessed 6 Apr 2008 | |||
6. Boissonnat, J.-D., Teillaud, M. (eds.) Effective Computational Geometry for Curves and Surfaces. Springer, Berlin (2006) | |||
7. Boissonat, J.-D., Devillers, O., Pion, S., Teillaud, M., Yvinec, M.: Triangulations in CGAL Comput. Geom. Theor. Appl. 22(1-3), 5-19(2002) | |||
8. Fabri, A., Giezeman, G.-J., Kettner, L., Schirra, S., Schonherr, S.: On the design of CGAL a computational geometry algorithms library. Softw. Pract. Experience 30(11), 1167-1202 (2000) | |||
9. Halperin, D., Leiserowitz, E.: Controlled perturbation for arrangements of circles. Int. J. Comput. Geom. Appl. 14(4-5), 277-310(2004) | |||
10. Haran, I., Halperin, D.: An experimental study of point location in general planar arrangements. In: Proceedings of 8th Workshop on Algorithm Engineering and Experiments, pp. 16-25 (2006) | |||
11. Held, M.: VRONI: An engineering approach to the reliable and efficient computation of Voronoi diagrams of points and line segments. Comput. Geom. Theor. Appl. 18(2), 95-123 (2001) | |||
12. Joswig, M.: Software. In: Goodman, J.E., O'Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, 2nd edn., chap. 64, pp. 1415-1433. Chapman & Hall/CRC, Boca Raton (2004) | |||
13. Kettner, L, Naher, S.: Two computational geometry libraries: LEDA and CGAL. In: Goodman, J.E., O'Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, Chapter 65, pp. 1435-1463, 2nd edn. Chapman & Hall/CRC, Boca Raton (2004) | |||
14. Mehlhorn, K., Naher, S.: LEDA: A Platform for Combinatorial and Geometric Computing. Cambridge University Press, Cambridge (2000) | |||
15. Wein, R., Fogel, E., Zukerman, B., Halperin, D.: Advanced programming techniques applied to CGAL'S arrangement package. Comput. Geom. Theor. Appl. 36(1-2), 37-63 (2007) | |||
