Выпуклый корпус Недоразумение?

Question

я написал реализацию алгоритма сканирования выпуклой оболочки Грэма и для тестовых данных я использовал точек

[(2.0,2.0),(4.0,2.0),(0.5,2.5),(3.0,3.5),(1.0,4.0),(0.0,4.0),(1.0,1.0),(3.0,2.5),(4.0,4.0),(3.5,1.5),(0.5,1.0)] 

Согласно моей программе выпуклой оболочкой является

[(0.0,4.0),(1.0,4.0),(4.0,4.0),(3.0,2.5),(4.0,2.0),(3.5,1.5),(1.0,1.0),(0.5,1.0)] 

Однако, я ожидал, что выпуклую оболочка для быть

Я попробовал мой набор точек с https://github.com/shadwstalkr/GrahamScanDemo/, а также, и это дает такое же решение, как хорошо. После долгих жалоб и ворчаний я читал в википедии, что «Объект выпуклый, если для каждой пары точек внутри объекта каждая точка на отрезке прямой, которая их соединяет, также находится внутри объекта».

После извлечения моих очков и корпуса. Похоже, что моя программа создала объект внутри этого определения, однако не означает ли это, что просто сортировка по углу даст выпуклый корпус, как и без каких-либо точек в корпусе?

Неужели я не понимаю, что такое выпуклый корпус, и я свяжусь с тем, чтобы решить другую проблему, или как моя реализация, так и неверная интерпретация?

Answer 1

С помощью wolframalphaPolygon{} команды вы можете увидеть разницу между вашим решением и реальным:
ваш:

реально:

Таким образом, ваш полигон ни convex, так как по определению выпуклых poly ALL пар po ints внутри многоугольника должен формировать сегмент линии, который содержит точки ТОЛЬКО от этого многоугольника. И, например, строка от {4,4} до {4,2} формирует сегмент, который выходит из полигона. Второй - ваш многоугольник не является convex hull, потому что резина не может сгибаться внутрь полигона до точки {3., 2.5}. Итак, вам нужно исправить свой алго.

Answer 2

Ваше интуитивно понятное решение является правильным, за исключением того, что у него слишком много точек: (1, 4). Выпуклая оболочка обычно определяется как минимальный выпуклый набор. В том числе (1, 4), множество выпуклое, но оно не является минимальным, потому что (1, 4) находится на линии между двумя другими точками в наборе: (0,4) и (4,4). Если вы удалите (1, 4), форма воображаемой резиновой ленты не изменится.

Похоже, в вашей программе есть ошибка.