Определить точку пересечения между линией и контуром, представленным списком точек

Question

Данные: Список точек, представляющих замкнутый контур Задача: выбрать случайную точку на контуре и снять лучи внутри контура и определить точку, в которой луч пересекает контур. Это необходимо реализовать с помощью некоторого языка программирования.

Подход, который я имею в виду, заключается в том, чтобы интерполировать точки и решить уравнения линии и кривой. Есть ли в C++ библиотека, которая может достичь этой или любой более простой математики, кроме интерполяции, или любых намеков.

Answer 1

Я бы рассматривал контур как набор сегментов линии и выполнял тест пересечения между каждым отрезком линии и вашим лучом. Geometric tools имеет очень обширную библиотеку тестов пересечений, и я успешно использовал ее для многих приложений.