Kortste afstand tussen twee lijnstukken

[Bascy]

Hallo,

ik ben geen wiskundige, maar een software ontwikkelaar met een meetkunde probleem...

Voor een project moeten we van alle lijnstukken uit de ene verzameling, uitvinden welk lijnstuk uit een andere verzameling de dichtsbijzijnde is. De lijnstukken zijn gedefinieerd door begin en eindpunten in 2 dimensies.

Kan iemand ons op weg helpen hoe dit probleem op te lossen?

[jhnbk]

wat bedoel je met de dichtsbijzijnde

- van eindpunt naar eindpunt?

- analoog voor beginpunt

- of nog iets anders?

post ook eens een stuk van je code, of hoe je het zoekt aan te pakken, dat is gemakkelijker om je te helpen

[Bascy]

Ik zal de achtergrond van het probleem even vertellen, dat maakt het misschien duidelijker.

Het gaat om een lijst met pijplijnsecties en een lijst met straatsecties, we moeten uitzoeken welk pijpsectie bij welke straatsectie hoort.

Een idee is om van elk pijpsectie de "gemiddelde" afstand naar een straatsectie te berekenen en de straatsectie met de kleinste gemiddelde afstand aan te wijzen als "behorende bij" de pijplijnsectie. Hier zit natuurlijk altijd een foutmarge in, maar die wordt voor lief genomen (het gaat om 100-duizenden pijp en straatsecties).

Werpt dit iets meer licht op de zaak?

[jhnbk]

je kan uiteraard een formule zoeken voor de gemiddelde afstand tussen 2 lijnstukken via integraalrekening, maar dat ga je denk ik niet vinden.

Ik zou gaan voor de middens van de lijnstukken.

Gewoon in een lus, per straat alle pijplijnsecties laten doorlopen

het midden van een lijnstuk van

\((x_a,y_a)\)

naar

\((x_b,y_b)\)

is dan

\( \left ( \frac{ x_a+x_b}{2 } , \frac{y_a+y_b }{2 } \right ) \)

[Bascy]

Bedankt voor je suggestie, we zullen hier zeker naar kijken. We hebben al eens een module gemaakt die de dichtsbijzijnde lijn bij een punt zoekt, dus die kunnen we dan mooi hergebruiken.

Missschien zijn er nog andere ideeen over hoe we dit aan kunnen pakken?

[jhnbk]

niet dat ik weet, maar welke taal gebruik je?

[Bascy]

Delphi,

we hebben onze lat inmiddels een stukje hoger gelegd, want we willen het voor n-dimensies kunnen oplossen

We zijn nu driftig aan het zoeken, oa op hier en hier

misschien dat we daarmee het probleem kunnen oplossen

De vraag is eigenlijk op dit punt of we de algopritmes uit de bovenstaande links ongestraft kunnen toepassen met vectors in n-dimensies ?

kan iemand daar iets zinnigs over zeggen?

[jhnbk]

dat weet ik niet, maar wat heeft het voor nut om dit voor n-D te doen