Trouver un point qui ne se trouve pas dans des rectangles tournés

Question

Je cherche un algorithme qui peut rapidement (je suis fortement contraint par la performance) trouver un point à l'intérieur d'un cercle, où ce point est en dehors de tous les rectangles d'un ensemble fourni (ces rectangles peuvent être tournés). Ou bien, pour trouver un cercle A avec son centre à l'intérieur d'un cercle B, où le cercle A ne se croise pas avec un ensemble de segments de droite.

La seule solution que je peux trouver est de faire simplement une boucle sur des échantillons de points et de faire ensuite une boucle dans les rectangles pour chacun d'entre eux. Mais puisque mon espace est continu, c'est assez pénible. Je suis fondamentalement satisfait d'un seul point qui ne se croise pas, mais il y aura des cas où de tels points n'existent pas. Dans ce dernier cas, j'essayerais idéalement de trouver un point avec le moins d'intersections, ou de trouver la réponse à l'absence de tel point.

Est-ce que quelqu'un connaît des algorithmes qui peuvent accomplir cela dans quelque chose de moins que O (n^2)? Tout ce qui aiderait à identifier de bons candidats serait aussi génial.

Un exemple typique de la situation est la suivante: Beaucoup de grands rectangles, avec un petit cercle dans lequel j'espère trouver un point (ici indiqué en bleu). Il est courant que beaucoup de rectangles tombent complètement à l'extérieur du cercle, et aussi commun que le cercle soit complètement couvert. Il y a seulement un petit ensemble de longueurs et de largeurs qui ont tendance à être utilisées pour les rectangles.

Answer 1

Une idée qui pourrait venir en sous-n^2 selon la façon dont les rectangles sont disposés:

Calculer la région possible explicitement.

La structure de données la représentant est une liste de sous-régions sans chevauchement, dont chacune est un triangle (si vous approximationz le cercle) ou un "triangle volumineux" (où un côté peut être un segment de cercle) .

Vous commencez avec une trisection du cercle (ou un ensemble de triangles le représentant), puis soustrayez successivement les rectangles. Vous faites cela en croisant chaque sous-région de la région viable qui résulte en un ensemble (éventuellement vide) de nouvelles sous-régions.

La façon dont cela peut fonctionner est si le nombre de sous-régions viables est susceptible d'être petit à un moment donné. Le traitement d'une paire d'un rectangle et d'une sous-région a une limite supérieure O (1), donc si nous attendons m sous-régions qui seront O (nm) ondulées à la main. Cela pourrait probablement être bien pire que O (n^2) dans le pire des cas (disons plusieurs rectangles disjoints complètement contenus dans le cercle) mais dans votre cas typique (grands rectangles, petit cercle) les chances sont le nombre de sous-régions wouldn ' t grandir très haut et alors ce serait "presque O (n)".

La région viable peut être une liste chaînée, où vous ajoutez uniquement des sous-régions à la fin et les supprimez au début, de sorte que l'accès peut être constant.

Les sous-régions (le cas échéant) sont convexes et ne se chevauchent pas. Ainsi, une fois la région viable calculée, l'insertion d'un point à l'intérieur de celle-ci serait triviale.