Top-Themen

AppleEntwicklungHardwareInternetLinuxMicrosoftMultimediaNetzwerkeOff TopicSicherheitSonstige SystemeVirtualisierungWeiterbildungZusammenarbeit

Aktuelle Themen

Administrator.de FeedbackApache ServerAppleAssemblerAudioAusbildungAuslandBackupBasicBatch & ShellBenchmarksBibliotheken & ToolkitsBlogsCloud-DiensteClusterCMSCPU, RAM, MainboardsCSSC und C++DatenbankenDatenschutzDebianDigitiales FernsehenDNSDrucker und ScannerDSL, VDSLE-BooksE-BusinessE-MailEntwicklungErkennung und -AbwehrExchange ServerFestplatten, SSD, RaidFirewallFlatratesGoogle AndroidGrafikGrafikkarten & MonitoreGroupwareHardwareHosting & HousingHTMLHumor (lol)Hyper-VIconsIDE & EditorenInformationsdiensteInstallationInstant MessagingInternetInternet DomäneniOSISDN & AnaloganschlüsseiTunesJavaJavaScriptKiXtartKVMLAN, WAN, WirelessLinuxLinux DesktopLinux NetzwerkLinux ToolsLinux UserverwaltungLizenzierungMac OS XMicrosoftMicrosoft OfficeMikroTik RouterOSMonitoringMultimediaMultimedia & ZubehörNetzwerkeNetzwerkgrundlagenNetzwerkmanagementNetzwerkprotokolleNotebook & ZubehörNovell NetwareOff TopicOpenOffice, LibreOfficeOutlook & MailPapierkorbPascal und DelphiPeripheriegerätePerlPHPPythonRechtliche FragenRedHat, CentOS, FedoraRouter & RoutingSambaSAN, NAS, DASSchriftartenSchulung & TrainingSEOServerServer-HardwareSicherheitSicherheits-ToolsSicherheitsgrundlagenSolarisSonstige SystemeSoziale NetzwerkeSpeicherkartenStudentenjobs & PraktikumSuche ProjektpartnerSuseSwitche und HubsTipps & TricksTK-Netze & GeräteUbuntuUMTS, EDGE & GPRSUtilitiesVB for ApplicationsVerschlüsselung & ZertifikateVideo & StreamingViren und TrojanerVirtualisierungVisual StudioVmwareVoice over IPWebbrowserWebentwicklungWeiterbildungWindows 7Windows 8Windows 10Windows InstallationWindows MobileWindows NetzwerkWindows ServerWindows SystemdateienWindows ToolsWindows UpdateWindows UserverwaltungWindows VistaWindows XPXenserverXMLZusammenarbeit

Schulaufgabe Cpp Konsolenprogrammierung

Frage Entwicklung C und C++

Mitglied: Klogriff

Klogriff (Level 1) - Jetzt verbinden

12.06.2007, aktualisiert 13.06.2007, 4060 Aufrufe, 5 Kommentare

Servus ich grüße euch!

Ich habe ein kleines Problem mit einer Aufgabe für Programmieren. Ich bin in der 11. Klasse auf einer Fachoberschule und ich muss unter anderem diese Aufgabe lösen:

Ein Dreieck sei durch die Koordinaten seiner Eckpunkte gegeben. Gesucht ist ein Programm, welches entscheidet,
ob ein gegebener Punkt im Inneren, auf dem Rand oder außerhalb des Dreiecks liegt.

Jetzt ist mein Problem, dass ich nicht einmal weiß wie ich überhaupt ausrechne ob ein Punkt im Inneren, auf dem Rand oder außerhalb eines gegebenen Dreiecks liegt.
Habt ihr da vllt. eine Idee?
Wir sind momentan in der C++ Konsolenprogrammierung.
Bin für jede Antwort dankbar.

Mit freundlichen Grüßen
Felix
Mitglied: chefkochbln
12.06.2007 um 19:34 Uhr
Hmmmm, also ich würde das so machen:

Du musst doch - wenn ich dich richtig verstanden habe - die Koordinaten für die Eckpunkte angeben, richtig? Und das Ganze spielt sich ja im zweidimensionalen Raum auf (also das Dreieck ist durch die Punkte X1/Y1, X2/Y2 und X3/Y3 gegeben).

Lies doch die drei Punkte in Arrays ein. Danach kannst du u.U. noch einmal eine Probeausgabe machen, um zu schauen, ob die Punkte richtig in die jeweiligen Arrays eingelesen wurden.
Dann lässt du den vierten Punkt einlesen und vergleichst die Elemente des Arrays mit den vorgegebenen.
Bsp:

Dreieck ABC ist gegeben durch die Punkte A(1/1), B(1/5) und C(4/3).
Wenn du jetzt einen Punkt X(2/2) hast, befindet er sich im Inneren des Dreiecks - richtig? Soviel erst einmal dazu..... verfeinern (Berechnung der Randpunkte etc.) kannst du dann ja immer noch!
Bitte warten ..
Mitglied: problemsolver
12.06.2007 um 20:44 Uhr
Hi!

@chefkochbln
so ganz verstehe ich nicht deinen Ansatz. Würde mich aber dennoch interessieren. Schreib nochmal etwas mehr dazu.

Mein Ansatz wäre, der Weg über die Flächeninhalte von Dreiecken:
1.) Bei 3 gegebenen Eckpunkten des Dreiecks, ist das Dreieck eindeutig durch die Längen der Seiten festgelegt. Somit kannst du den Flächeninhalt des Dreiecks bestimmen.

2.) Zeichne mal dieses Dreieck in ein KO-System. Dann füge auf deinem Blatt 3(...) unterschiedliche Punkte hinzu, wobei einer genau innerhalb des Dreiecks ist.

