Tematem dzisiejszego wpisu będzie „Przynależność punktu do odcinka”. Wydawać by się mogło, że będzie to coś nudnego. Nie w taki sposób powinno się celebrować artykuł, który zasługuje na miano jubileuszowego. Czy aby na pewno tak jest?

Postanowiłem to sprawdzić i zaryzykować.  Jednak nie masz się czego obawiać, nie będzie tu dziesiątek wzorów i niezrozumiałych teorii. Odpowiem za to na następujące pytania:

  • Jak zaimplementować rozwiązanie za pomocą języka C#?
  • Czym jest odcinek? A czym punkt?
  • Co rozumiemy poprzez „przynależność punktu do odcinka”?
  • Jak za pomocą cyrkla wyznaczyć środek odcinka?

Sam widzisz, że pytania potrafią zaintrygować. Zaczynajmy!

Przynależność punktu do odcinka — wprowadzenie

Na wstępie od razu chcę zaznaczyć, że w niniejszym wpisie muszą pojawić się wzory. Nie masz jednak powodu do paniki — w łagodny sposób Cię przez nie przeprowadzę. Jednak aby rozpocząć nasze dywagacje na temat tego, czy punkt o konkretnych współrzędnych X oraz Y znajduje się na odcinku, warto odpowiedzieć sobie na kilka pytań.

Czym właściwie jest punkt?

Punkt to jedno z tak zwanych pojęć pierwotnych, czyli takich, które uważamy za fundamentalne. Zgodnie z definicją punkt jest obiektem bezwymiarowym i oznaczany jest najczęściej za pomocą kropki oraz podpisywany dużą literą alfabetu łacińskiego.

Pierwsze próby opisania punktu podjął Euklides z Aleksandrii około 300 roku p.n.e. Powiedział on cytowane do dziś zdanie.

Punkt to jest to, co nie składa się z części (czego nie można rozłożyć na części).

Euklides

Punkt spotykamy zarówno w przestrzeni dwu, jak i trójwymiarowej. W przestrzeni euklidesowej będzie on uporządkowany dwiema lub trzema liczbami rzeczywistymi. Punkty możemy również spotkać w przestrzeniach metrycznych, Riemanna,  Łobaczewskiego, Minkowskiego. 

Tyle informacji na temat punktu nam wystarczy. Przejdziemy teraz do drugiej definicji, czyli odcinka.

A czym jest odcinek?

Odcinek to jedno z pojęć matematycznych. Jest to po prostu część prostej zawarta pomiędzy dwoma punktami. Trzeba zapamiętać, że punkty początkowy i końcowy odcinka są jego integralnymi częściami. Na odcinek możemy spojrzeć też z innej strony. Można sobie go wyobrazić jako nieskończenie wielką ilość punktów (nazywana zbiorem punktów) pomiędzy końcami A i B. W przypadku gdy A i B są równe (leżą w tym samym miejscu), wtedy możemy uznać, że odcinek ten nie ma żadnych punktów pomiędzy tymi dwoma i nazywany jest odcinkiem zerowym.

Definicję ze zbiorem punktów między dwoma krańcowymi punktami możemy uznać za oficjalną.  Dodatkowo musi być  spełniony warunek określany wzorem:

ΣA · B = ΣA · x + Σx · B

Wzór ten możemy przedstawić jako długość odcinka AB, równa się sumie odległości od A do x oraz od x do B.

Gdy punkt A = B, to odcinek nazywamy zerowym.

Omawiany odcinek możemy też nazwać odcinkiem metrycznym. Dla formalności dorzucę rysunek.

Odcinek pomiędzy punktami A oraz B
Rysunek 1. Odcinek pomiędzy punktami A oraz B

Odcinek w układzie współrzędnych

Jak wiadomo, najczęściej odcinek kojarzy się z układem współrzędnych. Katowani jesteśmy tym od szkoły podstawowej aż po ostatnie lata studiów, więc wielką niestosownością byłoby nie powiedzieć na ten temat kilku słów.

