Площадь самопересекающегося многоугольника

Вычисление площади простого неправильногомногоугольника тривиально. Однако рассмотрим самопересекающийся многоугольник ABCDEF, показанный слева внизу:

Если мы используем приведенную выше формулу со ссылкой для обхода точек в порядке многоугольника, мы получим площадь, равную 0. (Площадь «по часовой стрелке» отменяет из области «против часовой стрелки».)

Однако, если мы отсортируем точки радиально вокруг центраи вычислим площадь, мы получим неправильную площадь многоугольника ABEDCF справа вверху.

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

Этот вопрос возник при исследовании пограничных случаев для моего решения этот вопрос.

Определение области

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