Suppression de zones se chevauchant

[Guitz80]

Bonjour,

Je suis entrain de développer sur Unreal Engine 4 et en c++ un city builder, et là je suis en pleine implémentation de cette partie ô combien compliquée : le zoning.
Je suis en pleine reflexion sur un algorithme qui maximise le nombre de zones (petits carrés dans zonesblocks) qui demeurent après l'exclusion des zones se chevauchant, tout ayant un aspect compact.

S1 et S2 étant les segments (routes) contigus du graphes, et Z1 et Z2 étant respectivement ZonesBlock1 et ZonesBlock2, voilà ce que je souhaite obtenir étape par étape :



Y a-t'il svp un algorithme connu pour ce genre de choses ?
-----

[PHIGE]

Bonjour,

Peut être mais je pense a priori que c'est un calcul de puissance d'un point (centre des carrés) par rapport à une droite (la bissectrice de l'angle). Au delà de Coté/sqrt(2) je garde. Du mauvais coté je jette. Les restants sont triés par distance à la droite (ie sans s'occuper du signe). On garde la moitié (enfin (n+1) >> 1) la plus distante, les autres sont éliminés.

Selon l'arrangement de carrés il est peut être possibles d'éviter une partie des calculs.

Je n'obtiens pas exactement le même découpage (moins de rouges et surtout moins de vides) mais je crois, par exemple, que le carré rouge tout à droite endeuxième ligne en partant du bas n'est pas du bon coté de la bissectrice et ne devrait donc pas être conservé.

Salutations.

[polo974]

si tu avais enlevé tous les rouges touchés par les bleus, tu avais le même résultat. (-14 par rapport au i=0)
si tu avais enlevé tous les bleus touchés par les rouges, tu avais le même résultat. (-14 par rapport au i=0), mais c'est plus "serré"

actuellement, tu es parti d'un quadrillage à partir des extrémités libres, mais auras-tu toujours des extrémités libres (ex: un polyline (pire s'il est fermé).
ton angle est supérieur à 90°, mais peut-il être inférieur? peut-il aller au-delà de 180°? approcher 360°?

bref, le limites sont mal précisées...

que cherches-tu à favoriser quand il y a plusieurs solutions en nombre de carrés? (rien, une distance mini minimale, une distance mini maximale, un axe, ...)

bon, ça fera 1% des revenus de ton module... (bientôt disponible sur https://www.unrealengine.com/marketplace/ ?)

[PA5CAL]

J'ai peut-être mal vu, mais il me semble qu'il y avait la place pour un carré de plus :



Pour reprendre la méthode donnée par PHIGE, on pourrait :

Sur chaque paires de lignes de carrés situées à une même distance de son segment porteur (de 1 à 4 dans l'exemple, qu'importe l'ordre) :
- on conserve tous les carrés jusqu'au premier carré présentant une intersection avec la bissectrice des segment, ce carré étant exclus ;
- sur la ligne dont le dernier carré placé et le plus loin de la bissectrice, ajouter autant de carrés que possible sans déborder la zone de l'autre ligne de carrés.

[A voir en vidéo sur Futura]

[PA5CAL]

Illustration pour une paire de lignes situées à une même distance de leur segment porteur respectif, dans le cas d'un angle aigu :



(première étape en rouge et bleu, seconde étape en violet)