Widziałem dwa sposoby rozwiązania tego problemu. Jeden jest dość prosty. Drugi wymaga dużej ilości danych pomocniczych.
Prosty algorytm opierałby się raczej na wypukłych kadłubach niż na wielokątach voronoi. Skonstruuj wypukły kadłub wektorowych punktów końcowych i wierzchołków dla odcinków ulic, które mieszczą się w odcięciach czasu jazdy. Następnie użyj tego wypukłego kadłuba, aby wybrać połączone sieci wewnątrz wypukłego kadłuba, które są poza czasem odcięcia napędu. Są to kieszenie w twoim obszarze ogólnym, które nie są osiągalne w czasie jazdy (np. Odcięcia w jedną stronę, złożone podziały wewnętrzne itp.). Zbuduj wypukły kadłub dla każdej z tych izolowanych sieci kieszeniowych i użyj tych kadłubów jako wewnętrznych pierścieni do oryginalnego wypukłego kadłuba.
Zauważ, że ten konkretny algorytm staje się znacznie bardziej złożony, jeśli używasz prawdziwych krzywych, ponieważ prawdziwa krzywa może spaść poza wypukły kadłub zbudowany z wierzchołków.
W przypadku algorytmu obsługującego dane stosuje się podział gruntów. Paczki są najbardziej oczywistym podziałem gruntów, ale niekoniecznie skuteczne w każdym scenariuszu. W zależności od sieci rozwiązań każda paczka jest ustalana jako dostępna lub niedostępna w sieci rozwiązań. Jeśli paczka jest dostępna, umieszczasz ją w obszarze zlewni. Jeśli nie, na zewnątrz. Na obszarze z rozwiniętymi planimetrami może to być dość łatwe; uwzględnij podjazdy i drogi prywatne jako elementy sieci drogowej. Jeśli partycja dotknie sieci rozwiązania, jest dostępna. Jedną z trudności tutaj jest zapewnienie, że wszystkie potencjalnie dostępne partycje dotykają sieci. Na przykład, jeśli masz wewnętrzną wspólną działkę naziemną w podrejonie, musisz połączyć ją w jakiś sposób z paczką lub paczkami, które dotykają sieci. Ale możesz mieć regiony, takie jak wewnętrzne szlaki w dużym parku, które są w ogóle niedostępne, a po prostu nie dotykają sieci. Tak jak powiedziałem, dużo danych pomocniczych, ale bardzo skuteczny algorytm, kiedy już masz dane.