Algoritme til at bestemme nærmeste punkt

Jeg vil foretrække et svar fra en person der selv har kendskab til denne slags algoritmer. Links til sider der forklarer hvordan det der spørges om gøres accepteres dog også, men i så fald forbeholder jeg mig retten til at nøjes med at give 30 point for svarer. Tak.

Hvis du ikke har nogen form for orden i punkterne så må du gå dem allesammen igennem og beregne afstanden i anden til hvert punkt.

Noget i retningen af:

mindist2=1000000000000
taetpunkt=null

for each [punktliste] as punkt
    dist2=(punkt.x-x)^2+(punkt.y-y)^2
    if dist2<mindist2 then
        mindist2=dist2
        taetpunkt=punkt
    end if
next

Og så ligger punktet i taetpunkt.

I avancerede fysiksimulationer vil man typisk inddele verden i sektorer og holde styr på hvilke objekter der befinder sig i hvilke sektorer, på den måde kan man skærer ned på antallet af nødvendige afstandsmålinger fordi man ved at objekter som befinder sig i sektorer langt fra hinanden også vil være langt fra hinanden.

Hvad hvis jeg har mulighed for at ordne listen af punkter på alle tænkelige måde på forhånd? Kan den enkelte søgning så gøres hurtigere?

Ja, den bedste mulighed jeg kan komme på er sektor inddeling, i stedet for at have punkterne på en liste skal du have dem i et todimensionelt array med lister, hvert element i dette array skal så representere et kvadratisk udsnit af det rum du arbejder i, og listen skal indeholde de punkter som findes i dette udsnit.

Når du søger det nærmeste punkt så starter du med at finde det nærmeste punkt indenfor den sektor hvor p befinder sig, hvis der er kortere til nogen af kanterne end til det fundne punkt så skal udvide søgefeltet i den retning, gentag indtil det fundne punkt er tættere på end samtlige usøgte sektorer.

Optimalt skal du nok have i gennemsnit omkring 10 punkter per sektor.

Jeg tror i stedet jeg vil gøre det på den måde at jeg for hvert punkt i listen bestemmer den cirkel indenfor hvilken punktet er det nærmeste i listen. Derefter vil jeg så bestemme det omskrevne rektangel for hver cirkel, og gemme disse i en database.

For et punkt p kan jeg så meget hurtigt finde de firkanter som p falder indenfor, hvilket vil begrænse listen af punkter betydeligt, og så undersøge hvilke af disse punkter p er tættest på.

"Jeg tror i stedet jeg vil gøre det på den måde at jeg for hvert punkt i listen bestemmer den cirkel indenfor hvilken punktet er det nærmeste i listen."
Den figur er ikke en cirkel

"For et punkt p kan jeg så meget hurtigt finde de firkanter som p falder indenfor, hvilket vil begrænse listen af punkter betydeligt, og så undersøge hvilke af disse punkter p er tættest på."
Uden nogen anden orden på punkterne vil du stadigvæk være tvunget til at gå dem alle igennem, jeg tror egentlig ikke at det bliver hurtigere end den først foreslåede formel. Afstand i anden formlen er meget simpel og kræver kun to input værdier, i modsætning til denne som kræver fire.

Hmm, okay. Jeg ville umiddelbart tro at kvadrering og kvadratrødder ville kræve betydeligt mere processorkraft end blot simple større-end-mindre-end operationer.

Jeg er ikke helt klar på hvordan man finder ud af hvilken sektor et givet punkt skulle falde indenfor?

Der er derfor du skal sammenligne afstand i anden, så slipper du for kvadratrødderne, dertil har jeg ikke tiltro til at du kan finde ud af at finde tættest-på-figurens omskrevne rektangel.

Hvor hurtigt skal det gå og hvor mange punkter har du? For hvis det er hurtigt nok så synes jeg bare at du skal holde dig til første forslag.

Der er i omegnen af 10.000 punkter på listen, og søgning udføres interaktivt - dvs. brugeren bestiller en søgning på nærmeste punkt og sidder så og venter på resultatet. Derfor skal det helst ske hurtigt nok til at det ikke virker overvældende langsommeligt for brugeren.

Hvis det kun er en søgning blandt 10000 punkter så bør det kunne lade sig gøre så hurtigt at brugeren ikke lægger mærke til det, også uden indeksering.