Tworzenie wielokątów Thiessena (Voronoi) przy użyciu linii (zamiast punktów) jako elementów wejściowych?

Mam zestaw cech linii wewnątrz określonej granicy wielokąta. Dla każdej linii chciałbym wygenerować wielokąt, w którym każdy możliwy punkt jest bliżej danej linii niż do dowolnej innej linii na warstwie. Robiłem to w przeszłości dla funkcji wprowadzania punktów przy użyciu triangulacji Delaunaya, ale jeśli istnieje podobny proces robienia tego z elementami linii, nie byłem w stanie go znaleźć.

ETA: Przyszło mi do głowy rozwiązanie Geogeeka, ale w prostszych sekcjach, w których linie wejściowe mają mniej wierzchołków, powstałe wielokąty zbliżają się zbyt blisko (nawet nakładając) na linię, której nie powinny. Tutaj czerwone linie to moje dane wejściowe, widać wierzchołki i generowane z nich wielokąty Thiessen.

Być może szybkim i (bardzo) brudnym rozwiązaniem może być przekonwertowanie każdej linii na duży zestaw równomiernie rozmieszczonych punktów (zamiast tylko wierzchołków linii), wygenerowanie z nich wielokątów Thiessena, a następnie rozpuszczenie ich na podstawie identyfikatora linii początkowej.

Aby zilustrować rozwiązanie do przetwarzania rastra / obrazu, zacząłem od opublikowanego obrazu. Ma znacznie niższą jakość niż oryginalne dane, z powodu nałożenia niebieskich kropek, szarych linii, kolorowych regionów i tekstu; i pogrubienie oryginalnych czerwonych linii. Jako takie stanowi wyzwanie: jednak nadal możemy uzyskać komórki Voronoi z wysoką dokładnością.

Wyodrębniłem widoczne części czerwonych liniowych elementów, odejmując zielony od czerwonego kanału, a następnie rozszerzając i erodując najjaśniejsze części o trzy piksele. Zostało to wykorzystane jako podstawa do obliczenia odległości euklidesowej:

i = Import["http://i.stack.imgur.com/y8xlS.png"];
{r, g, b} = ColorSeparate[i];
string = With[{n = 3}, Erosion[Dilation[Binarize[ImageSubtract[r, g]], n], n]];
ReliefPlot[Reverse@ImageData@DistanceTransform[ColorNegate[string]]]

(Cały pokazany tutaj kod to Mathematica 8.)

Identyfikacja widocznych „grzbietów” - które muszą obejmować wszystkie punkty oddzielające dwie sąsiednie komórki Voronoi - i ponowne połączenie ich z warstwą liniową zapewnia większość tego, co musimy zrobić:

ridges = Binarize[ColorNegate[
   LaplacianGaussianFilter[DistanceTransform[ColorNegate[string]], 2] // ImageAdjust], .65];
ColorCombine[{ridges, string}]

Czerwony pasek reprezentuje to, co mogłem zapisać na linii, a cyjanowy pasek pokazuje grzbiety w transformacji odległości. (Wciąż istnieje wiele śmieci z powodu przerw w samej oryginalnej linii.) Te grzbiety muszą zostać oczyszczone i zamknięte przez dalszą dylatację - zrobią to dwa piksele - a następnie możemy zidentyfikować połączone regiony określone przez oryginalne linie i grzbiety między nimi (niektóre z nich wymagają wyraźnej rekombinacji):

Dilation[MorphologicalComponents[
  ColorNegate[ImageAdd[ridges, Dilation[string, 2]]]] /. {2 -> 5, 8 -> 0, 4 -> 3} // Colorize, 2]

W efekcie udało się zidentyfikować pięć zorientowanych cech liniowych. Widzimy trzy oddzielne cechy liniowe emanujące z punktu przecięcia. Każda ma dwie strony. Uważałem prawą stronę dwóch najbardziej prawych elementów za identyczne, ale poza tym odróżniłem wszystko inne, podając pięć cech. Kolorowe obszary pokazują schemat Voronoi z tych pięciu cech.

Komenda alokacji euklidesowej oparta na warstwie, która rozróżnia trzy cechy liniowe (których nie miałam dostępna dla tej ilustracji) nie rozróżniałaby różnych boków każdej cechy liniowej, a zatem łączyłaby obszary zielony i pomarańczowy otaczające lewą linię ; podzieliłby skrajnie prawą cechę turkusowy na dwie części; i połączyłby te podzielone elementy z odpowiadającymi im beżowymi i karmazynowymi elementami po ich drugiej stronie.

Oczywiście to podejście rastrowe ma moc konstruowania teselacji dowolnych cech Voronoi - punktów, elementów liniowych, a nawet wielokątów, niezależnie od ich kształtów - i może odróżniać boki elementów liniowych.

Myślę że możesz:

• Konwertuj wierzchołki linii na punkty (punkty_wiersza).
• Twórz wielokąty voronoi za pomocą punktów (punkty_linii).
• Rozpuść uzyskane wielokąty za pomocą atrybutu id, który został zapisany z warstwy linii, lub poprzez połączenie przestrzenne z warstwą linii.

Mam nadzieję, że naprawdę zrozumiałem twoje pytanie. Jeśli nie, możesz podać rysunek wyjaśniający twoje potrzeby.