Wiemy już, że odcinek zawiera się pomiędzy punktami A i B. Na układzie współrzędnych jeden, jak i drugi punkt opisane są dwiema liczbami — odpowiednio x oraz y. 

A = (x1, y1)           B = (x2, y2)

Dzięki parom liczb, które składają się na punkt, możemy w prosty sposób policzyć długość takiego odcinka. 

Wzór na długość odcinka w układzie współrzędnych

Możesz sobie zadać pytanie — z czego taki wzór wynika? Jest to po prostu wyprowadzenie z twierdzenia Pitagorasa, które dotyczy trójkąta prostokątnego ABC. 

Układ współrzędnych z trójkątem prostokątnym
Rysunek 2. Układ współrzędnych z trójkątem prostokątnym

Zgodnie z twierdzeniem Pitagorasa, jeżeli trójkąt jest prostokątny, to suma kwadratów długości przyprostokątnych jest równa kwadratowi długości przeciwprostokątnej. W naszym przypadku przyprostokątnymi będą odcinki AC oraz BC, a przeciwprostokątna to nasz szukany odcinek AB. Poniżej wzory zgodne z tym twierdzeniem.

Wyprowadzenie wzoru na długość odcinka

Przynależność punktu do odcinka — Implementacja

Skoro formalności mamy za sobą i wiemy, czym są zarówno punkt, jak i odcinek, to możemy przejść do napisania prostego programu, który odpowie nam na pytanie, czy na wskazanym odcinku AB znajduje się punkt C. 

Na wstępie zastanówmy się nad założeniami.

Po pierwsze będziemy operować na układzie współrzędnych, dlatego wszystkie punkty — te należące do odcinka AB oraz sprawdzany punkt C — będą zapisywane jako para liczb XY.

Po drugie musimy mieć założenie co do zakończenia programu. Gdy pomyślimy na chłodno, to możemy wywnioskować, że tak naprawdę program kończyć się będzie jednym z trzech stanów — punkt nie należy ani do odcinka, ani do prostej, punkt należy do prostej, ale nie do odcinka, i trzeci stan to gdy punkt należy do prostej i do odcinka. Zarówno w drugim, jak i w trzecim przypadku mówimy o współliniowości punktów. Zobacz rysunek poniżej.

Układ współrzędnych a na nim prosta, odcinek i pięć punktów
Rysunek 3. Układ współrzędnych a na nim prosta, odcinek i pięć punktów

Na rysunku obecna jest prosta (kolor szary), odcinek (kolor czerwony) i pięć punktów (kolor brązowy). W naszym programie tylko punkt C3 będzie poprawny, bo tylko on należy do odcinka. W pozostałych dwóch przypadkach punkty do odcinka nie należą.

Opis

Skoro wszystko mamy już jasne, czas przejść do utworzenia programu konsolowego. Zadaniem na start będzie do zadeklarowanych tablic wprowadzić współrzędne punktów A, B i C. Do tego celu użyłem pętli, która wykona się trzy razy i uzupełni tablicę wartościami punktów x oraz y.

Macierz

Teraz czas znów sięgnąć do matematyki i zastanowić się nad wzorem i zmienną wyznacznik. Głównym pojęciem, z którym musimy się zaznajomić to macierz. Jest to nic innego jak układ liczb ułożony w wiersze i kolumny (temat ten poruszałem w tym wpisie). Zgodnie z definicją musimy wiedzieć, że punkt należy do prostej wtedy, gdy specjalnie skonstruowana macierz będzie posiadała wyznacznik równy 0. Czas więc zbudować taką macierz, a następnie stworzyć wzór taki, jaki zaprezentowałem w linii 30.

Zbudujmy więc następującą macierz.

Macierz trzech punktów A, B i C

Jest to nic innego jak nasze punkty A, B oraz C w trójwymiarowej przestrzeni. Trzeci wymiar jest tu odzwierciedlony jako 1 – nie wpłynie to we wzorze na obliczenia. Dzięki temu sprowadziliśmy punkty do drugiego wymiaru. Kolejnym zadaniem — jak to bywa przy macierzach — są operacje po skosie. Najpierw mnożymy trójkę liczb po skosie w dół i sumujemy wynik, a następnie trójki liczb mnożymy i odejmujemy po skosie w górę.

