| | | Gut zu wissen: Hilfreiche Tipps und Tricks aus der Praxis prägnant, und auf den Punkt gebracht für Autodesk Produkte |
Autor
|
Thema: Punkt in Fläche (4687 mal gelesen)
|
U. Neumann Mitglied
Beiträge: 22 Registriert: 18.11.2003 AutoCAD 2000
|
erstellt am: 26. Mai. 2004 16:28 <-- editieren / zitieren --> Unities abgeben:
Hallo Lisp-Forum, ich habe folgendes Problem. Gegeben ist eine Fläche, d.h. die Punkte, die diese Fläche einschließen liegen in einer Liste vor. Wie ermittle ich nun, ob ein weiterer Punkt (Koordinaten sind ebenfalls bekannt) innerhalb oder außerhalb dieser Fläche liegt? Dank für eure Hilfe.
Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
Brischke Moderator CAD on demand GmbH
Beiträge: 4171 Registriert: 17.05.2001 AutoCAD 20XX, defun-tools (d-tools.eu)
|
erstellt am: 26. Mai. 2004 16:45 <-- editieren / zitieren --> Unities abgeben: Nur für U. Neumann
|
U. Neumann Mitglied
Beiträge: 22 Registriert: 18.11.2003 AutoCAD 2000
|
erstellt am: 28. Mai. 2004 12:16 <-- editieren / zitieren --> Unities abgeben:
|
Ex-Mitglied
|
erstellt am: 28. Mai. 2004 13:00 <-- editieren / zitieren -->
Zitat: Original erstellt von U. Neumann: Hallo Lisp-Forum,ich habe folgendes Problem. Gegeben ist eine Fläche, d.h. die Punkte, die diese Fläche einschließen liegen in einer Liste vor. Wie ermittle ich nun, ob ein weiterer Punkt (Koordinaten sind ebenfalls bekannt) innerhalb oder außerhalb dieser Fläche liegt? Dank für eure Hilfe.
Im Thread, auf den Brischke verlinkt hat, sind die echten Lösungswege nicht näher erklärt, und die LISP-Lösung ist eine sehr unsaubere Krücke. Deshalb will ich das mal hier nachholen. Es gibt zwei sehr einfache und schnelle Verfahren, mit denen man auch programmtechnisch sehr schnell feststellen kann, ob ein Punkt innerhalb oder außerhalb eines Polygons liegt. Hat die Fläche eine Grenze, die nicht ausschliesslich aus Geradenstücken besteht, dann wird es allerdings schwierig. Der erste Weg ist: man zieht einen Strahl vom zu prüfenden Punkt auf einen beliebigen, weit ausserhalb der Zeichnung liegenden Punkt (kann einfach mittels EXTMIN/EXTMAX ermittelt werden) und erzeugt alle Schnittpunkte der das Polygon begrenzenden Linien mit diesem Strahl. Ist die Anzahl der Schnittpunkte ungerade, dann liegt der Punkt innerhalb, ist sie gerade, dann liegt der Punkt außerhalb des Polygons. Der zweite Weg ist, von einem beliebigen Eckpunkt des Polygons aus jeweils den Winkel zwischen dem zu prüfenden Punkt, dem Polygonpunkt, und dem darauf folgenden Polygonpunkt zu ermitteln und sämtliche so ermittelte Winkel aufzusummieren. Ist die Winkelsumme ein ganzzahliges Vielfaches von 360 Grad, dann liegt der Punkt innerhalb des Polygons, andernfalls nicht. Der Vorteil dieser Methoden liegt darin, dass das Polygon nicht geschlossen sein muss und noch nicht mal als Zeichnungselement existieren muss - es genügen ganz abstrakt die Angaben der Knotenpunkte und des zu prüfenden Punktes als Koordinatentupel. Sogar selbstüberschneidende Polygonzüge sind erlaubt. Die Implementierung in LISP ist absolut einfach und auch von einem Anfänger zu bewältigen, die Rechenzeit steigt lediglich linear mit der Anzahl der Vertices des Polygons. Gruß Tom Berger
------------------ Architekturwerkzeuge für AutoCAD: http://www.archtools.de |
gmk Mitglied Dipl.-Ing.(FH) Vermessung
Beiträge: 667 Registriert: 23.10.2002 Autocad 2004, WS CadCompass, Normica V2000, WinXP Prof., AMD Athlon 64 X2, 2GB, NVIDIA GeForce 7600GS, HP1055CM
|
erstellt am: 28. Mai. 2004 13:27 <-- editieren / zitieren --> Unities abgeben: Nur für U. Neumann
Zitat: Original erstellt von tom.berger: Der zweite Weg ist, von einem beliebigen Eckpunkt des Polygons aus jeweils den Winkel zwischen dem zu prüfenden Punkt, dem Polygonpunkt, und dem darauf folgenden Polygonpunkt zu ermitteln und sämtliche so ermittelte Winkel aufzusummieren. Ist die Winkelsumme ein ganzzahliges Vielfaches von 360 Grad, dann liegt der Punkt innerhalb des Polygons, andernfalls nicht.
@tom super tipp!! wenn man jetzt noch zusätzlich prüft ob der punkt immer auf der gleichen seite das jeweiligen elements (links oder rechts von linie oder bogen) liegt, hätte man das mit den bögen auch erschlagen. (ist sowieso nötig für den fall, daß der punkt auf dem polygon liegt) ciao georg Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
Ex-Mitglied
|
erstellt am: 28. Mai. 2004 14:07 <-- editieren / zitieren -->
Zitat: Original erstellt von gmk: @tom super tipp!! wenn man jetzt noch zusätzlich prüft ob der punkt immer auf der gleichen seite das jeweiligen elements (links oder rechts von linie oder bogen) liegt, hätte man das mit den bögen auch erschlagen. (ist sowieso nötig für den fall, daß der punkt auf dem polygon liegt) ciao georg
Leider nein: Wenn ein Punkt auf der Polygongrenze liegt, dann ist bei der Winkelmethode der eingeschlossene Winkel einmal +-180 Grad, dafür braucht man also keinen gesonderten Aufwand zu treiben. Aber Bögen können konkav und konvex sein, so dass die Lage des Punkts zum Bogen keinen Aufschluss darüber gibt, ob er drinnen oder draussen liegt. Wenn Bögen mitgeprüft werden sollen, dann würde ich die Prüfung über die erste Methode mit dem Strahl und den Schnittpunkten machen. Den/die Schnittpunkt(e) zwischen Strahl und Bogen kann man leicht ermitteln. Gruß Tom Berger ------------------ Architekturwerkzeuge für AutoCAD: http://www.archtools.de |
gmk Mitglied Dipl.-Ing.(FH) Vermessung
Beiträge: 667 Registriert: 23.10.2002 Autocad 2004, WS CadCompass, Normica V2000, WinXP Prof., AMD Athlon 64 X2, 2GB, NVIDIA GeForce 7600GS, HP1055CM
|
erstellt am: 28. Mai. 2004 14:38 <-- editieren / zitieren --> Unities abgeben: Nur für U. Neumann
Zitat: Original erstellt von tom.berger: Aber Bögen können konkav und konvex sein, so dass die Lage des Punkts zum Bogen keinen Aufschluss darüber gibt, ob er drinnen oder draussen liegt.
richtig! ich meinte links oder rechts im bezug auf die laufrichtung des polygons. ansonsten sagt natürlich drinnen oder draussen nichts über die zugehörigkeit zur polyfläche aus. ciao georg Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
Ex-Mitglied
|
erstellt am: 28. Mai. 2004 18:33 <-- editieren / zitieren -->
Zitat: Original erstellt von gmk: ich meinte links oder rechts im bezug auf die laufrichtung des polygons. ansonsten sagt natürlich drinnen oder draussen nichts über die zugehörigkeit zur polyfläche aus.
... geht auch nicht, beispielsweise bei sich selbst überscheidenden Polygonen. Schon bei 'ner "8" kannst Du keine Drehrichtung mehr angeben, und verzwicktere Topologien kannst Du problemlos basteln, z.B. indem Du den oberen Kreis der "8" nach unten klappst. Andererseits zeigt dies auch ein Problem auf: nach der streng mathematischen Definition wäre der Punkt innerhalb dieses Doppelkreises nämlich immer außerhalb des Polygons, während unsere weniger strenge Maßstäbe anlegende Anschauung natürlich sagen würde, dass der Punkt dann innerhalb wäre. Gruß Tom Berger
------------------ Architekturwerkzeuge für AutoCAD: http://www.archtools.de |
mapcar Mitglied CADmin
Beiträge: 1250 Registriert: 20.05.2002 Time flies like an arrow, fruit flies like a banana (Groucho Marx)
|
erstellt am: 29. Mai. 2004 08:34 <-- editieren / zitieren --> Unities abgeben: Nur für U. Neumann
|
Ex-Mitglied
|
erstellt am: 29. Mai. 2004 12:37 <-- editieren / zitieren -->
Zitat: Original erstellt von mapcar: Ich hab da ja doch noch ein kleines Problem mit der ersten Methode: Object.IntersectWith gibt ja 'Schnittpunkte' zurück, wenn nur Berührungen vorliegen.Code:
o----o | | | x-o--o >>>>> y | | o-------o
2 Schnittpunkte, also außerhalb? Das ist ein ganz typisches Beispiel, wo die Sache sehr schnell in die Hose geht.Gruß, Axel
Hallo Axel, auch in dem speziellen Fall gibt's keine Probleme, denn Du erfährst während der Berechnung des Schnittpunkts, dass die 4 Punkte kolinear sind, und dass Du deshalb diesen Fall gesondert behandeln musst. Tipp: rechne Dir einfach mal den "Schnittpunkt" für Deinen Fall aus, bei dem die zwei zu schneidenden Strecken auf einer Geraden liegen. Du siehst: Mathematik funktioniert :-) Ich würde übrigens bei solchen Fällen niemals auf eingebaute Methoden wie Object.IntersectWith zurück greifen. Die Mathematik dafür ist absolut simpel, man sollte sowas sowieso in der eigenen Funktionsbibliothek haben, der Code läuft überall und man macht sich so nicht von fremden Programmierern abhängig, und v.a. weiss man, was die Funktion macht und was nicht. Ich hab' mir übrigens das komplette GEOMCAL nachprogrammiert, und so kann ich für selten verwendete Funktionen immer auf die Doku von AutoCAD zurück greifen. Gruß Tom Berger ------------------ Architekturwerkzeuge für AutoCAD: http://www.archtools.de |
Dabrunz Mitglied
Beiträge: 127 Registriert: 28.05.2003
|
erstellt am: 01. Jun. 2004 13:40 <-- editieren / zitieren --> Unities abgeben: Nur für U. Neumann
So leid es mir tut, aber ich muss auch den 'Strahl'-Ansatz ad absurdum führen, das funktioniert nur bei sogenannten konvexen Mengen (Die Verbindungslinie von je 2 inneren Punkten liegen vollständig im Inneren der Menge) und auch nur, wenn bereits ein innerer Punkt gesichert ist. Schon bei sternförmigen Mengen (Es gibt einen inneren Punkt, von dem aus jeder Randpunkt ohne Überschneidung des Randes per Linie erreichbar ist), wie die Menge in Axels Beispiel zeigt, gibt es sehr wohl Strahlen, die aus dem Inneren der Kontur herausführen, aber den Rand 2x schneiden: Hierzu genügt es, einen Strahl zu konstruieren, der einen der Eckpunkte des Randes nur berührt und schon ist Schluss! Das gilt natürlich auch für äußere Punkte: Hier kann auch eine Linie angegeben werden, die 2 äußere miteinander verbindet, aber den Rand der betrachtetetn Menge genau einmal schneidet, also sie berührt, ganz unabhängig davon, wie die Menge beschaffen ist. Nun erinnere ich mich aber nicht mehr en detail an mein Studium, aber eines ist sicher: Für einfach zusammenhängende Mengen (Alle Punkte aus dem Inneren der Punktmenge lassen sich paarweise mit einem Polygonzu verbinden, der vollständig im Inneren der Menge liegt) gibt's eine Integrations-Methode aus der Funktional-Analysis, mit der einduetig geklärt werden kann, ob der Punkt im Inneren der Menge liegt. Ist allerdings für uns nicht besonders hilfreich .. Die Einschränkung auf einfach zusammenhängende Mengen ist allerdings von hoher Praxis-Relevanz, denn andere Mengen (oder Konturen) werden uns kaum begegnen - naja, abgesehen vieleicht von doppelten Linien .. Ich werde mich nocheinmal schlau machen. Eine Frage habe ich allerdings noch: Was soll ein inner Punkt einer nicht geschlossenen Kontur sein? Achim Dabrunz [Diese Nachricht wurde von Dabrunz am 01. Jun. 2004 editiert.] Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
Ex-Mitglied
|
erstellt am: 01. Jun. 2004 14:28 <-- editieren / zitieren -->
Zitat:
So leid es mir tut, aber ich muss auch den 'Strahl'-Ansatz ad absurdum führen, das funktioniert nur bei sogenannten [b]konvexen Mengen (Die Verbindungslinie von je 2 inneren Punkten liegen vollständig im Inneren der Menge) und auch nur, wenn bereits ein innerer Punkt gesichert ist. Schon bei sternförmigen Mengen (Es gibt einen inneren Punkt, von dem aus jeder Randpunkt ohne Überschneidung des Randes per Linie erreichbar ist), wie die Menge in Axels Beispiel zeigt, gibt es sehr wohl Strahlen, die aus dem Inneren der Kontur herausführen, aber den Rand 2x schneiden: Hierzu genügt es, einen Strahl zu konstruieren, der einen der Eckpunkte des Randes nur berührt und schon ist Schluss!.][/B]
Na gut, dann musst Du da halt noch ein paar Fallunterscheidungen einbauen :-) Zitat:
Eine Frage habe ich allerdings noch: Was soll ein inner Punkt einer nicht geschlossenen Kontur sein? [/B]
Diese Algorithmen verwenden eine Liste der Vertices in der Reihenfolge, wie sie eine Kontur bilden würden. Es wird geprüft, ob der Punkt innerhalb dieser angenommenen Kontur liegt. Das hat nur Relevanz für ein CAD Programm wie AutoCAD, wo z.B. "Polylinien" nicht geschlossen sind, aber dennoch Schraffurgrenzen usw bilden können.. Tom Berger ------------------ Architekturwerkzeuge für AutoCAD: http://www.archtools.de |
Dabrunz Mitglied
Beiträge: 127 Registriert: 28.05.2003
|
erstellt am: 01. Jun. 2004 15:13 <-- editieren / zitieren --> Unities abgeben: Nur für U. Neumann
Zitat: Original erstellt von tom.berger: Na gut, dann musst Du da halt noch ein paar Fallunterscheidungen einbauen :-)
Aha - allerdings ist die Anzahl der in Frage kommenden Fälle nicht notwendig endlich - eine wahre Sysiphus-Aufgabe :-) Die einzig sichere Aussage ob ein Punkt innerhalb oder außerhalb einer Kontur liegt gelingt über die (rel. zur Kontur) schnitt-freie Verbindung zu einem Referenz-Punkt, wenn wir us auf diese Strahl- oder Linien-, bzw. Polygon-Technik festlegen wollen. Alle anderen Methoden (abgesehen von wohl definiertetn Spezial-Fällen) liefern nur 'häufig richtige' Resultate - manchmal reicht das aber auch .. Achim Dabrunz Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
Dabrunz Mitglied
Beiträge: 127 Registriert: 28.05.2003
|
erstellt am: 01. Jun. 2004 15:21 <-- editieren / zitieren --> Unities abgeben: Nur für U. Neumann
Ich glaube, ich muss mich korrigieren: Unter der Einschränkung, dass unser betrachtetes Gebiet durch ein Polygon begrenzt wird, bleibt die Anzahl der möglichen Fälle wohl endlich. Eckpunkte (schließt Kolinearität mit ein) könnten wohl als Außnahmen genügen ... Achim Dabrunz [Diese Nachricht wurde von Dabrunz am 01. Jun. 2004 editiert.] Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
Ex-Mitglied
|
erstellt am: 01. Jun. 2004 17:03 <-- editieren / zitieren -->
Zitat: Original erstellt von Dabrunz: Aha - allerdings ist die Anzahl der in Frage kommenden Fälle nicht notwendig endlich - eine wahre Sysiphus-Aufgabe :-)
Inwiefern könnte diese unendlich sein? Sieh' nochmals oben nach: es geht nur um Konturen, die durch n gerade Linien begrenzt werden. Du musst bei der Strahlmethode den Schnittpunkt einer einzigen Strecke P-A(ußerhalb) mit jeder Grenzlinie suchen, und dabei musst Du prüfen, ob einer oder beide der jeweiligen Endpunkte auf P-A liegen. Das sind genau n einfache Prüfungen. Zitat:
Die einzig sichere Aussage ob ein Punkt innerhalb oder außerhalb einer Kontur liegt gelingt über die (rel. zur Kontur) schnitt-freie Verbindung zu einem Referenz-Punkt, wenn wir us auf diese Strahl- oder Linien-, bzw. Polygon-Technik festlegen wollen. Alle anderen Methoden (abgesehen von wohl definiertetn Spezial-Fällen) liefern nur 'häufig richtige' Resultate - manchmal reicht das aber auch ..
Nein - die Anzahl der Schnittpunkte ergibt immer ein eindeutig richtiges Ergebnis, wenn man die Sonderfälle berücksichtigt, bei denen die Endpunkte der jeweiligen Grenzlinie direkt auf P-A liegen. Gruß Tom Berger ------------------ Architekturwerkzeuge für AutoCAD: http://www.archtools.de |
Ex-Mitglied
|
erstellt am: 01. Jun. 2004 17:05 <-- editieren / zitieren -->
Zitat: Original erstellt von Dabrunz: Ich glaube, ich muss mich korrigieren: Unter der Einschränkung, dass unser betrachtetes Gebiet durch ein Polygon begrenzt wird, bleibt die Anzahl der möglichen Fälle wohl endlich. Eckpunkte (schließt Kolinearität mit ein) könnten wohl als Außnahmen genügen ...
Entschuldige - hatte Deinen vorherigen Beitrag beantwortet, bevor ich diesen hier gelesen habe. Gruß Tom Berger
------------------ Architekturwerkzeuge für AutoCAD: http://www.archtools.de |
jupa Ehrenmitglied V.I.P. h.c. Ruheständler
Beiträge: 6050 Registriert: 16.09.2004 WINDOWS Vista Ultimate SP2 (64bit), NVIDIA Geforce 9600M GT, AutoCAD 2013.
|
erstellt am: 26. Jul. 2017 17:51 <-- editieren / zitieren --> Unities abgeben: Nur für U. Neumann
ACHTUNG! Sie antworten auf einen Beitrag der älter als 1 Jahr ist! Hier mal ein ganz anderer Denkansatz für das Prüfen, ob sich ein Punkt innerhalb eines Polygones befindet oder nicht. Die Funktion testet, ob sich ausgehend von einem gegebenen Punkt und einer Kontur eine Umgrenzung(spolylinie) erfolgreich erstellen läßt (dann ist der Punkt innerhalb) oder nicht (dann eben nicht innerhalb). Damit wären etliche der oben angeführten Probleme erledigt, insbes. auch das immer wieder auftauchende Problem der Kreisbögen innerhalb der Kontur. Auch die 8 macht keinerlei Probleme. Wird die Kontur jedoch komplexer, dann müßte erst mal definiert werden, was "innerhalb" und "außerhalb" ist. Beispielsweise der im angehängten Bild rot markierte Punkt, innen oder außen? (Wird nach meiner Methode als innerhalb der Kontur erkannt). Hier der Code. Übergabeparameter sind ein Elementname (die Kontur(poly)linie) und eine Koordinate (der zu prüfende Punkt). Rückgabewert ist entweder T (wenn der Punkt innerhalb der Kontur liegt), andernfalls nil. Das "warum nil" (keine geschlossene Kontur, ungültiges Konturobjekt, Punkt nicht innerhalb, ...) wird hier im Prinzipbeispiel nicht analysiert. (defun pip (bound pp / cmd_old success) ; Point-Inside-Polygon (if (entlast) (progn (setq cmd_old (getvar "cmdecho")) (setvar "cmdecho" 0) (setq LastHandle (cdr (assoc 5 (entget (entlast))))) ;;; (setq bound (car (entsel "\nPolygon wählen: "))) ;;; (setq pp (getpoint "\nPunkt eingeben: ")) (command "_-boundary" "_a" "_b" "_n" bound "" "" pp "") (if (/= (cdr (assoc 5 (entget (entlast)))) LastHandle) (progn (setq success 'T) (entdel (entlast)) ) ) ) ) success )
Jürgen ------------------ Bildung kommt nicht vom Lesen, sondern vom Nachdenken über das Gelesene. (Carl Hilty) Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
cadffm Moderator 良い精神
Beiträge: 21533 Registriert: 03.06.2002 Alles
|
erstellt am: 26. Jul. 2017 19:11 <-- editieren / zitieren --> Unities abgeben: Nur für U. Neumann
Als GANZ ANDERS und DENKANSATZ darf man das wohl stehen lassen Aber grausam bleibt es Wenn man für so eine Form eine Lösung benötigt, im aktuellen Bereich "gearbeitet" wird, why not. Hatte ich tatsächlich auch schon öfters für temporäre Aufgabe in Gebrauch. Nicht vergessen sollte man die (geringe) Abhängigkeit von der aktuellen Anzeige, es werden grenznahe Punkte als "auf Linie" gewertet und keine Umgrenzung erzeugt. (die Meldung kann man ggf. auswerten um zwischen AufLinie und Ausserhalb zu unterscheiden) Aber das geht dann wohl in einen Bereich in dem so eine Lösung wohl auch nicht angewand werden würde. http://ww3.cad.de/foren/ubb/Forum145/HTML/001704.shtml ------------------ CAD on demand GmbH - Beratung und Programmierung rund um AutoCAD Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
jupa Ehrenmitglied V.I.P. h.c. Ruheständler
Beiträge: 6050 Registriert: 16.09.2004 WINDOWS Vista Ultimate SP2 (64bit), NVIDIA Geforce 9600M GT, AutoCAD 2013.
|
erstellt am: 26. Jul. 2017 19:33 <-- editieren / zitieren --> Unities abgeben: Nur für U. Neumann
|
| Anzeige.:
Anzeige: (Infos zum Werbeplatz >>)
|