Blokkendoos opvullen

[KopjeThee]

Ik zit met een programmeer/query probleempje.

Ik heb een tabel met rechthoeken in een plat vlak:
x_begin, x_eind, y_begin, y_eind

Nu wil ik de tabel verder aanvullen met de nog niet "bedekte" stukken van het platte vlak (de min en max waardes van x en y zodanig dat in ieder geval de rechthoeken van de tabel er in vallen). Verder zijn er geen eisen. Het hoeft niet per se met een minimum aantal records of iets dergelijks. En eigenlijk wil ik ook nog controleren of in de opgegeven tabel records zitten met rechthoeken die overlappen (dat mag namelijk niet).

Ik heb even geen enkele inspiratie hoe dit probleem op te lossen. Ook google zoektermen zou ik niet weten. Iemand een idee???

[Matis]

Ik mis nog een hoop informatie: Welke programmeertaal wil/moet je gebruiken? Daarnaast zou je eens kunnen kijken naar het Wikipedia: Knapsack problem voor een optimale invulling van je vierkant (wat overigens niet echt een eis is).

[NMe]

Dit is inderdaad een knapsack in zijn simpelste vorm. Ik stel voor dat je link van Matis even doorneemt en daarna kijkt hoe ver je komt. Je kan daarna hier veel gerichter vragen stellen; met dit topic kunnen we niet zoveel.

[Davio]

Laat ik eens aannemen dat jouw vlak niet oneindig bij oneindig is en normale afmetingen heeft (zeg 50x50) en geen pixels.

Dan kun je per mini-rechthoek (1 bij 1) wel uitrekenen of hij bedekt is of niet door een matrix van 50x50 te maken en alle waarden op true (bedekt) of false (onbedekt) te zetten.

Vervolgens kun je voor alles wat op false staat een mini-rechthoek aanmaken, of je kunt horizontaal kijken hoe lang je de rechthoeken maximaal kunt maken. Dit is verder met knapsack wel op te lossen.

Trouwens: Jouw manier van opslaan is vervelend, want rechthoek(x1, y1, x2, y2) is natuurlijk hetzelfde als rechthoek(x2, y2, x1, y1), maar ze kunnen allebei worden opgeslagen. Misschien moet je het zo opslaan: rechthoek(x, y, hoogte, breedte).

Trouwens, tijdens het genereren van de matrix kun je kijken of er al overlap is als hij iets op true wil zetten wat al op true staat.

[Soultaker]

Het vullen van een rechthoek met andere rechthoeken is een bin packing problem, geen knapsack problem. Die zijn gerelateerd, maar wel fundamenteel verschillend (en ik heb het idee dat ik dit in elk semi-binpacking-gerelateerd topic moet zeggen )

Maar als ik de TS goed lees, dan wil 'ie heel wat anders. Hij wil drie dingen. Ten eerste kijken of er rechthoeken in de invoer overlappen. Ten tweede een bounding rectangle voor de invoer bepalen. Ten derde het niet-bedekte deel van die bounding rectangle uitdrukken in nieuwe rechthoeken.

Het eerste kan al vrij simpel door paarsgewijs rechthoeken te vergelijken. (Het kan sneller dan dat, maar dan wordt het snel ingewikkeld). Het tweede is eenvoudig: vind de minimum- en maximumcoordinaten van álle rechthoeken en dat is je bounding rectangle. Het derde kun je greedy aanpakken door steeds een onbedekt punt ergens linksboven te pakken, dan een lijn zo ver mogelijk naar rechts door te trekken die de basis van je rechthoek vormt, en die vervolgens zo ver mogelijk naar onder door te trekken. De resulterende rechthoek voeg je toe aan de set en je herhaalt de procedure tot er geen onbedekte ruimte over is. Dat levert niet noodzakelijkerwijs een minimale opdeling op, maar dat was ook niet gevraagd.

[ Voor 13% gewijzigd door Soultaker op 04-05-2010 16:23 ]

[KopjeThee]

Dank jullie wel voor de reacties. Soultaker heeft het probleem bij het juiste eind. De oplossing die ik uiteindelijk heb gebruikt is:

• Trek vertikale lijnen op alle voorkomende x coordinaten
• Trek horizontale lijnen op alle voorkomende y coordinaten
• Het zo gevormde raster vormt de basis voor de toe te voegen rechthoeken
• Verwijder uit het raster de rechthoeken die al in de originele tabel zitten
• De overgebleven rechthoeken uit het rasterwerk zijn de records die toegevoegd worden aan de tabel