Opis skomplikowany, ale już spieszę z wyjaśnieniem. Najpierw zobacz na pomocnicze dwie linie pod macierzem — są to skopiowane dwa pierwsze wiersze.

Macierz trzech punktów A, B i C z pomocnicznymi dwoma wierszami

Wystarczy teraz od góry po skosie brać wartości i je mnożyć — pierwsza trójka to x1, y2 i 1, druga to x2, y3 i 1, a ostatnia, trzecia to x3, y1 i 1.

Drugim krokiem jest przejście od ostatniego wiersza w górę. Tak mamy pierwszą trójkę x2, y1 i 1, drugą x1, y3 i 1 oraz trzecią x3, y2 i 1.

Otrzymany wzór poniżej.

Wzór na wyznacznik macierzy M

Zakończenie

Możemy pominąć wartość 1 i wyliczyć w naszym programie wyznacznik. Wystarczy sprawdzić dwa warunki. Po pierwsze, czy wyznacznik jest różny od 0. Oznaczać to będzie, że punkt w ogólne nie należy do prostej i odcinka. Po drugie, gdy już okaże się, że wyznacznik równa się zero, możemy sprawdzić, czy leży na wskazanym odcinku. Wystarczy w warunkach opisać sytuację, gdy x i y punktu C zawiera się pomiędzy najniższym i najwyższym X oraz najniższym i najwyższym Y. Warto zwrócić uwagę na to, że w warunku jest znak <= i =>, ponieważ punkt C może leżeć też dokładnie w punkcie A lub B. Na koniec pozostaje opcja numer trzy, czyli punkt leży na prostej, ale poza odcinkiem.

Właściwa implementacja

using System;

// Przynależność punktu do odcinka
namespace Wpis_20___Przynależność_punkty_do_odcinka
{
    class Program
    {
        static void Main(string[] args)
        {
            int determinant; 
            int[] x = new int[3];
            int[] y = new int[3];

            Console.WriteLine("Wprowadź współrzędnych punktów AB.");
            for (int i = 1; i < 4; i++)
            {
                if(i == 1)
                    Console.WriteLine("Punkt A");
                else if (i == 2)
                    Console.WriteLine("Punkt B");
                else
                    Console.WriteLine("Punkt C");

                Console.WriteLine("x = ");
                x[i - 1] = int.Parse(Console.ReadLine());

                Console.WriteLine("y = ");
                y[i - 1] = int.Parse(Console.ReadLine());
            }

            determinant = x[0] * y[1] + x[1] * y[2] + x[2] * y[0] - x[1] * y[0] - x[0] * y[2] - x[2] * y[1];

            if(determinant != 0)
                Console.WriteLine("Punkt nie przynależy do odcinka AB i do prostej");
            else if (
                 (Math.Min(x[0], x[1]) <= x[2]) &amp;&amp; 
                 (x[2] <= Math.Max(x[0], x[1])) &amp;&amp; 
                 (Math.Min(y[0], y[1]) <= y[2]) &amp;&amp; 
                 (y[2] <= Math.Max(y[0], y[1]))
                )
                Console.WriteLine("Punkt przynależy do odcinka AB");
            else
                Console.WriteLine("Punkt nie przynależy do odcinka AB lecz należy do prostej");

            Console.ReadLine();
        }
    }
}

Czy wiesz, że…

Przynależność punktu do odcinka to bardzo ciekawy temat. Mam z nim jeszcze jedno wspomnienie. Pamiętam jak dziś, że w latach młodości i szkoły podstawowej/gimnazjum interesowałem się bardzo intensywnie matematyką — później szkoła średnia była bardziej buntownicza i trochę nie po drodze było mi z nauką ogólnie. 

