---

hejsa
Sidder lige og roder med lidt beregninger hvor jeg skal finde et
centrum i området som dannes når cirkler overlapper hinanden.
eksempel:
http://www.cs.aau.dk/~kim/rings.png

På billedet er det det mørkeste område jeg vil finde centrum af.

Der kan godt være flere (men ikke færre) end 4 cirkler og de er ikke
placeret efter noget bestemt mønster (dog ligger de med sikkerhed ikke
på f.eks. linje).

Eksemplet viser kun en cirkel om hvert cirkel-center, men principielt er
der cirkler for hver x væk fra centrum (x er en konstant afstand som
er ens for alle cirkler).

Bare lige for at give det et ekstra twist, så skal jeg kunne beregne
centrum for alle de "celler" som dannes mellem cirklerne.

Mit umiddelbare gæt var noget med at lave en polygon mellem
skærringspunkterne mellem cirklerne og så finde centrum i denne, men
allerede der kom jeg til kort.

Der er garanteret en smart måde at beregne det på, men jeg kan bare
ikke lige gennemskue hvordan.

nogen der kan give mig et hint eller en reference til hvem der har
rodet med den slags.

MVH
Kim

---

Scripsit Kim Schulz <kim@schulz.dk>

> På billedet er det det mørkeste område jeg vil finde centrum af.

Du bliver nødt til at definere nøjere hvad du mener med "centrum" i
denne sammenhæng.

--
Henning Makholm "Nu kommer han. Kan du ikke høre knallerten?"

---

Scripsit Kim Schulz <kim@schulz.dk>
> Henning Makholm <henning@makholm.net> wrote:

>> Du bliver nødt til at definere nøjere hvad du mener med "centrum" i
>> denne sammenhæng.

> Et approximeret centrum imellem siderne af cellen.

Det er en _anvendelse_ af ordet "centrum", ikke en definition.

--
Henning Makholm "There is a danger that curious users may
occasionally unplug their fiber connector and look
directly into it to watch the bits go by at 100 Mbps."

---

Scripsit Kim Schulz <kim@schulz.dk>

> afgørende er det at punktet ligger inde i cellen.

Hvis det er din eneste betingelse, så tag fx det aritmetiske
gennemsnit af cellens hjørnepunkter.

--
Henning Makholm "What a hideous colour khaki is."

---

"Henning Makholm" <henning@makholm.net> skrev i en meddelelse
news:871wxn4dsr.fsf@kreon.lan.henning.makholm.net...
> Scripsit Kim Schulz <kim@schulz.dk>
>
>> afgørende er det at punktet ligger inde i cellen.
>
> Hvis det er din eneste betingelse, så tag fx det aritmetiske
> gennemsnit af cellens hjørnepunkter.

Det letter selvfølgelig beregningerne en del, men et mere korrekt valg vil -
i mine øjne - være tyngdepunktet. Altså gennemsnittet af samtlige "punkter"
i celleområdet.

/Kenneth

---

Kenneth Brun Nielsen skrev:

> Det letter selvfølgelig beregningerne en del, men et mere korrekt valg vil -
> i mine øjne - være tyngdepunktet.

"Korrekt"? Hvis han bare skal bruge et punkt 'til at tage fat i',
så er den hurtige beregning bedst.

--
Bertel
http://bertel.lundhansen.dk/      http://fiduso.dk/

---

"Bertel Lund Hansen" <nospamfilius@lundhansen.dk> skrev i en meddelelse
news:44056678$0$4820$ba624c82@nntp02.dk.telia.net...
> Kenneth Brun Nielsen skrev:
>
>> Det letter selvfølgelig beregningerne en del, men et mere korrekt valg
>> vil -
>> i mine øjne - være tyngdepunktet.
>
> "Korrekt"? Hvis han bare skal bruge et punkt 'til at tage fat i',
> så er den hurtige beregning bedst.

"Bedst"? Som jeg forstår de tidligere indlæg, er det ikke blot et punkt
at 'tage fat i', men et . Jeg holder stadig på at
tyngdepunktet er den bedste repræsentation. Nøjagtig som man i mekanikken
benytter tyngdepunktet til at repræsentere legemer med en endelig
udstrækning. Men det endelig valg bør naturligvis skele til såvel
kompleksiteten af beregningerne som den repræsentative værdi af punktet. Man
skal ikke skyde gråspurve med kanoner...

/Kenneth

---

Scripsit Kim Schulz <kim@schulz.dk>

> men vil du så gøre
> ((x1+x2+x3...+xn)/n,(y1+y2+y3...+yn)/n)
> eller hvad?

