Oppervlakte vullen met polygonen

[Xuj]

Beste Tweakers,

In eerste instantie weet ik niet zeker of dit topic thuis hoort in Programming, of dat het nu in Wetenschap (& Levensbeschouwing) geplaatst moet worden.

Aangezien ik een poging aan het maken ben, met het programmeren van mijn vraag, nam ik aan dat het beter in Programming pastte. Mocht dit niet de beste keus zijn, wil ik het best plaatsen in de andere categorie.

Anyway, let's get to the point.

Ik kreeg laatst een interessant probleem voorgeschoteld.

Het gaat om het volgende:

Probeer onderstaand figuur te verdelen in zo min mogelijk driehoeken.
De grootte en de stand van de driehoeken mag je zelf bepalen.

Er gelden enkele regels:

• Er mag alleen maar gebruik worden gemaakt van de driehoeken met verhouding 1:1:√2 (i.e. het past op hokjespapier).
• Het gekruiste celletje is een 'muur'. Dat vlak mag zich niet in één van je polygonen bevinden.
• Driehoeken mogen elkaar niet overlappen.

--
Een voorbeeld:

Leeg vlak:



Ingevuld (Driehoeken (1-1-√2): 11)


Plaatjes zijn (zo eenvoudig) gemaakt als voorbeeld.

--

Nu heb ik echter géén idee, waar ik mee moet beginnen, als ik dit in een stuk code gedaan wil krijgen. Aangezien ik het momenteel vul door "zomaar wat te doen", iets wat natuurlijk niet de beste methode is!

Mijn vraag aan jullie, mede-Tweakers, is of iemand weet waarmee ik een begin kan maken. Ik verwacht geen stukken code, maar een Wiki naar een gelijkwaardig probleem bijvoorbeeld zou zeer op prijs gesteld worden.

[ Voor 10% gewijzigd door Xuj op 02-12-2010 00:45 . Reden: Versimpeling ]

[joppybt]

In google zoeken op "polygon covering" brengt je nog het meest in de buurt.

Wat ik zo lees is het probleem al extreem moeilijk (NP-complete) als je jezelf zou beperken tot vullen met vierkanten, laat staan als je complexere vormen toestaat.

Anderzijds heeft je voorbeeld een vrij eenvoudige oplossing in twee polygonen omdat hij lijn-symmetrisch is. Trek een denkbeeldige lijn van linksboven naar rechtsonder. Alles linksonder is je ene polygoon, alles rechtsboven is je andere polygoon.

Eigenlijk mis ik een heleboel randvoorwaarden om het probleem behapbaar te maken. Is de te vullen vorm altijd vierkant en past hij op 'hokjespapier'? Mogen de vul-polygonen alle vormen hebben of moeten ze convex zijn? etcetera.

[Xuj]

Als ik het zo lees.. Inderdaad.
Polygon covering is inderdaad ongeveer wat ik zoek.

De lijn-symmetetrie zit speciaal in dit voorbeeld ter versimpeling. Zou je echter een denkbeeldige lijn trekken van linksboven naar rechtsonder en vervolgens één van de twee zijden te maken om dan een spiegeling te maken, dan zal er een groter aantal driehoeken (in mijn voorbeeld) zijn.


Om enkele vragen te beantwoorden:
- De te vullen vorm is niet altijd een vierhoek. Echter zullen de hoeken tussen twee zijdes altijd 90 graden zijn.
- De polygonen die ingevuld moeten worden, zijn altijd gelijkvorming.

Tevens heb ik het probleem een stuk versimpeld. Er kan nu alleen nog maar gebruik worden gemaakt van driehoeken met verhouding 1:1:√2. Het blijft echter een moeilijk probleem.

[MLM]

Ik denk dat je behoorlijk in de buurt komt als je gewoon de zo groot mogelijke driehoek eerst plaatst, en dan blijft zoeken naar de grootst mogelijke totdat je vol zit.

Er zijn wel gevallen waarin je dan niet de beste oplossing hebt, maar je krijgt altijd wel een oplossing, die niet heel slecht is. Als je echt de best mogelijke zoekt, moet je denk ik toch gaan bruteforcen. Eventueel een hybride vorm die een aantal veelbelovende velden uitprobeert.

[ Voor 9% gewijzigd door MLM op 02-12-2010 13:49 ]

[Soultaker]

Het lijkt mij een variant op het exact cover problem wat al NP-compleet is. Daarbij zoek je naar een aantal verzamelingen (in jouw geval driehoekjes) die samen precies een doelverzameling overlappen (in jouw geval een rechthoek met wat vakjes weggelaten), waarbij je het probleem nog lastiger maakt door te specificeren dat een minimaal aantal verzamelingen wil selecteren.

