[Java] Vereenvoudigen polygoon

[Verwijderd]

Hallo allemaal,

Ik ben bezig met polygonen in Java. Nu heb ik een bestaand polgoon met x punten.
Nu kan je eenvoudig in Java een nieuw punt toevoegen met addPoint(int x, int y). Maar als ik dit doe dan veranderd mijn polygoon niet zoals ik wil (er lopen nu kruislingse lijnen door m'n polygoon). Hoe kan ik ervoor zorgen dat mijn polygoon vereenvoudigd wordt ( dat ik dus alleen maar hoekpunten) over hou.

Ik hoop dat jullie mij een zetje in de goede richting kunnen geven, want met het alleen sorteren van een 2 dimensionale array ben ik er volgens mij niet.

[Verwijderd]

De volgorde van punten is erg belangrijk in een polynoon... dus als je gewoonweg een addPoint doet.. zet na het laatste punt een nieuw punt... dit kan natuurlijk de bedoeling zijn... maar ik kan me voorstellen dat je eigenlijk tussen twee punten een punt wilt toevoegen en daar is addPoint niet voor geschikt. Met het gevolg dat je die kruizen krijgt!

[Verwijderd]

Ja dat is inderdaad de bedoeling. Plus het feit dat als je 2 punten hebt op een zelfde lijn en er komt een punt bij op dezelfe lijn, dat je eigenlijk maar 2 punten nodig hebt om de lijn door te trekken. Weet iemand hier een manier voor om dit probleem op te lossen??

[Verwijderd]

alle punten opslaan in een array buiten de polynoom de nodige punten toevoegen op de juiste plaats dan... alle punten in polynoom verwijderen, dan punten toevoegen in polynoom via addPoint(..)

maar waarschijnlijk heeft die polynoom classe een methode die een bepaald punt op een bepaalde index kan toevoegen!

[Dash2in1]

Het lijkt me dat je de oorspronkelijke punten moet hebben aangevuld met je nieuwe punt.
Dan die punten gaan sorteren op de x-as (als er voor elke x, maar 1 punt mag zijn).
En vervolgens die polygoon gaan tekenen..

Kan je niet op dubbele punten checken dmv intersects?

[Verwijderd]

Nee dat is juist het probleem. Die bestaat niet. En ik heb geen idee hoe ik zelf zo methode kan maken.

[Verwijderd]

Dash2in1 was me voor. Dit lijkt me wel een oplossing die ikzelf kan bouwen. Ik ga er even mee stoeien. Alvast bedankt. Mocht iemand anders nog tips hebben. Die zijn van harte welkom !!

[hobbit_be]

ik snap echt niet wat je wil doen ik neem aan dat die Polygon met een addpoint gewoon een vertex aan de lijst hangt. Als je er een tussen wil voegen dan bestaan daar misschien functies voor (zoals addPoint(x,y, index). Voor het vereenvoudigen van Polygonen - tja hangt er ook vanaf wat je wil: als je uitsluitend unwanted points kwijt wil spelen is de normale techniek: pak punt x en x+2 bereken lijn equation. pak punt x+1 en bereken hoever deze van de lijn zit: als dit kleiner is dan een bepaalde afstands dan is dat punt 'safe' om te verwijderen.

(dat laatste kun je ook opvatten als de krommings sterkte tussen de twee lijnstukken wat ook een veelgebruikte techniek is. Bijvoorbeeld if hoek < 2graden dan kill point)

[ Voor 15% gewijzigd door hobbit_be op 21-08-2003 14:23 ]

[Verwijderd]

hobbit_be schreef op 21 August 2003 @ 14:21:
ik snap echt niet wat je wil doen ik neem aan dat die Polygon met een addpoint gewoon een vertex aan de lijst hangt. Als je er een tussen wil voegen dan bestaan daar misschien functies voor (zoals addPoint(x,y, index). Voor het vereenvoudigen van Polygonen - tja hangt er ook vanaf wat je wil: als je uitsluitend unwanted points kwijt wil spelen is de normale techniek: pak punt x en x+2 bereken lijn equation. pak punt x+1 en bereken hoever deze van de lijn zit: als dit kleiner is dan een bepaalde afstands dan is dat punt 'safe' om te verwijderen.

(dat laatste kun je ook opvatten als de krommings sterkte tussen de twee lijnstukken wat ook een veelgebruikte techniek is. Bijvoorbeeld if hoek < 2graden dan kill point)

Dit laatste snap ik wel. Alleen met die index...ik kan alle punten wel een index geven. Alleen welke index moet in nu aan mijn nieuwe punt geven? Hoe bepaal ik dat?

[edit] Ik kom er net achter dat ik het in de hoek van union boolean moet zoeken. Maar ja hoe nu verder. Hoe kan ik 2 polygonen samen smelten?

[ Voor 10% gewijzigd door Verwijderd op 21-08-2003 15:32 ]

[hobbit_be]

tja deadman als je wil geen boolean met polys hoop ik dat daar code inzit in java voor jouw anders kun je alvast Foley Van Damme gaan kopen en deftig searchen. Boolean ops zijn heel logisch voor de mens en dus moeilijk voor de PC. (nou ja is wiskunde, wiskunde en nog eens wiskunde dus). Btw alle punten HEBBEN al een index:

addPoint() //index 0
addPoint() //1 ...
etc.

Euh een polygon is een volgorde van punten. Zet maar eens 20 stippen op een blad daar kan je belachelijk veel mogelijke polygons van maken. Je kan dus wel zeggen poly A bestaat uit punt 3 ,2, 8 en 10 maar de volgorde is net even belangrijk.

[Knutselsmurf]

Wat je dus wilt hebben, is de convexe polygoon? Zo ja, dan zijn daar een aantal efficiente algorithmes voor, om voor een aantal punten de convexe polygoon te bepalen. Iedere keer dat je nu een punt toevoegd, bepaal je de convexe polygoon en alles wat daar niet toe behoort, kieper je weg.....

[Verwijderd]

Ja het gaat om een convex polygoon.

Ja inderdaad de volgorde daar zit het hem ook in. Stel dat ik 5 punten heb die netjes sluiten zodat ik een pentagon krijg. Als ik nu een willekeurig punt wil toevoegen moet ik eerst checken of dat punt niet binnen de huidige polygon ligt (met intersect). Maar als dat niet het geval is hoe weet ik dan waar (onder welke index) dat punt moet toevoegen !! Ik kom er echt niet uit. Misschien toch maar van Damme kopen, of kan iemand mij verder helpen?

En wat zijn die effectieve algoritmes? Ik heb al gegoogled, forums etc, maar ik kom er niet uit. (gaat om 2d polygonen trouwens)

[ Voor 17% gewijzigd door Verwijderd op 21-08-2003 17:36 ]

[hobbit_be]

kun je geen screenshotje maken van wat je wil doen (ie before and after). misschien wil je iets specifieker dan een allesomvattend geval...

[MrBucket]

Een convex polygon wordt in de computationele geometrie ook wel een 'convex hull' genoemd. Als je daarop zoekt (evt. in combinatie met 'algorithm') dan kom je hele interessante links tegen. Deze leek me zelf wel handig:

http://www.cs.princeton.e.../version1/ConvexHull.html

[MrBucket]

Mja, bij nader inzien wel lollig maar niet echt effectief. Dit algoritme rekent de convex hull uit van een willekeurige verzameling hoekpunten, en is bij mijn weten een van de efficientste:

In pseudo-code:

code:

Input: A set P of points in the plane
Output: A list containing the vertices of CH(P) in clockwise order
1. Sort the points by x-coordinate, resulting in a sequence p[1]...p[n]
2. Put the points p[1] and p[2] in a list LUpper, with p[1] as its first point
3. for i := 3 to n do
4.   Append p[i] to LUpper
5.   while LUpper contains more than 2 points AND the last three points
             in LUpper do not make a right turn
6.     do Delete the middle of the last three points from LUpper
7. Put the points p[n] and p[n-1] in a list LLower, with p[n] as its first point
8. for i := (n-2) downto 1 do
9.   Append p[i] to LLower
10.  while LLower contains more than 2 points AND the last three points
             in LLower do not make a right turn
11.    do Delete the middle of the last three points from LLower
12.Remove the first and last point from LLower (since they're already contained
   in LUpper
13.Append LLower to LUpper, and call the resulting list L
14.Return L

Omdat het om een convex polygon gaat, mogen 3 opeenvolgende punten alleen maar een 'bocht naar rechts' maken - op het moment dat je een bocht naar links maakt, is je polygon niet langer convex.
Dit algoritme loopt twee keer door je verzameling punten heen: 1 keer om de bovenkant van de convex hull te bepalen, en 1 keer voor de onderkant. Bij beide keren wordt het criterium gebruikt: als 3 opeenvolgende hoekpunten geen bocht naar rechts maken, dan maakt de middelste geen deel uit van de convex hull.

Tip: loop 't algoritme een keer met de hand na met een stuk of 10 punten ofzo....
Helpt om het te snappen

[.oisyn]

Als je al een hull hebt waar je 1 punt aan toe moet voegen, is het wat makkelijker

Je moet alle edges van de polygoon die je al hebt doorlopen, en dan kijken of het nieuwe punt zich dan aan de binnenkant of aan de buitenkant van de edge bevindt. Je bent namelijk op zoek naar alle edges waarbij de punt erbuiten ligt. Stel de lijst edges van de polygoon voor als een cyclische lijst, en als er meerdere edges zijn waarbij de punt erbuiten ligt, dan volgen deze elkaar allemaal op.

Is er geen edge te vinden, dan valt de punt volledig binnen de polygoon, en hoeft er dus niets gedaan te worden.
Zijn er wel een of meerdere edges, dan haal je alle hoekpunten die deze edges hebben ertussenuit, behalve de eerste en de laatste, en vervolgens voeg je het nieuwe punt hiertussen.

Et voila, daar is je nieuwe convex hull


even tekeningetje erbij, da's wat makkelijker te begrijpen


Het rode punt is de vertex die je toe wilt voegen. Je begint de lijst edges te doorzoeken vanaf edge a. Je ziet dat het punt buiten edge a ligt (trek de edge tot in het oneindige door, en kijk dan of het punt zich aan de andere kant bevindt dan je polygoon). Ditzelfde geldt voor b.
Bij c, d en e ligt ie erbinnen.

Het pad a-b loopt van vertex 1 t/m 3, dus alle punten tussen 1 en 3 haal je weg. Alleen punt 2 dus. En de nieuwe vertex voeg je hiertussen in.

Deze methode is sneller als je al een hull hebt en je maar 1 punt hoeft toe te voegen. Als je de hull om een verzameling punten moet vinden dan kun je beter de methode gebruiken die MrBucket naar voren bracht

[Verwijderd]

Okey volgens Mr. curry684 mocht ik gewoon doorgaan binnen dit topic, alhoewel het een nieuw probleem is.

Alfin. Nu heb ik echter een probleem erbij. 1 punt toevoegen is nu geen probleem. Maar nu wil ik aan het polygoon een willekeurig figuur toevoegen (zie afbeelding). Weet iemand waar ik een algoritme hiervoor kan vinden, of kan iemand mij wat zoektermen geven...of gewoon een zetje in de goede richting, want ik loop helemaal vast.



Zoals je kan zien is het niet meer de bedoeling dat de buitenste hoekpunten met elkaar worden verbonden. In het bovenstaande voorbeeld wil ik een vierkant toevoegen. Er komen 2 punten bij. Stel dat ik dit zelfde vierkant aan de bovenkant van het polygoon wil toevoegen, dan moeten alleen de bovenste punten doorgetrokken worden.

Alvast bedankt voor je reactie. (En voor Janoz...alle niet gebruikte punten moeten worden verwijderd...ook hiervoor heb ik dus een algoritme nodig)

[Janoz]

ff een CnP uit het vorige topic van mijn reactie :
Dit is ook niet een simpel probleem. Daarnaast mis je in je omschrijving ook behoorlijk wat stappen . Wat wordt bijvoorbeeld het criterium voor het verwijderen van punten? Ik kan me voorstellen dat een punt dat niet meer op de rand van het resulterende polygon ligt wordt weggehaald, maar in je voorbeeld is een punt dat nog steeds op de rand lag ook verwijderd. Op het oog is dat heel goed te doen, maar in een algoritme is dat net ietsje lastiger.

Probeer het samenvoeg probleem op te delen in hele kleine stapjes. Deze stapjes zouden in totaal uit moten komen bij het nieuwe polygon, en elk los stapje moet op zichzelf een simpele handeling zijn.

Het probleem is op te lossen door stappen als "Ligt punt A binnen poly B", "Snijd lijnstuk A lijnstuk B en op welk punt" op een bepaalde manier te combineren.
---
Dat laatste punt is afaik in dit topic al een keer behandeld. Dit moet je echter weer als een los onderdeel zien en niet in een keer meenemen. Zorg eerst dat je een polygon hebt waarin de rand goed is ondanks dat er misschien teveel punten in zitten. Die punten kun je vervolgens in een nieuwe stap wel weer verwijderen.

[ Voor 16% gewijzigd door Janoz op 25-08-2003 12:37 ]

[Verwijderd]

Ja dat is het hem idd. "Een bepaalde manier" wat is deze manier?

[.oisyn]

Zoek eens naar Constructive Solid Geometry, oftewel CSG. Hiermee kun je verschillende boolean operaties (union (OR), intersection (AND), difference (-)) uitvoeren op verzamelingen van convexe objecten. Over het algemeen wordt dit toegepast in 3D, maar het werkt net zo goed op 2D polygonen

[Verwijderd]

Constructive Solid Geometry...kan wel wat vinden, maar niet echt hoe je ze moet gebruiken. In combinatie met BSP's? BSP's inplementeren is niet mijn favoriete hobby...zeg maar gerust dat ik het gewoon erg lastig vind om deze techniek te gebruiken. Zijn er echt geen andere technieken?

[Verwijderd]

Zo bijna de hele dag lopen zoeken, andere forums etc. Maar niets wat mij verder kan helpen. Heel vervelend als je op zoiets vast loopt. Het schijnt dus allemaal behoorlijk ingewikkeld te zijn. Maar het lijkt mij dat ik niet de enige ben die zoiets wil doen zonder gebruik van BSP's...

[.oisyn]

Wat is er mis met BSP's? Het is juist een hele simpele techniek. Ik zie het probleem dan ook niet helemaal... wat is precies je probleem met BSP trees?

offtopic:
en btw, een topic kicken mag pas na 24 uur

[Verwijderd]

Nou...ik snap nog wel hoe je bijv. een vierkant kan onderbrengen in een binaire boom. Vierkant ABCD resulteerd in:



Maar hoe moet ik nu EFGH mergen en dan de punten zo in Java verwerken dat ik een rechthoek AFGD krijg(simpel voorbeeld) Dat snap ik echt niet.

[.oisyn]

Bij CSG werk je niet met lijnstukken, maar met vlakken. In 2D zijn dat dus oneindige lijnen. De leafs in de bijbehorende BSP tree geven aan of dat stukje ruimte solid of empty is.

Het ligt er een beetje aan hoe je je objecten definieert, maar over het algemeen is de voorkant van een vlak empty, en de achterkant solid. Om consistent te zijn met bovenstaand figuur, is de rechter child de voorkant, en de linker child de achterkant.

Als je het vierkant ABCD van hierboven neemt, dan is de root dus de lijn waar lijnstuk AB op ligt. Voor AB is lege ruimte, dus de rechterchild van de root is een empty leaf. Achter AB volgen de andere lijnen.
Dit gaat zo door tot DA. Daar is de voorkant lege ruimte, dus de rechterchild is een empty leaf. De achterkant is echter solid ruimte, dus de linkerchild is een solid leaf.

Vierkant EFGH ga je vervolgens toevoegen aan deze boom. Aangezien je hier een boolean union wilt berekenen, behandel ik alleen die.

Bij elke node die je in de boom tegen komt, moet je het object snijden door de huidige lijn. De linkerchild laat je dan verder gaan met het gedeelte dat aan de achterkant van de lijn ligt, en de rechterkant gaat verder met het gedeelte dat aan de voorkant ligt. Dit doe je tot je bij een leaf uitkomt. Is de leaf solid dan kun je de rest vergeten. Is de leaf empty, dan voeg je de lijnen van het object dat je dan nog over hebt toe aan de boom.

Het uitendelijke object kun je dan uit de boom halen door alle lijnstukken te vinden die op de grens liggen van empty en solid ruimte. Let wel dat je dan rechthoek ABFGCD krijgt, en niet AFGD. Maar dan kun je nog wel alle lijnstukken doorlopen om te zien of het volgende lijnstuk op het verlengde ligt van de vorige, zodat je onnodige punten kunt verwijderen

[curry684]

Verwijderd schreef op 25 August 2003 @ 12:31:
Okey volgens Mr. curry684 mocht ik gewoon doorgaan binnen dit topic, alhoewel het een nieuw probleem is.

Sja binnen 3 dagen, en in zoverre hetzelfde probleem dat je het zelfs 'Part 2' noemt vind ik wat overdreven _{en je hoeft geen meneer te zeggen hoor}

[.oisyn]

Ik vond hier trouwens nog een mooi linkje: http://www.cfxweb.net/~aggrav8d/tutorials/csg.html

[hobbit_be]

voor de een of andere reden denk ik niet dat CSG zo geweldig is voor deze dude zijn probleem. Lijkt me in 2D veel logischer om alle snijpunten te vinden deze bij te houden dan een origineel punt te vinden, deze 'edge' tracen (ie lijnstukken af lopen in richting) totdat je bij een nieuw snijpunt uitkomt (if any) dan zien welke dat de bewerken is (Union, Substract) en de lijn verder volgen in 1 v/d twee richtingen. Er zijn een paar speciale gevallen maar die zijn makkelijk op te lossen. Als je dan van 1 poly - andere poly 2 stukken moet verkrijgen moet je alle punten afgaan en deze als 'traversed' beschouwen. ... euh uit de duim. Heb Foley van Damme niet maar lijkt me toch dat dit hier in moet staan?

[Verwijderd]

hobbit_be schreef op 25 augustus 2003 @ 21:09:
voor de een of andere reden denk ik niet dat CSG zo geweldig is voor deze dude zijn probleem. Lijkt me in 2D veel logischer om alle snijpunten te vinden deze bij te houden dan een origineel punt te vinden, deze 'edge' tracen (ie lijnstukken af lopen in richting) totdat je bij een nieuw snijpunt uitkomt (if any) dan zien welke dat de bewerken is (Union, Substract) en de lijn verder volgen in 1 v/d twee richtingen. Er zijn een paar speciale gevallen maar die zijn makkelijk op te lossen. Als je dan van 1 poly - andere poly 2 stukken moet verkrijgen moet je alle punten afgaan en deze als 'traversed' beschouwen. ... euh uit de duim. Heb Foley van Damme niet maar lijkt me toch dat dit hier in moet staan?

Heb je misschien een ISBN nummer voor me? Het lijkt me wel een handig boekje om te hebben, maar ik kan 'm niet vinden bij bol.com. Thnx

[Verwijderd]

Bedankt voor jullie reacties .oisyn & hobbit_be !! Ik denk dat ik hier wel even verder mee kan stoeien. Maar het blijft lastig als je het nog nooit gedaan hebt. Ik heb echt het idee dat ik het wiel opnieuw aan het uitvinden ben. Maar goed. Altijd handig om je wiskunde weer een beetje boven water te halen. Ik hoop dat andere ook wat aan dit topic gehad hebben !! Andere opties/technieken blijven welkom !!!

[.oisyn]

hobbit_be verwijst waarschijnlijk naar het boek "Computer Graphics: Principles and Practice" (2nd edition in C)

hobbit_be: CSG doet precies dat, het vinden van snijpunten. Zoals jij het voorstelt heb je een O(n^2) oplossing, omdat elke edge vergeleken moet worden met elke andere edge. En wat doe je als de 2 polygonen elkaar raken met een edge? Dan vindt je geen snijpunten, terwijl het toch 1 vorm is.

CSG is imho toch wel the way to go voor dit soort problemen, en het is geordend en snel.

[hobbit_be]

.oisyn. ja ik wou ook eerst zeggen CSG maar voor ik het postte ben ik het wat gaan opzoeken en toen vond ik al nul over 2D CSG. Wat ik begrepen of als mee oplossing kwam zal wel CSG zijn maar helaas nooit informatica geleerd en dus zoek je oplossing zelf en meestal zijn dat implementaties van welbekende dingen. Die edge/edge (ie oneindig snijpunten) is een van/de speciale gevallen. (eenvoudig though - je neemt alle eindpunten gewoon (van beide)). Maar met CSG (de full implementation zal dit mischien al ineens doen. Laten we hopen dat deadman verder kan. Wel een interssant geval want Flash is in dat soort zaken eigenlijk vree knap (zoals gaten in polys en curve intersects). Als ie dus met de oplossing (concreet) mag ie dat graag posten. En idd dat boek. Mischien staat er ook iets in Graphic Gems of op Citeseer (die NEC super graphics search site).

[Verwijderd]

Okey ik ben dus ff gaan stoeien met de informatie die ik van .oisyn had gekregen. Ik heb nu EFGH in de boom van ABCD verwerkt. Wat resulteerd in het volgende:


Uitgaande van een post-order en dat een node met 1 empty en 1 solid leaf een geldig lijnstuk voorsteld:
AB-EF-FG-GH-CD = ABFGHCD

Geweldig dat is de oplossing(als ik de boom althans goed heb gerealiseerd, volgens mij wel. Toch .oisyn?) Ik snap niet waarom ik EF als eerste node heb gekozen (onder BC)...omdat dit de root is van vierkant EFGH? En waarom ik onder CD geen EH heb gezet? Geen idee. Anders krijg je redudantie ????

Maar nu heb ik ook een probleem bij het toevoegen van een driehoek:


Wat is de root van driehoek EFG? Als ik EG als root neem, dan liggen zowel EF als FG aan de voorzijde? Maar dat kan dus niet met een binaire boom. Hoe los ik dit op?

[.oisyn]

Je kunt niet zomaar uitgaan van de volgorde van de boom. Zoals je zelf al zegt gaat het bij die vierkanten goed zolang je EF als root neemt, maar als je EH als root neemt dan krijg je een heel ander resultaat. Bovendien werkt het al helemaal niet zo als de 2 polygonen elkaar snijden.

Overigens zijn de lijnen EF en EH zoals ie in je boom staat overbodig: er zijn namelijk al respectievelijk een AB en een BC, dus nog een keer de ruimte verdelen over die lijnen is nogal nutteloos. De rechterchild van EH moet dan ook gewoon een solid leaf zijn, en EF kan er ook uit.

Je moet het anders aanpakken: jij denkt nog steeds in lijnstukken. Maar dat zijn het niet, het zijn oneindige lijnen. De root van de boom, AB, loopt dan ook tot in het oneindige door, en zo moet je het ook behandelen. Deze oneindige lijn wordt uiteindelijk gevormd tot een of meerdere lijnstukken, en dat hangt dus volledig af van de kinderen van de node.

Even voor de goede orde, je boom zou er zo uit moeten zien:

code:

        AB
       /  \
      BC   e
     /  \
    CD   \
   /  \   \
  DA   e   FG
 / \      /  \
s   e    GH   e
        /  \
       s    e

Zoals ik al zei, je moet alle lijnstukken vinden die solid space van empty space onderscheiden. De makkelijkste manier om deze te vinden is denk ik door langs alle stukjes solid space te gaan. Alle lijnen die dit stukje solid space omsluiten zijn alle parents van de leaf. Dus DA, CD, BC en AB. Als je deze lijnen met elkaar snijdt, dan krijg je weer vierkant ABCD. Ga nu voor elk van de lijnen AB, BC, CD en DA zoeken of er een stukje solid space is dat deze lijn ook als afbakening heeft, maar aan de andere kant ligt. Voor AB, CD en DA vindt je niets, en dit zijn dan automatisch ook lijnstukken die in de uiteindelijke polygoon terecht komen. Aan de andere kant van BC vindt je echter een stukje dat de oorspronkelijke vierkant EFGH was. Nu moet je gaan kijken welk deel van BC ze overlappen. Aangezien E=B en H=C overlappen ze elkaar volledig, en komt lijnstuk BC dus ook niet in de uteindelijke polygoon voor. Maar stel nou dat je EFGH iets naar beneden had verplaatst, dan was er op het stuk BE geen overlapping geweest, en dan zou dat wel een lijnstuk in het resultaat worden.

Doe dit voor elke lijn van elk stukje solid space, tot je ze allemaal gehad hebt. En vervolgens heb je een lijst van lijnstukken, die je dan alleen nog maar aan elkaar hoeft te plakken.


hobbit_be: nu ik er zo over praat is het idd misschien toch meer werk dan gewoon op zoek gaan naar snijpunten zoals je voorstelde. De boom opbouwen is zo gedaan natuurlijk, maar ik had er even niet bij stil gestaan dat de rest, dus wat ik hier net heb uitgelegd, ook nog wat rekenwerk vergt. Maar goed, het is iig een methode die werkt

[Verwijderd]

Ik ga weer ff knutselen....Bedankt voor je uitleg.

[edit]
Okey ik probeer het te vertalen in stappen(mijn vriend computer is nogal dom namelijk)
1. Bepaal Root, trek deze lijn oneindig door;
2. Kijk voor de lijn, kijk achter de lijn; Voeg oneindige lijn die kruist voor toe aan rechter kant en oneindige lijn die achter kruist aan de linker kant van de boom;
3. herhaal stap 2 voor alle (oneindige)lijnen;
4 bepaal per gevonden node of voor of achter(links of rechts) solid of empty is.
5. De nieuwe polygoon zijn alle nodes in de boom, beginnend bij de root waarbij de rechter node empty is en de ander solid.(of in geval van de root bijde solid zijn)

Ik probeer het zo voor te stellen:


Is deze gedachte correct?

[ Voor 88% gewijzigd door Verwijderd op 27-08-2003 15:16 ]

[.oisyn]

Uhm nee, volgens mij snap je het idee van een BSP tree nog niet helemaal

Je zegt dat EF aan de voorkant van AB ligt (rechterchild van AB), maar dat klopt natuurlijk niet. Zowel de driehoek EFG als vierkant ABCD ligt aan de achterkant van lijn AB. Dus de rechterchild van AB is een empty leaf.

[Verwijderd]

Nee idd, ik dacht dat ik het door had, maar kennelijk niet. Wat zou de BSP tree van bovenstaand voorbeeld moeten zijn dan?

[Janoz]

Kort door de bocht:
BSP (binairy space partition) (not sure about the space though) deelt de ruimte op.

Ales wat aan de ene kant ligt komt in de ene subboom en alles wat aan de andere kant ligt in de andere. Zou je met BC beginnen dan komt BF en FC in de ene subboom en AB,CD en CA in de andere. Het lijkt me sowieso handiger om voor de zelfde punten niet meerdere namen te nemen. Dat werkt alleen maar verwarrend en is simpel op te lossen .

1st guess voor de boom met AB als root:

code:

       AB
      /  \
     e    AD
         /  \
       BC    e
      /  \
     /    CD
    /    /  \
  BF    e    s
 /  \ 
e    CF
    /  \
   s    e

disclaimer: Dit is zo ongeveer de eerste BSP tree die ik met de hand maak......

[.oisyn]

deadman: de lijnen zijn natuurlijk wel oneindig, maar ze kunnen nooit verder gaan dan de lijn van de parent, anders heeft die opdeling ook weinig nut

Als je weer uitgaat van de boom van ABCD, dan ligt EFG dus rechts van BC. De lijn EF gaat dan ook maar tot aan BC. Als BC de driehoek EFG zou snijden, dan komt EF natuurlijk wel aan beide kanten te liggen, maar dan zie je ze ook aan beide kanten in de boom terug. Je werkt continu in deelruimtes die zijn afgeschermd door de lijnen van elke parent van de huidige node

Ik stel voor om op zoek te gaan naar een goeie BSP tutorial, die kan het allemaal vast beter uitleggen dan ik