Ja.

--
Henning Makholm "There were few families that didn't have at least
one hopeful who, from Reading Day on, was the great
hope because of the way he handled his trisyllabics."

---

Scripsit Kim Schulz <kim@schulz.dk>

> Jeg kan ikke helt se at det kan garantere at centrum ligger inde i
> cellen.
> eks. punkterne her forbundet i den rækkefølge:
> (1,1) (2,6) (2,2) (6,2)

Det giver jo en ikke-konveks figur. Hvordan opnår du den som
fællesmængden af en række cirkelskiver?

--
Henning Makholm "Dylle skød en stegepande."

---

"Kenneth Brun Nielsen" <news@_FJERNES_brun.dk> writes:

> "Henning Makholm" <henning@makholm.net> skrev i en meddelelse
> news:871wxn4dsr.fsf@kreon.lan.henning.makholm.net...
>> Scripsit Kim Schulz <kim@schulz.dk>
>>
>>> afgørende er det at punktet ligger inde i cellen.
>>
>> Hvis det er din eneste betingelse, så tag fx det aritmetiske
>> gennemsnit af cellens hjørnepunkter.
>
> Det letter selvfølgelig beregningerne en del, men et mere korrekt valg vil -
> i mine øjne - være tyngdepunktet. Altså gennemsnittet af samtlige "punkter"
> i celleområdet.

Hvad der er "bedst" afhænger af hvad der menes med at "repræsentere
cellen". Tyngdepunktet er et godt gæt, men det bliver aldrig mere end
det, hvis vi ikke ved hvad det skal bruges til mere præcist.

Et andet valg kunne være det punkt der har størst afstand til kanten
(hvor "afstand til kantent" er minimum af afstand til punkterne på
kanten) - eller et af disse hvis der er flere. Tyngdepunktet har
fordelen af at være entydigt.

/L
--
Lasse Reichstein Nielsen - lrn@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'

---

On Tue, 28 Feb 2006 16:33:34 +0100
Henning Makholm <henning@makholm.net> wrote:

> Scripsit Kim Schulz <kim@schulz.dk>
>
> > På billedet er det det mørkeste område jeg vil finde centrum af.
>
> Du bliver nødt til at definere nøjere hvad du mener med "centrum" i
> denne sammenhæng.
>

Et approximeret centrum imellem siderne af cellen.

Cirklernes overlap danner et pseudo grid jeg skal skal bruge til nogle
senere distance beregninger. Derfor skal jeg have punkt i hver celle
som bedst muligt repræsenterer cellen når jeg skal finde en afstand
mellem cellen og et andet punkt (placeret i en folkårlig vinkel og
afstand fra cellen).

Jeg ved ikke hvad der er bedst umiddelbart til dette.

mine tidligere informationer kan forøvrigt begrænses yderligere til at
der aldrig kommer over 10 cirkel centrummer på fladen.

---

On Tue, 28 Feb 2006 17:39:18 +0100
Henning Makholm <henning@makholm.net> wrote:

> Scripsit Kim Schulz <kim@schulz.dk>
> > Henning Makholm <henning@makholm.net> wrote:
>
> >> Du bliver nødt til at definere nøjere hvad du mener med "centrum" i
> >> denne sammenhæng.
>
> > Et approximeret centrum imellem siderne af cellen.
>
> Det er en _anvendelse_ af ordet "centrum", ikke en definition.
>

et punkt som bedst muligt kan repræsentere alle de andre punkter i
cellen. Ved ikke rigtigt hvordan det kan siges mere præcist end det.

afgørende er det at punktet ligger inde i cellen.

---

On Tue, 28 Feb 2006 18:02:28 +0100
Henning Makholm <henning@makholm.net> wrote:

> Scripsit Kim Schulz <kim@schulz.dk>
>
> > afgørende er det at punktet ligger inde i cellen.
>
> Hvis det er din eneste betingelse, så tag fx det aritmetiske
> gennemsnit af cellens hjørnepunkter.
>

Jeg er ikke helt sikker på hvad du mener når du suger jeg skal udregne
det for cellens hjørnepunkter? for mig er aritmetisk gennemsnit noget
med f.eks. (a+b+c)/3

men vil du så gøre
((x1+x2+x3...+xn)/n,(y1+y2+y3...+yn)/n)
eller hvad?

---

On Tue, 28 Feb 2006 20:15:14 +0100
Henning Makholm <henning@makholm.net> wrote:

