Получение контура графика как многоугольника в PyGame

Question

У меня такое ощущение, что это невозможно (или, по крайней мере, очень сложно), но в настоящее время у меня есть сгенерированный граф, который выглядит примерно так (извините за мои страшные навыки рисования):

Теперь, я хотел бы быть в состоянии создать многоугольник контура, у меня есть coordnates всех узлов, но не пересечения. До сих пор я мог бы управлять алгоритмом подарочной упаковки, который дает больше грубых очертаний многоугольника, чем что-либо еще.

Есть ли у кого-нибудь идеи относительно того, как я могу это сделать?

(я в настоящее время с помощью PyGame)

Answer 1

Вы будете хотеть, чтобы выяснить, где Пересечения случаются, и сделать новые узлы там.

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

Тогда представьте себе, что вы идете по этому краю, держа левую руку на границе и правой руке. Начните ходить.

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

Все это базовая алгебра и тригонометрия средней школы, но это может быть немного грубо, если это ваш первый программный код из этого природа. Однако вы многое узнаете.