Как сгенерировать случайный многоугольник без взаимопересечений?

Хороший способ, гарантирует отсутствие оторванных островов, т.к. строим от предыдущего.
Список всегда будет содержать внешний контур.
При добавлении точки, получившийся треугольник может содержать в себе мЕньший предыдущий (или несколько). Рёбра не пересекутся. Но это простое для проверки условие.

Сергей Соколов, тогда нужно будет ещё проверять, чтобы медиана не пересекала других рёбер. Мне кажется, хорошим вариантом будет строить равнобедренный треугольник.
Ещё остаётся случай, если новый будет меньше предыдущего и целиком лежать в нём.

Для каждого ребра стоит хранить направление от центра треугольника, в котором оно было добавлено. Это избавит от проверок на генерацию в "неправильную" сторону.

Можно усложнить алгоритм, чтобы получить многоугольник, больше напоминающий сеть пещер. Для этого, кроме одного списка с рёбрами всего многоугольника нужно завести несколько списков с "генерирующими" рёбрами. После добавления очередного трегольника, в генерирующий список заносится только одно случайное ребро из двух и увеличивается счётчик для этого списка. После достижения какого-либо количества сгенерированных с помощью этого списка треугольников, на очередной итерации заводится ещё один список, в который кладётся второе ребро, т.е. получится "развилка".

unepic, генерация в «неправильную» сторону допустима, наверное: почему бы не «выедать» из площади существующего треугольника мЕньший треугольник?

не понял пункт 3

накладываете ограничения на соседние многоугольники

Сергей Соколов, например, что бы не пересекались соседние комнаты, если они разной формы. Или что бы не повторялись.