Как пересекаются два полигона?
Это кажется нетривиальным (об этом часто спрашивают на разных форумах), но мне это абсолютно необходимо как строительный блок для более сложного алгоритма.
вход: 2 полигона (A и B) в 2D, представленные в виде списка ребер[(x0, y0, x1, y2), ...]
каждый. Точки представлены парамиdouble
s. Я не знаю, даются ли они по часовой стрелке, против часовой стрелки или в каком-либо направлении. яделать Знайте, что они не обязательно выпуклые.
Выход: 3 многоугольника, представляющих A, B и пересекающийся многоугольник AB. Любой из которых может быть пустым (?) Многоугольником, например,null
.
Подсказка для оптимизации: Эти многоугольники представляют границы комнаты и пола. Таким образом, граница помещения обычно полностью пересекается с границей этажа, если только она не принадлежит другому этажу в той же плоскости (аааа!).
Я надеюсь, что кто-то уже сделал это в C # и позволит мне использовать их стратегию / код, поскольку то, что я нашел по этой проблеме, довольно устрашающе.
РЕДАКТИРОВАТЬТак что, похоже, я не совсем хулиган, потому что я чувствую слабость от такой возможности. Я хотел бы повторить желаемый результат здесь, так как это особый случай и может упростить вычисления:
Выход: Первый многоугольник минус все пересекающиеся биты, многоугольники пересечения (множественное число в порядке). Меня не очень интересует второй многоугольник, просто его пересечение с первым.
EDIT2: В настоящее время я используюGPC (General Polygon Clipper) библиотека, которая делает это действительно легко!