J'ai un problème de géométrie computationnelle que je me sens devrait avoir une solution relativement simple, mais je ne peux pas tout à fait le comprendre.
J'ai besoin de déterminer la non-convexe contour d'une région définie par plusieurs segments de ligne.
Je suis au courant de diverses organisations non-enveloppe convexe des algorithmes (par exemple les alpha formes), mais je n'ai pas besoin pleinement algorithme général, comme les segments de ligne définir une unique solution dans la plupart des cas.
Comme @Jean-FrançoisCorbett l'a souligné, il y a des cas où il existe plusieurs solutions. J'ai clairement besoin de penser plus au sujet de ma définition.
Cependant, ce que je suis en train de faire est de le désosser et d'utiliser un format de fichier propriétaire, de sorte que je peux exécuter des analyses de base sur des données recueillies par moi-même et les autres. Le format de fichier est assez simple, mais la détermination de l'algorithme qu'ils utilisent pour définir la frontière est beaucoup plus difficile.
Mettre dans de nombreux cas limites qui aurait pour conséquence une non-solution unique provoque le logiciel en question soit de bloquer sans avertissement ou silencieux, ne parviennent pas à lire le fichier.
Par conséquent, lorsqu'il y a plusieurs solutions, soit en générant une des solutions acceptables, ou d'être en mesure de déterminer qu'il existe de multiples solutions serait acceptable.
Définition Du Problème:
Le polygone de contour ne doit jamais traverser l'un quelconque des segments et devrait être constitué de lignes joignant tous les segments terminaux. Tous les segments doivent se trouver entièrement à l'intérieur ou le long de la frontière du polygone. Pas de point de terminaison peut être utilisée plus d'une fois dans le plan (Ignorant la "fermeture" du polygone en ajoutant le premier point à la fin pour les bibliothèques logicielles qui nécessitent de polygones pour les fermer.).
Dans les cas où il existe plusieurs solutions qui répondent à ce critère, aucune de ces solutions serait acceptable. (Il serait agréable d'être en mesure de déterminer quand la solution n'est pas unique, mais ce n'est pas strictement nécessaire.)
Exemples:
Comme un exemple, j'ai quelque chose le long de ces lignes:
Et je tiens à délimiter le domaine suivant:
Il devrait également travailler pour les non-intersection des segments. E. g.
Je pense (?) il y a une unique solution dans les deux cas, sous réserve des critères aperçu plus tôt. (Edit: Il n'y a pas une solution unique, en général, comme @Jean-FrançoisCorbett souligné. Cependant, je suis toujours intéressé à un algorithme qui permettrait de générer l'une des solutions acceptables.)
Des Cas De Test
Pour un cas de test, voici le code à générer les chiffres ci-dessus. Je suis à l'aide de python ici, mais la question est indépendant de la langue.
import matplotlib.pyplot as plt
def main():
test1()
test2()
plt.show()
def test1():
"""Intersecting segments."""
segments = [[(1, 1), (1, 3)],
[(3.7, 1), (2, 4)],
[(2, 0), (3.7, 3)],
[(4, 0), (4, 4)],
[(4.3, 1), (4.3, 3)],
[(0, 2), (6, 3)]]
desired_outline = [segments[0][0], segments[5][0], segments[0][1],
segments[1][1], segments[2][1], segments[3][1],
segments[4][1], segments[5][1], segments[4][0],
segments[3][0], segments[1][0], segments[2][0],
segments[0][0]]
plot(segments, desired_outline)
def test2():
"""Non-intersecting segments."""
segments = [[(0, 1), (0, 3)],
[(1, 0), (1, 4)],
[(2, 1), (2, 3)],
[(3, 0), (3, 4)]]
desired_outline = [segments[0][0], segments[0][1], segments[1][1],
segments[2][1], segments[3][1], segments[3][0],
segments[2][0], segments[1][0], segments[0][0]]
plot(segments, desired_outline)
def plot(segments, desired_outline):
fig, ax = plt.subplots()
plot_segments(ax, segments)
ax.set_title('Segments')
fig, ax = plt.subplots()
ax.fill(*zip(*desired_outline), facecolor='gray')
plot_segments(ax, segments)
ax.set_title('Desired Outline')
def plot_segments(ax, segments):
for segment in segments:
ax.plot(*zip(*segment), marker='o', linestyle='-')
xmin, xmax, ymin, ymax = ax.axis()
ax.axis([xmin - 0.5, xmax + 0.5, ymin - 0.5, ymax + 0.5])
if __name__ == '__main__':
main()
Des idées?
Je commence à soupçonner que le logiciel dont les résultats que j'essaie de reproduire utilise une radiale de balayage de l'algorithme dans une sorte de "interne" du système de coordonnées (par exemple, Un système de coordonnées avec x-prime et y-prime à l'échelle et rotation le long des axes principaux définis par la propagation de points. Ce qui rend le problème plus "circulaire".) Cependant, ce qui produit des solutions où le contour coupe des segments de ligne dans de nombreux cas. Il est assez facile de le détecter et de force brute à partir de là, mais il y a certainement une meilleure façon?
