Algorytm: przenieś źródłową polilinię na polilinię odniesienia (całkowicie lub częściowo)

10

W naszym systemie są wymagania, aby przenieść niektóre linie źródłowe (o niskiej precyzji) do linii odniesienia (o wysokiej precyzji). Poniższe zdjęcia przedstawiają normalne przypadki użycia. Czerwona to linia źródłowa, a niebieska to linia odniesienia.

Czerwona to linia źródłowa, a niebieska to linia odniesienia

W tym przypadku linia źródłowa zostałaby częściowo przesunięta, a wynik byłby taki, jak pokazuje zielona linia:

Przenieś wynik 1

Są sytuacje, że linia źródłowa musi zostać całkowicie przeniesiona.

Przykład 2

Wynik:

Przenieś wynik 2

Obecnie naszym rozwiązaniem jest rzutowanie punktu początkowego / końcowego linii źródłowej na linię odniesienia i odwrotnie, a następnie znalezienie rzutowanych punktów na linii źródłowej i linii odniesienia. Za pomocą tych rzutowanych punktów możemy wyodrębnić potrzebną część źródła i linii odniesienia, a następnie połączyć je w nową.

Działa to w większości przypadków, ale zdarzają się przypadki, że ta metoda nie działa. W szczególności, gdy jedna z linii ma kształt litery „C” lub punkt wierzchołkowy znajduje się bardzo blisko punktu końcowego. Następne dwa zdjęcia przedstawiają scenariusz.

C jak linia kształtu

Stosując mój algorytm, otrzymujemy wynik:

Wyniki

W pewnym sensie jest to zrozumiałe, ponieważ obecny algorytm po prostu wyszukuje rzutowane punkty i wydobywa linie.

Oczekiwaliśmy czegoś takiego:

oczekiwane rezultaty

Potrzebuję więc bardziej niezawodnego algorytmu, aby to zrobić, aby mógł on również obsługiwać specjalne przypadki, takie jak poprzedni. Próbowałem rzutować wszystkie punkty z linii na drugą i znaleźć dwa rzutowane punkty, które są najbliżej punktu początkowego / końcowego rzutowanej linii, ale nie miałem szczęścia. Nadal mogę znaleźć przypadki, które dają nieoczekiwane wyniki.

Czy ktoś wcześniej spotkał podobne problemy? Byłoby również świetnie, gdyby oprogramowanie lub biblioteka mogła wykonywać podobne zadania. Każda odpowiedź będzie mile widziana.

algorithm

— mfdev
źródło

1

Może pomoże ci, gdy spojrzysz, jak Topologia w ArcGIS sprawdza, czy obiekty są zbieżne: help.arcgis.com/en/arcgisdesktop/10.0/help/index.html#//… akapit „Przetwarzanie klastra”.

— Jens

Dziękuję za odpowiedź, @Jens. Ale obawiam się, że nie tego chcę.

— mfdev,

Czy te linie reprezentują sieć? Czy istnieją między nimi relacje topologiczne?

— Julien

Nie musi to być sieć i być może brak relacji topologicznych.

— mfdev,

4

Szacuję, że przypadki końcowe będą często wyjątkami, które nie mogą być programowane maszynowo. Pracowałem z podobnymi problemami i zawsze wymagały one pewnej ręcznej edycji. To, co musisz dostroić, to wyjątki tworzone przez sprawę i podawane w systemie zarządzania pracą użytkownikowi końcowemu.

— chwytak
źródło

Nieco podobny przykład można zobaczyć tutaj: vividsolutions.com/jcs JCS ma długą drogę do zautomatyzowania łączenia geometrii, ale obejmuje również manualną kontrolę jakości geometrii, których nie można całkowicie scalić. vividsolutions.com/... Jest zbudowany z niego i umożliwia kontrolę jakości oraz dodaje śledzenie problemów w przypadku trudnych geometrii.

— DPierce

1

Wszystkie rozwiązania topologiczne nie mogą być zautomatyzowane przez programowanie, aw dużych przedsiębiorstwach takie rozwiązania są opracowywane podobnie jak w przykładzie, ponieważ wypadanie konfuzji może być duże i cykliczne z uwagi na złożone geometrie transportowe o wysokiej szybkości zmian.

— lewis

2

Będziesz potrzebował tolerancji przyciągania i tolerancji skrętu dla tego algorytmu (zakładam, że masz już tolerancję przyciągania).

Rzutuj punkt czołowy z linii źródłowej na linię odniesienia. Przerwij linię odniesienia w tym rzutowanym punkcie.

Przejdź przez linię źródłową od punktu głównego do pierwszego wierzchołka, aby uzyskać kierunek podróży wzdłuż linii źródłowej. Przejdź przez każdą z dwóch linii odniesienia od rzutowanego punktu źródłowego do następnego wierzchołka. Jeśli kierunek podróży mieści się w granicach tolerancji skrętu w stosunku do kierunku jazdy od punktu głównego na linii źródłowej, zastosuj algorytm normalnie, ale tylko przy użyciu tego odcinka linii odniesienia. Jeśli algorytm dojdzie do końca linii źródłowej, gotowe. Jeśli nie, przerwij linię źródłową między przekształconym elementem a nietransformowanym elementem (który będzie zawierał punkt końcowy).

Teraz weź nietransformowany element i rzutuj punkt końcowy na oryginalną linię odniesienia. Wykonaj tę samą procedurę, jak poprzednio ... przejdź przez źródło od punktu końcowego do pierwszego wierzchołka, aby znaleźć kierunek podróży. Przerwij linię odniesienia w punkcie końcowym projektu i przejdź przez każdy z nich, aby sprawdzić, czy kierunek podróży od rzutowanego punktu końcowego mieści się w tolerancji skrętu. Jeśli tak, użyj tego fragmentu linii odniesienia, aby normalnie zastosować algorytm.

Pamiętaj, że w tym momencie używasz tylko nietransformowanego elementu, więc nie zachodzi na siebie transformacja wierzchołka.

Na koniec połącz dwa powstałe fragmenty linii, jeśli to konieczne: transformowany punkt główki z rzutowanego punktu główki do nietransformowanego punktu przerwania, a następnie na transformowanym punkcie końcowym fragmentu z nietransformowanego punktu przerwania do rzutowanego punktu końcowego.

— blord-castillo
źródło