Mimo mojego buntowniczego charakteru w młodości chodziłem na dodatkowe zajęcia i pamiętam ciekawe ćwiczenie. Polegało ono na narysowaniu dowolnego odcinka i jedynie za pomocą cyrkla wyznaczenie jego środka. Zadanie wydawać by się mogło dość trudne, ale wystarczy to przeanalizować.

Weź kartkę papieru, narysuj odcinek, a następnie za pomocą cyrkla narysuj fragmenty okręgów nad odcinkiem i pod. Ważne, by ostra część cyrkla była najpierw przyłożona do punktu A, a później do punktu B. Dodatkowo rozwartość cyrkla musi być większa od połowy odcinka — najlepiej w przybliżeniu niech to będzie 3/4 odcinka. Po narysowaniu fragmentów okręgu możesz przez skrzyżowane fragmenty przeprowadzić linię prostą. Przetnie ona odcinek dokładnie w połowie! 

Wyznaczenie środka odcinka za pomocą cyrkla
Rysunek 4. Wyznaczenie środka odcinka za pomocą cyrkla

Przynależność punktu do odcinka – Podsumowanie

Założenie moje było takie, że wszystkie tematy — niezależnie, czy będą to wpisy programistyczne, matematyczne czy na luźno — będę przedstawiał w sposób ciekawy. Zauważyłem również pewną prawidłowość w moich wpisach.

O ile temat artykułu jest zwięzły (w przypadku tego wpisu tematem jest „Przynależność punktu do odcinka”), o tyle ja staram się poruszać w nim dużo więcej tematów w obrębie danego zagadnienia. Na przykład wyjaśnienie, czym jest odcinek oraz punkt. Do tego garść ciekawostek, które bardzo się Wam podobają, a mi sprawia dużo radości szukanie ich i analizowanie na potrzeby dodania do artykułu.

Postanowiłem też jeszcze przed wylotem do Tajlandii poruszyć temat nauki matematyki. Będzie kilka ciekawych i znów kontrowersyjnych myśli!

Na koniec zostawiam Ci dwie przyjemne książki do zgłębienia zagadnień matematycznych.

PS. Będę wdzięczny za komentarze pod tym postem!

PS2. Czeka też na Ciebie prezent. Wystarczy, że zapiszesz się na Newsletter poniżej!

PS3. Dołącz do naszej grupy na Facebook!


Subskrybuj

Zapisz się na Newsletter, odbierz NAGRODĘ w postaci e-booka z 10 omówionymi algorytmami pojawiającymi się w pytaniach podczas REKRUTACJI..

Dodatkowo otrzymuj co niedzielę informacje na temat nowych wpisów, wiadomości ze świata IT i matematyki oraz ciekawych wydarzeniach. Nie przegap i dołącz już dziś do 930 osób!.

Źródła

https://sites.google.com/site/infabgc/szybkie-podnoszenie-do-potegi/przynaleznosc-punktu-do-odcinka 
https://brain.fuw.edu.pl/edu/index.php/Fizyka_I_FM/Kinematyka0?action=mpdf
https://pl.khanacademy.org/math/basic-geo/basic-geo-lines/lines-rays/a/lines-line-segments-and-rays-review 
http://www.smrw.lodz.pl/~owsik20/figury.html 
http://www.wiw.pl/matematyka/geometria/geometria_01_03.asp 
Autor

👨‍💻 .NET and Python programming passionate 🏦 Digtial Banking Solutions 🎓 Student 📊 Psychology 📚 Bookworm 🏠 Warsaw

1 Komentarz

  1. Świetny masz styl pisania Mateusz. Bardzo mi się przyjemnie czytało ten artykuł. Nie sądziłem że przynależność punktu do odcinka może być ciekawym tematem. Myliłem się :-).

    Sama implementacja choć nie jest trudna wydaje mi się bardziej zaawansowanym zagadnieniem. Bardzo jestem ciekaw w jakiego typu programach można używać tej wiedzy. Myślę że na pewno w Game Dev.

    Pozdrawiam :-).

Napisz komentarz

Witryna wykorzystuje Akismet, aby ograniczyć spam. Dowiedz się więcej jak przetwarzane są dane komentarzy.