Zawieranie się krzywej w regionie

Witam,

Staram się znaleźć optymalizację dla pewnego algorytmu, a mianowicie mam obszar na którym są krzywe, zawierają one w sobie zbiór punktów (mówimy o 2D), również w tym obszarze znajdują się regiony (prostokąty), teraz muszę obliczyć czy dana krzywa znajduje się w jakimś regionie. Obecnie mam to w ten sposób że dla każdej krzywej sprawdzam każdy region obliczając na ile % znajduje się w nim. Problem pojawia się gdy zaczynamy mieć więcej regionów i krzywych (2 krzywe i 2 regiony to 4 iteracje, 4 i 4 to 16 itd) nie mogę wykluczyć że krzywa będzie w kilku regionach, również region może zawierać wiele krzywych. Szukam jakiegoś sposobu optymalizacji tego algorytmu. Jest jakiś mechanizm który byłby w stanie mi to uprościć?

a mianowicie mam obszar na którym są krzywe, zawierają one w sobie zbiór punktów (mówimy o 2D)

Krzywe coś zawierają? Krzywe nie mogą nic zawierać, mogą najwyżej przecinać obszary :P.

Jak są opisane te krzywe? Jako łamane składające sie z wielu odcinków? Krzywe Beziera? Wielomiany?
Co dokładnie chcesz wyliczyć? Dla każdego regionu (prostokąta), ile procent krzywej się z nim znajduje?
Czy chcesz tylko wiedzieć z jakimi regionami przecina się krzywa dla danej krzywej?
Czy dla danego regionu, jakie krzywe się z nim przecinają?
Czy ogólnie, mieć listę wszystkich przecięć krzywych i regionów?
Regiony są stałe podczas działania programu czy za każdym razem inne?
Krzywe są stałe czy inne za każdym razem?

Chyba tyle pytań na początek :P.

msm napisał(a):

Krzywe coś zawierają? Krzywe nie mogą nic zawierać, mogą najwyżej przecinać obszary :P.

Krzywe to zbiory punktów, więc zawierają te punkty.

Te zbiory są jednowymiarowe w sensie geometrycznym, no a regiony zwykle 2D, więc pewnie to ci się pomieszało:
dim region / dim krzywa = 0.

no może nieco odwrotne jest. :)

Aha! Mowa o krzywych skończonej długości... bowiem generalnie może być dim krzywa = dim region,
co już nijaki Sierpiński chyba wynalazł... potem Hilbert, no reszta świat (jak zwykle: jesteśmy tu liderami. :))

Daj obrazek z przykładowymi danymi. Wtedy dobierzemy metody optymalizacji.

Prawie na pewno trzeba po prostu zastosować jakiś szybki warunek konieczny do odfiltrowania par region-krzywa, by dopiero na tych parach wykonać bardziej skomplikowany test z warunkiem wystarczającym.
Warunek konieczny dobiera się do zestawu danych, by uzyskać najskuteczniejsze odfiltrowanie.
Bardzo ważne jet też jak masz opisane te dane.