Top-Themen

AppleEntwicklungHardwareInternetLinuxMicrosoftMultimediaNetzwerkeOff TopicSicherheitSonstige SystemeVirtualisierungWeiterbildungZusammenarbeit

Aktuelle Themen (A bis Z)

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, 4109 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.

MfG
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 ..
Ähnliche Inhalte
C und C++
gelöst Wie spreche ich diese Cpp Datei unter CSharp an (1)

Frage von Aicher1998 zum Thema C und C ...

PHP
gelöst PfSense Captive Portal Plus Problem (2)

Frage von wurscht12 zum Thema PHP ...

Neue Wissensbeiträge
Humor (lol)

Wohnt jemand in Belgien und kann nicht mehr ruhig ausschlafen?

(5)

Information von LordGurke zum Thema Humor (lol) ...

Sicherheits-Tools

Trendmicro OSCE und das Fall Creators Update Win10 RS3

(3)

Information von Henere zum Thema Sicherheits-Tools ...

Microsoft Office

Text in Zahlen umwandeln

Tipp von logische zum Thema Microsoft Office ...

Heiß diskutierte Inhalte
Windows Server
Gruppenrichtlinie greift nicht zu! (24)

Frage von Syosse zum Thema Windows Server ...

Hosting & Housing
Mailserver Software Empfehlungen (21)

Frage von sunics zum Thema Hosting & Housing ...

Voice over IP
DeutschlandLAN IP Voice Data M Premium, Erfahrung mit Faxgeräte? (16)

Frage von liquidbase zum Thema Voice over IP ...