Czy istnieje algorytm znajdowania prawie wypukłego kadłuba przy danym kącie tolerancji?

Chciałbym wiedzieć, czy istnieje algorytm, który podał ustalone punkty o, a kąt oblicza wypukły kadłub, jeśli kąt wynosi $\alpha = 0$ a gdy $\alpha > 0$ oblicza obwiednię, która jest bliżej „obwodu” „.

$Ilustracja efektu wielkości $ \ alpha $$

A jeśli istnieje definicja nie przecinającego się obwodu zbioru punktów, w tym przypadku powstały wielokąt, gdy $\alpha$ jest duży.

Innym spojrzeniem na problem może być znalezienie algorytmu, który można sparametryzować w celu znalezienia dla minimalnego rozwiązania obwodu (wypukły kadłub) i dla (znormalizowanego) polilinię minimalnego obszaru obejmującą wszystkie punkty. $\alpha = 0$ $\alpha = 1$

algorithms computational-geometry

— naufraghi
źródło

Czy zastanawiałeś się nad koncepcją mocno wypukłych zbiorów ?

— Deathbreath

Czy możesz wyjaśnić cel ? Do czego to służy?

α

$\alpha$

— Paweł

Czy byłoby dozwolone zaproponować algorytm, który będzie działał w miarę wzrostu ? A może spodziewałeś się, że zwiększenie zmniejszy „oczekiwaną” złożoność?

α

$\alpha$

α

$\alpha$

— hardmath

Zamierzałem to, ponieważ kąt, pod jakim algorytm może się odsunąć od wypukłego kadłuba. I nie, nie sądzę, że zmniejszy to złożoność.

— naufraghi

Odpowiedzi:

Możesz zbadać tak zwany kadłub alfa , na przykład: pakiet CRAN , Wikipedia na temat kształtów alfa :
wprowadź opis zdjęcia tutaj
_{[Zdjęcie z tego linku ]}

Kadłub alfa ma bardzo ładne właściwości geometryczne i został gruntownie zbadany, ale nadal może nie spełniać twoich celów.

— Joseph O'Rourke
źródło

Dzięki temu kształty alfa są bardzo interesujące, mają nadzbiór właściwości, których szukałem (interesuje mnie tylko jedna koperta), a implementacja nie jest porównywalna z tą wypukłą. Poczekam jeszcze trochę, jeśli ktoś może zaproponować coś prostszego, jeśli nie, zaakceptuję tę odpowiedź.

— naufraghi

Może to być zbyt proste, aby być interesujące, ale jednym z podejść byłoby znalezienie wypukłego kadłuba i użycie wielokątnego segmentu granicznego segment po segmencie, aby zlokalizować dodatkowe punkty, które spełniają kryterium trójkąt, zatrzymując się po ukończeniu pełnego obwodu bez dodając kolejne wierzchołki. Aby osiągnąć „zbieżność”, może być wymagane więcej niż jedno przejście. $\alpha$

-angle kryterium może być sformułowana dla danej pary kolejnych wierzchołków przyściennej leży w obszarze między kołowego łuku i jego cięciwy = segmentu ograniczającego. Można to nazwać okrągłym segmentem. $\alpha$

Chcielibyśmy zastanowić się nad strukturą danych, która ułatwiłaby znalezienie określonych punktów. Jednym z pomysłów byłoby obliczenie obwiedni dla każdego segmentu i porównanie go z posortowaną listą punktów.

— matematyka
źródło