Вроде, не сложная задача).

Если заданы точки p1,p2,p3,p4,p5,p6,p4,p7,p8,p3,p9,p1 то контуры будут следующими

p1,p2,(p3,(p4,p5,p6,p4),p7,p8,p3), p9,p1

p4,p5,p6,p4
p3,p4,p7,p8,p3
p1,p2,p3,p9,p1

То есть повторяющиеся точки - начало нового контура или линии между контурами.
Расставляем "скобки". Всё что внутри извлекаем, оставляя только одну точку.
В результате две точки - линия между контурами, больше двух - контур.

А где (злополучная) p1 - неизвестно. Напр она может принадлежать контуру дырки...

Я тоже так думал 

Вы исходите из предположения что (стартовая) p1 - точка "внешнего" контура, тогда последующие совпадающие точки обозначат дырки. Но такое предположение часто оказывается неверным, т.е. Вы можете просто "начвть с дырки"

Триангулировать "комплексные полигоны", т.е. с числом вертексов >= 5, задаются такой полилинией 

Спасибо за ссылку, но что такое "spatial indexing", и чему это посвящено - хз

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

Ну в как Вы триангулируете полигон на картинке выше ? Здесь как раз надо "искать готовые", велики типа "откусывания ушей" уже не катят. Я использую Шевчука (Джонатана Ричарда), когда-то смотрел и другие, но они тоже требуют указания "дырок".

Так контура-то надо иметь, т.е. сначала выделить. Вы предложили простой и естественный способ - ищем контур по совпадению точек. Каждая пара - дырка, они могут быть вложены друг в друга. То что осталось - внешний контур.

И это будет работать если напр первая точка - правая нижняя на картинке. А вот если первая первая = верхней, то может и нет, внешний контур будет найден как дырка, а остаток (верхняя дырка) будет внешним. Анализировать все найденные контура чтобы убедиться какой же внешний - вероятно возможное решение, но выглядит длинным и мутным. Нет ли чего  попроще/получше ?

Насколько помню, и там контура дырок надо задавать, внешний CCW, дырки CW (или наоборот). Указание дырок так или иначе неизбежно, иначе это могут быть просто ребра.

Как я сделал. Собсно все как Вы и сказали, только еще выбор стартовой точки:

1) Нахожу 4 точки max/min X/Y. Они точно лежат на внешнем контуре. Убираю повторы, остается минимум 2 точки

2) Каждую из найденных проверяю - есть ли совпадающая с ней. Если нет, точка сразу считается стартовой. Иначе из 2 возможных контуров выбирается тот на котором лежит  вторя внешняя точка. Ну и совпадение для стартовой дыркой не считаем - это внешний контур

Правда это не учитывает 3 и более совпадений (для одной точки), на это забил, не хватило терпения 

Кстати в триангуляторе Шевчука дырка задается одной точкой, поэтому потом еще требуется найти точку внутри дырки. Для этого привлекается пресловутый дуст - объективно страшно избыточное решение