Dat betekent dat er waarschijnlijk geen efficiënt optimaal oplossingsalgoritme bestaat. Maar kleine instanties zijn wellicht nog op wel exact op te lossen. Verder kun je met behulp van dynamic programming de complexiteit drastisch verlagen, ten koste van hoger geheugengebruik. In hoeverre dat praktisch is, hangt af van hoe groot de instanties zijn die je wil oplossen.

[Janoz]

Ik denk dat je in eerste instantie niet te moeilijk moet denken. Het probleem is redelijk 'versimpeld' doordat de driehoeken allemaal gelijkvormig zijn. Ze variëren alleen in grootte en rotatie. Aangezien er dus maar een eindig* aantal mogelijke driehoek vormen zijn lijkt het mij de beste aanpak om met de mogelijke driehoeken te beginnen.


Begin gewoon met een zo groot mogelijke driehoek en kijk of je die kwijt kunt. Doe dat met alle vier de rotatie voorkomens. Vervolgens neem je telkens een driehoek die een slag kleiner is en probeer daarmee telkens de overgebleven gaten mee te vullen.

*
Gegeven een oplosgebied met de afmeting X bij Y (waarbij X <= Y heb je de volgende mogelijke driehoeken:
4 rotatie vormen waarbij de korte zijde een gehele lengte heeft
Hiervan zijn er X groottes.

4 rotatie vormen waarbij de lange zijde een gehele lengte heeft
Hiervan zijn er MIN(X/2 , Y) groottes.

[PrisonerOfPain]

Alle vierkanten bevatten maximaal 2 driehoeken en die kunnen op 2 verschillende orientaties voorkomen, kortom volgens mij zou je een BFS kunnen doen naar welke driehoeken het beste mergen (eg, 3 driehoeken samenvoegen tot 1 grotere).

[MLM]

PrisonerOfPain schreef op donderdag 02 december 2010 @ 15:36:
Alle vierkanten bevatten maximaal 2 driehoeken en die kunnen op 2 verschillende orientaties voorkomen, kortom volgens mij zou je een BFS kunnen doen naar welke driehoeken het beste mergen (eg, 3 driehoeken samenvoegen tot 1 grotere).

Hoe zie je dat voor je
Je kan er 2 samenvoegen, of 4 (immers, 2x2), maar niet 3 voor zover ik weet.

BFS is brute-force in dit geval denk ik (immers, je weet niet wat de beste oplossing is, dus je weet niet wanneer je een node hebt die optimaal is, totdat je alle states hebt ge-evalueerd)

[Merijn70]

(eg, 3 driehoeken samenvoegen tot 1 grotere)

Moet zijn:
(eg, 2 of 4 driehoeken samenvoegen tot 1 grotere)

Edit: Sorry, spuit elf...

[ Voor 12% gewijzigd door Merijn70 op 02-12-2010 16:04 . Reden: Te laat ]

[PrisonerOfPain]

MLM schreef op donderdag 02 december 2010 @ 15:54:
[...]

Hoe zie je dat voor je
Je kan er 2 samenvoegen, of 4 (immers, 2x2), maar niet 3 voor zover ik weet.

Errrr. Wauw.

[TJHeuvel]

Even googlen naar 'Triangulation' en je komt al erg ver.

[MLM]

CyCloneNL schreef op donderdag 02 december 2010 @ 16:05:
Even googlen naar 'Triangulation' en je komt al erg ver.

Triangulation voldoet niet aan de eisen van de TS (de verhoudingen van de driehoek-zijden), en daarnaast zijn dit niet eens polygonen gezien ze meerdere rand-lijnen hebben (de gaten).

(Het is nog vrij simpel hier een polygoon van te maken, maar dan nog gaat triangulation niet voldoen aan de eisen van de TS)

[Janoz]

Zoeken naar triangulation is op zich ietwat onzinnig omdat de vorm van de driehoek beperkt is. Triangulatie algoritmen houden daar niet echt rekening mee.

[PrisonerOfPain]

Janoz schreef op donderdag 02 december 2010 @ 16:29:
Zoeken naar triangulation is op zich ietwat onzinnig omdat de vorm van de driehoek beperkt is. Triangulatie algoritmen houden daar niet echt rekening mee.

Alleen triangulaten als het dot product tussen je huidige edge en je te maken edge een veelvoud is van 0.5.

[Janoz]

Waardoor je dus 99.9% van de voorgestelde triangulaties af gaat wijzen omdat ze daar niet aan voldoen? Dat lijkt me erg inefficient. Zoals ik eerder al aangaf lijkt het me in deze situatie veel makkelijker om niet uit te gaan van het te vullen vlak, maar van de te gebruiken driehoeken. De mogelijke driehoeken zijn aftelbaar waardoor dat makkelijk als uitgangspunt genomen kan worden.