Как пересекаются два полигона?

Это кажется нетривиальным (об этом часто спрашивают на разных форумах), но мне это абсолютно необходимо как строительный блок для более сложного алгоритма.

вход: 2 полигона (A и B) в 2D, представленные в виде списка ребер[(x0, y0, x1, y2), ...] каждый. Точки представлены парамиdoubles. Я не знаю, даются ли они по часовой стрелке, против часовой стрелки или в каком-либо направлении. яделать Знайте, что они не обязательно выпуклые.

Выход: 3 многоугольника, представляющих A, B и пересекающийся многоугольник AB. Любой из которых может быть пустым (?) Многоугольником, например, ,null

Подсказка для оптимизации: Эти многоугольники представляют границы комнаты и пола. Таким образом, граница помещения обычно полностью пересекается с границей этажа, если только она не принадлежит другому этажу в той же плоскости (аааа!). I '

Я надеюсь, что кто-то уже сделал это в C # и позволит мне использовать их стратегию / код, поскольку то, что я нашел до сих пор по этой проблеме, довольно устрашающе.

РЕДАКТИРОВАТЬ: Так что, кажется, яЯ не совсем курица из-за ощущения слабости в перспективе сделать это. Я хотел бы повторить желаемый результат здесь, так как это особый случай и может упростить вычисления:

Выход: Первый многоугольник минус все пересекающиеся биты, многоугольники пересечения (множественное число в порядке). Я'Меня не очень интересует второй многоугольник, просто его пересечение с первым.

EDIT2: В настоящее время я используюGPC (General Polygon Clipper) библиотека, которая делает это действительно легко!

Ответы на вопрос(9)

Ваш ответ на вопрос