Изменение выпуклого корпуса для исключения нежелательных точек

В моей программе C# -Silverlight 3 у меня есть набор точек. Эти точки могут быть другого цвета, зеленого, красного или синего. Затем я создаю выпуклый корпус для разных точек: корпус для зеленого, корпус для красного и корпус для синего. Теперь может случиться так, что внутри корпуса каждого цвета есть точки другого цвета, например, красные точки в зеленом корпусе.Изменение выпуклого корпуса для исключения нежелательных точек

Существуют ли какие-либо алгоритмы для модификации корпуса, чтобы эти другие цвета были исключены из корпуса (что в этой точке не было бы выпуклостью)?

Заранее спасибо, Frank

источник

2009-10-20 Aaginor

Что вы имеете в виду, исключив? Вы хотите удалить эти баллы? Но при удалении некоторых точек вы можете «сломать» существующую выпуклую оболочку. И что будет, когда все точки зеленого выпуклого корпуса находятся внутри красной выпуклой оболочки? Более подробная информация необходима для ответа на этот вопрос. Конкретный пример также поможет. –

«Разбивая» выпуклый корпус, я имел в виду удаление 3 из 5 точек выпуклой оболочки, потому что эти 3 точки находились внутри другого корпуса. Затем вы получаете две оставшиеся точки, которые не могут быть выпуклой оболочкой. –

Перевести на классическую задачу коммивояжера.

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

EDIT

Нам нужно найти один путь невыхода над точками.

Найти одну точку в середине (artithmetic центр, например)
Вычислить угол к каждой точке (использование функции atan2)
Сортировка Это указывает на угол.

Сложность теперь N * Log (N)

источник

2009-10-20 13:42:36

Критически ответил, но правильный вывод: это проблема NP-hard. –

@Clint Tseng Теперь я думаю, что не обязательно, что как только вы ищете путь по этим исключенным точкам, чтобы быть самым страшным. Это просто корпус. Поиск непересекающегося пути по точкам в худшем случае N * log (N). –

С тех пор я нашел http://research.cs.queensu.ca/home/daver/Pubs/MyPDF/CCMSP_EadesRappaport.pdf что может вас заинтересовать. :) –

Изменение выпуклого корпуса для исключения нежелательных точек

ответ

Смежные вопросы