Jeśli masz okrąg o środku (center_x, center_y)
i promieniu radius
, jak przetestujesz, czy dany punkt o współrzędnych (x, y)
znajduje się w okręgu?
309
Jeśli masz okrąg o środku (center_x, center_y)
i promieniu radius
, jak przetestujesz, czy dany punkt o współrzędnych (x, y)
znajduje się w okręgu?
Odpowiedzi:
Ogólnie rzecz biorąc
x
iy
musi spełniać(x - center_x)^2 + (y - center_y)^2 < radius^2
.Należy pamiętać, że punkty, które spełniają powyższe równanie z
<
zastąpionym przez,==
są uważane za punkty na okręgu, a punkty, które spełniają powyższe równanie z<
zastąpionym przez,>
są uważane za znajdujące się poza okręgiem.źródło
<=
znajdzie punkty wewnątrz koła lub na jego krawędzi.Matematycznie Pitagoras jest prawdopodobnie prostą metodą, o której wielu już wspominało.
Obliczeniowo istnieją szybsze sposoby. Definiować:
Jeśli punkt prawdopodobnie znajduje się poza tym okręgiem, wyobraź sobie narysowany wokół niego kwadrat tak, że jego boki są styczne do tego koła:
Teraz wyobraź sobie kwadratowy diament narysowany wewnątrz tego koła, tak aby jego wierzchołki dotykały tego koła:
Teraz zajęliśmy większość naszej przestrzeni i tylko niewielka część tego koła pozostaje pomiędzy naszym kwadratem a diamentem do przetestowania. Wracamy do Pitagorasa, jak wyżej.
Jeśli punkt jest bardziej prawdopodobne w tym okręgu, odwróć kolejność pierwszych 3 kroków:
Alternatywne metody wyobrażają sobie kwadrat w tym okręgu zamiast diamentu, ale wymaga to nieco więcej testów i obliczeń bez przewagi obliczeniowej (wewnętrzny kwadrat i diamenty mają identyczne obszary):
Aktualizacja:
Dla zainteresowanych wydajnością zaimplementowałem tę metodę w c i skompilowałem z -O3.
Czasy wykonania uzyskałem przez
time ./a.out
Zaimplementowałem tę metodę, metodę normalną i metodę manekina, aby określić narzut czasowy.
Normal: 21.3s This: 19.1s Overhead: 16.5s
Wygląda więc na to, że ta metoda jest bardziej wydajna w tej implementacji.
źródło
inCircleN
używasz niepotrzebnego ABS. Prawdopodobnie bez różnicy ABS pomiędzyinCircle
iinCircleN
byłby mniejszy.Za pomocą Pitagorasa możesz zmierzyć odległość między punktem a centrum i sprawdzić, czy jest on mniejszy niż promień:
EDYCJA (czapka dla Paula)
W praktyce kwadratowanie jest często znacznie tańsze niż pierwiastek kwadratowy, a ponieważ interesuje nas tylko porządkowanie, możemy oczywiście zrezygnować z pierwiastka kwadratowego:
Jason zauważył również, że
<=
należy go zastąpić<
iw zależności od użycia może to mieć senschociaż uważam, że nie jest to prawdą w ścisłym sensie matematycznym. Poprawiono mnie.źródło
**
lub^
. Najszybszy sposób to zrobić, kiedy po prostu trzeba x ^ 2 lub x ^ 3 jest to zrobić „ręcznie”:x*x
.Jest to bardziej wydajne i czytelne. Pozwala to uniknąć kosztownej operacji pierwiastkowej. Dodałem również zaznaczenie, aby ustalić, czy punkt znajduje się w prostokącie ograniczającym okrąg.
Kontrola prostokąta jest niepotrzebna, z wyjątkiem wielu punktów lub wielu okręgów. Jeśli większość punktów znajduje się w okręgach, sprawdzanie prostokąta ograniczającego spowoduje spowolnienie!
Jak zawsze, weź pod uwagę swój przypadek użycia.
źródło
Oblicz odległość
to jest w C # ... konwersja do użycia w python ...
źródło
Należy sprawdzić, czy odległość od środka koła do punktu jest mniejsza niż promień, tj
źródło
Jak wspomniano powyżej - użyj odległości euklidesowej.
źródło
Znajdź odległość między środkiem okręgu a podanymi punktami. Jeśli odległość między nimi jest mniejsza niż promień, wówczas punkt znajduje się wewnątrz okręgu. jeśli odległość między nimi jest równa promieniu koła, wówczas punkt znajduje się na obwodzie koła. jeśli odległość jest większa niż promień, wówczas punkt znajduje się poza okręgiem.
źródło
Poniższe równanie jest wyrażeniem, które sprawdza, czy punkt znajduje się w danym okręgu, gdzie xP i yP są współrzędnymi punktu, xC i yC są współrzędnymi środka koła, a R jest promieniem danego koła.
Jeśli powyższe wyrażenie jest prawdziwe, wówczas punkt znajduje się w okręgu.
Poniżej znajduje się przykładowa implementacja w języku C #:
źródło
Jest to to samo rozwiązanie, o którym wspomniał Jason Punyon , ale zawiera przykład pseudokodu i kilka innych szczegółów. Po napisaniu tego zobaczyłem jego odpowiedź, ale nie chciałem usuwać mojej.
Myślę, że najłatwiej zrozumiałym sposobem jest najpierw obliczyć odległość między środkiem okręgu a punktem. Chciałbym użyć tej formuły:
Następnie po prostu porównaj wynik tej formuły, odległość (
d
), zradius
. Jeśli odległość (d
) jest mniejsza lub równa promieniu (r
), punkt znajduje się wewnątrz koła (na krawędzi koła, jeślid
ir
są równe).Oto przykład pseudokodu, który można łatwo przekonwertować na dowolny język programowania:
Gdzie
circle_x
icircle_y
jest środkowymi współrzędnymi koła,r
jest promieniem kołax
iy
jest współrzędnymi punktu.źródło
Moja odpowiedź w języku C # jako kompletne rozwiązanie do wycinania i wklejania (niezoptymalizowane):
Stosowanie:
źródło
Jak wspomniano wcześniej, aby pokazać, czy punkt znajduje się w okręgu, możemy użyć następujących elementów
Aby przedstawić to graficznie, możemy użyć:
źródło
Użyłem kodu poniżej dla początkujących takich jak ja :).
incirkel klasy publicznej {
źródło
Przechodząc do świata 3D, jeśli chcesz sprawdzić, czy punkt 3D znajduje się w Sferze Jednostkowej, w końcu robisz coś podobnego. Wszystko, co jest potrzebne do pracy w 2D, to użycie operacji wektorowych 2D.
źródło
Wiem, że upłynęło kilka lat od najlepszej głosowanej odpowiedzi, ale udało mi się skrócić czas obliczeń o 4.
Musisz tylko obliczyć piksele z 1/4 koła, a następnie pomnożyć przez 4.
Oto rozwiązanie, do którego dotarłem:
źródło
Oto prosty kod Java do rozwiązania tego problemu:
i matematyka: /math/198764/how-to-know-if-a-point-is-inside-a-circle
źródło
PHP
źródło