3.) Verbinde den zu prüfenden Punkt mit jedem Eckpunkt des Dreiecks. Fällt dir etwas auf? Sicherlich oder?

4.) Wie offensichtlich klar ist, kann nur ein Punkt INNERHALB eines Dreiecks liegen, wenn die SUMME der Flächeninhalte der Hilfsdreiecke (ABP,BCP,ACP) gleich des Flächeninhaltes des gegebenen Dreiecks ist. Ein Punkt der außerhalb des Dreiecks liegt, ergibt mit den Eckpunkten des Dreiecks ein vom Flächeninhalt größeres "Gebilde".

5.) Dieses kann man leicht in eine Programmierlogik umsetzen, oder?

Vielleicht noch eine kleine Hilfe: A=0,5*h*g (h= Höhe des Dreiecks, g=Grundseite)
Nimm dir die Strecke AB und den Punkt C. Fälle ein Lot auf die Strecke AB durch den Punkt C und du hast die Höhe.

Gruß

Markus
Bitte warten ..
Mitglied: filippg
13.06.2007 um 00:13 Uhr
4.) Wie offensichtlich klar ist, kann nur
ein Punkt INNERHALB eines Dreiecks liegen,
wenn die SUMME der Flächeninhalte der
Hilfsdreiecke (ABP,BCP,ACP) gleich des
Flächeninhaltes des gegebenen Dreiecks
ist. Ein Punkt der außerhalb des
Dreiecks liegt, ergibt mit den Eckpunkten des
Dreiecks ein vom Flächeninhalt
größeres "Gebilde".

Schöner Ansatz! Auch wenn mir das nicht so "offensichtlich klar" ist... Kleines Problem sind da dann halt noch rundungsfehler, da hat mich mein C++-Compiler schon ganz schön gelinkt (hihi, fast schon ein Wortspiel).
Wer mit Kanonen auf Spatzen schiessen will nimmt einen Punkt-in-Polygon-Test-Algorithmus wie etwa unter http://sidvind.com/wiki/Point-in-polygon:_Jordan_Curve_Theorem (nur leider meldet die Seite gerade einen Datenbankfehler), aber Punkt in Polygon hilft bei jeder Suchmaschine weiter.

Ich hätte das ansonsten gelöst, indem ich für die y-Koordinate des Punktes über die Steigung der Dreiecksseiten die x-Werte der beiden Dreiecksseiten an diesem y-Wert berechnet hätte, und dann mit dem x-Wert des Punktes verglichen hätte (natürlich nur, wenn y-Wert überhaupt innerhalb des Bereiches liegt).

Filipp
Bitte warten ..
Mitglied: chefkochbln
13.06.2007 um 09:17 Uhr
Hi!

@chefkochbln
so ganz verstehe ich nicht deinen Ansatz.
Würde mich aber dennoch interessieren.
Schreib nochmal etwas mehr dazu.

Nun ja, wenn man ein Dreieck in ein Koordinaten-System zeichnet, bildet sich dieses ja aus den jeweilgen Eckpunkten. Diese Eckpunkte besitzen doch im zweidimensionalen Raum eine x-Kompnente und eine y-Komponente.
Das bedeutet: der Punkt A vom Dreieck ABC liegt in einem gewählten Beispiel "1" in x-Richtung und "1" in y-Richtung vom Ursprung entfernt. - Verstanden?

Ich habe bspw. folgendes mal theoretisch ausprobiert: in ein Koordinaten-System habe ich ein Dreieck gezeichnet mit folgenden Punktkoordinaten:

A(1/1)
B(5/1)
C(3/4)

Durch diese drei Punkte ist doch das Dreieck definiert.
Habe ich jetzt einen zu prüfenden Punkt P, welcher die Koordinaten P(3/3) hat, so kann ich doch (auch ohne Programmierlogik) feststellen, dass sich dieser Punkt bspw. innerhalb des Dreiecks ABC befindet.
Das war eigentlich meine Überlegung. Und das umzusetzen, scheint nicht allzu schwer

Gruß Stephan
P.S. Dein Ansatz klingt kompliziert, aber dennoch irgendwie nachvollziehbar.
Bitte warten ..
Mitglied: filippg
13.06.2007 um 13:07 Uhr
[...] so
kann ich doch (auch ohne Programmierlogik)
feststellen, dass sich dieser Punkt bspw.
innerhalb des Dreiecks ABC befindet.

Die Programmierlogik ist aber genau das Problem. Wenn ich mir ein Dreieck und einen Punkt auf ein Stück Papier mahle, so kann ich immer ohne Probleme sagen, ob der Punkt im Dreieck liegt. Der Computer ist da etwas eingeschränkter...
Also ich habe noch nicht verstanden, wie dein Ansatz funktionieren sollte.

Filipp
Bitte warten ..
Neuester Wissensbeitrag
CPU, RAM, Mainboards

Angetestet: PC Engines APU 3a2 im Rack-Gehäuse

(1)

Erfahrungsbericht von ashnod zum Thema CPU, RAM, Mainboards ...

Heiß diskutierte Inhalte
DSL, VDSL
DSL-Signal bewerten (13)

Frage von SarekHL zum Thema DSL, VDSL ...

Switche und Hubs
Trunk für 2xCisco Switch. Wo liegt der Fehler? (9)

Frage von JayyyH zum Thema Switche und Hubs ...

Windows Server
Mailserver auf Windows Server 2012 (9)

Frage von StefanT81 zum Thema Windows Server ...

Backup
Clients als Server missbrauchen? (9)

Frage von 1410640014 zum Thema Backup ...