> Scripsit Kim Schulz <kim@schulz.dk>
>
> > men vil du så gøre
> > ((x1+x2+x3...+xn)/n,(y1+y2+y3...+yn)/n)
> > eller hvad?
>
> Ja.
>
Jeg kan ikke helt se at det kan garantere at centrum ligger inde i
cellen.

eks. punkterne her forbundet i den rækkefølge:

(1,1) (2,6) (2,2) (6,2)

dette vil give (2.75,2.75) hvilket ikke ligge inde for den firkant der
dannes mellem punkterne (altså ca det samme område som cellen dækker)..

---

On Tue, 28 Feb 2006 21:29:02 +0100
Henning Makholm <henning@makholm.net> wrote:

> Scripsit Kim Schulz <kim@schulz.dk>
>
> > Jeg kan ikke helt se at det kan garantere at centrum ligger inde i
> > cellen.
> > eks. punkterne her forbundet i den rækkefølge:
> > (1,1) (2,6) (2,2) (6,2)
>
> Det giver jo en ikke-konveks figur. Hvordan opnår du den som
> fællesmængden af en række cirkelskiver?
>

Nej det giver mening! takker.

---

> Hvad der er "bedst" afhænger af hvad der menes med at "repræsentere
> cellen". Tyngdepunktet er et godt gæt, men det bliver aldrig mere end
> det, hvis vi ikke ved hvad det skal bruges til mere præcist.

Måske kan du få noget ud af at kigge på højereordens
Voronoidiagrammer.

Du har en mængde A={1..N} af cirkelcentrummer. For ethvert r punkt i
R^2 kan vi finde de fire nærmeste cirkelcentrummer (Sorteret efter
størrelse). Dette giver en afbildnning f: R^2 -> A^4. To punkter r1 og
r2 i R^2 tilhører samme (generaliserede) Voronoicelle, hvis de f(r1)
= f(r2).

Så vidt jeg husker kan man definere et centrum for sådan en
højereordens generaliserede voronoicelle, men jeg er ikke helt sikker.
Her er en god bog ,m en den beskriver desværre kun 2D, så du kan ikke
generalisere)
http://www.amazon.com/gp/reader/0471986356/103-6360794-8376619

Hvis dit datasæt er tilpas småt, så kan du udregne dine arealer
numerisk.
Hvor ethvert y er det let at skrive et program der finder

xmin(y) = min{(x,y)|(x,y) tilhører din fællesmængde}
xmax(y) = max{(x,y)|(x,y) tilhører din fællesmængde}

Hennings nævnte at din fællesmængde er konveks (fordi den er en
fællesmængde af konvekse mængder). Dette medfører at dit areal kan
udregnes således:

Areal = integral dy (xmax(y) -xmin(y)) dy

Held og lykke. Når du er færdig med dit problem, så kunne det være
skægt for os andre hvis du skrev en post om hvilken metode du endte
med at bruge, og hvad det hele skal skulle bruges til.

Niels

---

On Wed, 01 Mar 2006 01:26:21 +0100
Lasse Reichstein Nielsen <lrn@hotpop.com> wrote:
[snip]
> Hvad der er "bedst" afhænger af hvad der menes med at
"repræsentere
> cellen". Tyngdepunktet er et godt gæt, men det bliver aldrig mere end
> det, hvis vi ikke ved hvad det skal bruges til mere præcist.

jeg arbejder på en implementation af en index struktur der kaldes
MGrid.
Der dannes et pseudo gitter af cirklerne hen over et område hvori der
ligger klustre af punkter. Der skal så regnes afstande fra hver celle
til hver kluster (kmeans benyttes til at finde "centrum" i disse).

Skal bruges til senere at kunne finde klustre hurtigt når jeg får en
forespørgsel(f.eks. k-nn eller Range) i indekset som ligger i en
specifik celle.

Håber det bliver lidt mere mening og et billede af hvad det er jeg
ønsker.

---

On Wed, 1 Mar 2006 10:17:29 +0100
Bertel Lund Hansen <nospamfilius@lundhansen.dk> wrote:

> Kenneth Brun Nielsen skrev:
>
> > Det letter selvfølgelig beregningerne en del, men et mere korrekt
> > valg vil - i mine øjne - være tyngdepunktet.
>
> "Korrekt"? Hvis han bare skal bruge et punkt 'til at tage fat i',
> så er den hurtige beregning bedst.
>

ja problemet er bare at det gerne skal være et rimeligt repræsentativt
punkt jeg tager fat i da jeg ikke ved noget om størrelsen på cellerne
(deres størrelse afgøres af afstanden mellem ringene og denne sættes ud
fra punkt distributionen i området)