Klasa PHP rozwiązująca problem przynależności punktu do wielokąta

Polygon.class.php
W poprzednim wpisie: Problem przynależności punktu do obszaru wielokąta omówiłem sposoby na sprawdzenie, czy dany punkt należy do obszaru wielokąta rozpiętego na punktach. W tym wpisie przedstawię gotowe rozwiązanie zaimplementowane w PHP.
Problem nie jest zbyt rozległy, zatem rozwiązaniem będzie tylko jedna klasa, oraz krótki przykład pokazujący jak z niej korzystać. Do tego jakieś małe demo.

Test przecięć

Do wykonania testu przecięć potrzebna będzie tablica ze współrzędnymi badanego punktu, oraz tablica współrzędnych (podanych w kolejności) wierzchołków wielokąta. Tablice te przekażemy w konstruktorze.
Ważną rzeczą jest sprawdzenie czy ostatni i pierwszy element tablicy wierzchołków jest taki sam, czyli czy figura się zamyka. Jeśli nie to w konstruktorze uzupełniamy tablicę kopię pierwszego elementu.

Kolejnym etapem jest sprawdzenie czy punkt należy do do jednego z boków wielokąta.
Jeśli powyższe sprawdzenie się nie powiedzie rozpoczynamy właściwą część, tj. sprawdzenie przecięć. W tym celu tworzymy półprostą, tutaj równoległą do osi OX, rozpoczynającą się w sprawdzanym przez nas punkcie, a kończącą się w dowolnym punkcie poza ostatnim punktem wielokąta (najbardziej wysuniętym w kierunku grotu osi OX).

Po utworzeniu półprostej przechodzimy do właściwego badania przecięć. W pierwszej kolejności pod młotek idzie sprawdzenie zawierania się półprostej w jednym z boków wielokąta (rys. 3, rys. 4 w poprzednim wpisie). Aby to sprawdzić musimy przetestować czy kolejne 2 punkty wielokąta należą do tej półprostej. Jeśli tak się zdarzy to sprawdzamy, z którym przypadkiem mamy do czynienia (czy punkty leżą po tej samej, czy po przeciwnych stronach półprostej). Jeśli po przeciwnej – zwiększamy licznik przecięć.

Jeśli półprosta nie zawiera się w boku wielokąta trzeba sprawdzić czy przypadkiem nie przecina jego wierzchołka. Aby to osiągnąć sprawdzamy czy wierzchołek zawiera się w półprostej a zarazem czy poprzedni i następny już nie. Jeśli sprawdzanie się powiedzie to pozostaje rozpoznać, z którą wersją mamy do czynienia (rys. 5, rys. 6 w poprzednim wpisie). W zależności od wyniku, albo zwiększamy licznik przecięć, albo nie. Jeśli natomiast warunek zawierania się wierzchołka nie zostanie spełniony sprawdzamy czy bok wielokąta przecina półprostą, a zarazem poprzedni wierzchołek jej nie przecina, jak również następny.

inPolygon.class.php

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
/**
 * @author Robert *Vokiel* Mikołajuk vokiel@vokiel.com http://blog.vokiel.com
 * @copyright (c) 2011 Robert Mikołajuk
 */
class inPolygon {
	/**
	 * @var	array	$point	Współrzędne prawdzanego punktu
	 */
	protected $point;
	/**
	 * @var	array	$raypoint	Punkt końcowy półprostej od $this->point równoległej do osi OX 
	 */
	protected $raypoint;
	/**
	 * @var	array	$polygon	Tablica współrzędnych punktów
	 */
	protected $polygon;
	/**
	 * @var	int	$crosses	Liczba przecięć odcinków
	 */
	protected $crosses = 0;
 
	/**
	 * 
	 * @param array $point
	 * @param array $polygon
	 */
	public function __construct($point,$polygon){
		$this->point = $point;
		$this->raypoint = array('x' => ($point['x']+1), 'y' => $point['y']); 
		$this->polygon = $polygon;
 
		// jeśli ostatni element nie jest tożsamy z pierwszym, dodajemy go na końcu tablicy
		if ( $this->polygon[0] != $this->polygon[count($this->polygon)-1]){
			array_push($this->polygon,$this->polygon[0]); 
		}
	}
 
	/**
	 * Sprawdzenie czy punkt zawiera się w obszarze
	 * @return bool
	 */
	public function check(){
		// sprawdzenie czy punkt nie należy do jednego z boków wielokąta
		for ($i=0; $i<count($this->polygon); $i++){
			if ( $this->pointCrossEdge($this->polygon[$i],$this->polygon[$i+1],$this->point) ){
				return true;
			}
		}
		if ( $this->setRaypoint() ){
			$this->edgeCross();
		}
		if ($this->crosses % 2 == 1){
			return true;
		}
		return false;
	}
 
	/**
	 * Wyznaczenie punktów półprostej równoległej do osi OX
	 * Współrzędna X punktu P1 musi być większa od największej wpsółrzędnej X wśród wszystkich wierzchołków wielokąta
	 */
	protected function setRaypoint(){
		for ($i=0; $i<count($this->polygon); $i++){
			if ( $this->polygon[$i]['x'] > $this->raypoint['x'] ){
				$this->raypoint['x'] = $this->polygon[$i]['x'];
			}
		}
		$this->raypoint['x'] = $this->raypoint['x']+1;
		return true;
	}
 
	/**
	 * Wyliczenie ilości przecięć półprostej przez odcinki boków wielokąta 
	 * Półprosta zostaje przeprowadzona od badanego punktu w prawo, 
	 * aż za najbardziej wysunięty w prawo punkt wielokąta  
	 */
	protected function edgeCross() {
		// wstawienie na koniec tablicy punktów wielokąta drugiego wierzchołka - dla ułatwienia obliczeń
		array_push($this->polygon,$this->polygon[1]);
		for ($i=1; $i<(count($this->polygon)-1); $i++){
			// Prosta P-P1 zawiera się w boku wielokąta W($i,$i+1) 
			if ($this->pointCrossEdge($this->point, $this->raypoint, $this->polygon[ $i ]) &&
				!$this->pointCrossEdge($this->point, $this->raypoint, $this->polygon[ ($i+1) ]) 
			){
				// Punkt wcześniejszy wielokątea i dalszy leżą po przeciwnej stronie prostej P-P1 - ilość przecięć: 1
				if ($this->sng( $this->det( $this->point, $this->polygon[ $i ], $this->polygon[ ($i-1) ] ) ) != 
					$this->sng( $this->det( $this->point, $this->polygon[ $i ], $this->polygon[ ($i+1) ])) 
				){
					$this->crosses++;
				}
			} else { // Prosta P-P1 nie zawiera się w boku wielokąta
				// Prosta P-P1 zawiera wierzchołek W($i)
				if ($this->pointCrossEdge( $this->point, $this->raypoint, $this->polygon[ $i ] ) &&
					$this->pointCrossEdge( $this->point, $this->raypoint, $this->polygon[ ($i-1) ] ) &&
					!$this->pointCrossEdge( $this->point, $this->raypoint, $this->polygon[ ($i+1) ] )
				){
					// Sprawdzenie położenia wierzhołków sąsiadujących z wierzchołkiem W($i)
					if ($this->sng( $this->det( $this->point, array('x'=>($this->point['x']+1),'y'=>$this->point['y']), $this->polygon[ ($i-1) ] ) ) !==
						$this->sng( $this->det( $this->point, array('x'=>($this->point['x']+1),'y'=>$this->point['y']), $this->polygon[ ($i+1) ] ) )
					){
						$this->crosses++;
					}
				} else {
					// Sprawdzenie czy prosta P-P1 przecina bok wilokąta W($i,$i+1)
					if ( $this->edgeCrossEdge( $this->polygon[ $i ], $this->polygon[ ($i+1) ], $this->point, $this->raypoint) &&
						(!$this->pointCrossEdge( $this->point, $this->raypoint, $this->polygon[ ($i-1) ] ) ||  
							(
								!$this->pointCrossEdge( $this->point, $this->raypoint, $this->polygon[ ($i-2) ] ) &&
								!$this->pointCrossEdge( $this->point, $this->raypoint, $this->polygon[ ($i-3) ] )
							) && (
								$this->sng( $this->det( $this->point, array('x'=>($this->point['x']+1),'y'=>$this->point['y']), $this->polygon[ ($i-1) ] ) ) !==
								$this->sng( $this->det( $this->point, array('x'=>($this->point['x']+1),'y'=>$this->point['y']), $this->polygon[ ($i-2) ] ) )
							)
						) && !$this->pointCrossEdge( $this->point, $this->raypoint, $this->polygon[ ($i+1) ] )
					){
						$this->crosses++;
					}
				}
			}
		}
	}
 
	/**
	 * 
	 * Sprawdzenie czy $check_point należy do odcinka ($start_point|$stop_point) 
	 * @param array $start_point	Punkt startowy odcinka
	 * @param array $stop_point 	Punkt końcowy odcinka
	 * @param array $check_point	Sprawdzany punkt
	 */
	protected function pointCrossEdge($start_point,$stop_point,$check_point){
		return $this->det($start_point, $stop_point, $check_point) == 0 &&
			min( $start_point['x'], $stop_point['x'] ) <= $check_point['x'] &&
			$check_point['x'] <= max( $start_point['x'], $stop_point['x'] ) &&
			min ( $start_point['y'], $stop_point['y'] ) <= $check_point['y'] &&
			$check_point['y'] <= max( $start_point['y'], $stop_point['y'] );
	}
 
	/**
	 * Sprawdzenie czy odcinki $start_point_1-$stop_point_1 i $start_point_2-$stop_point_2 przecinają się
	 * @param array $start_point_1	Punkt startowy pierwszego odcinka 
	 * @param array $stop_point_1	Punkt końcowy pierwszego odcinka 
	 * @param array $start_point_2	Punkt startowy drugiego odcinka 
	 * @param array $stop_point_2	Punkt końcowy drugiego odcinka 
	 */
	protected function edgeCrossEdge($start_point_1,$stop_point_1,$start_point_2,$stop_point_2){
		return ($this->sng( $this->det($start_point_1,$stop_point_1,$start_point_2) ) != $this->sng( $this->det($start_point_1,$stop_point_1,$stop_point_2) ) && 
				$this->sng( $this->det($start_point_2,$stop_point_2,$start_point_1) ) != $this->sng( $this->det($start_point_2,$stop_point_2,$stop_point_1) ) ||
				$this->pointCrossEdge($start_point_1,$stop_point_1,$start_point_2) ||
				$this->pointCrossEdge($start_point_1,$stop_point_1,$stop_point_2) ||
				$this->pointCrossEdge($start_point_2,$stop_point_2,$start_point_1) ||
				$this->pointCrossEdge($start_point_2,$stop_point_2,$stop_point_1)
		);
	}
 
	/**
	 * Wyznacznik macierzy kwadratowej stopnia 3
	 * @param array $start_point
	 * @param array $stop_point
	 * @param array $check_point
	 */
	protected function det($start_point,$stop_point,$check_point){
		return $start_point['x'] * ( $stop_point['y'] - $check_point['y'] ) + $stop_point['x'] * ( $check_point['y'] - $start_point['y'] ) + $check_point['x'] * ( $start_point['y'] - $stop_point['y']);
		/* druga metoda
		return ($start_point['x'] * $stop_point['y'] + $stop_point['x'] * $check_point['y'] + $check_point['x'] * $start_point['y'] - $check_point['x'] * $stop_point['y'] - $start_point['x'] * $check_point['y'] - $stop_point['x'] * $start_point['y']);
		*/ 
	}
 
	/**
	 * Określenie znaku liczby
	 * @param int $x	Liczba
	 * @return int $x
	 */
	protected function sng($x){
		if ( $x == 0 ){
			return 0;
		} else if ( $x > 0){
			return 1;
		} else {
			return -1;
		}
	}
 
}// end of inPolygon class

Na koniec przydałoby się napisać jakieś demo. Wkrótce się pojawi.

 

Przeczytaj także

Komentarze: 7

Dodaj komentarz »

 
 
 

Bardzo ciekawe wpisy. Liczę na to że więcej pojawi się w tym temacie. Sam ostatnio zabrałem się za matematykę z fizyką które są potrzebne przy moim hobbystycznym projekcie (gra w przeglądarce).
Takie przypomnienie bardzo się przydało. Zwłaszcza że niebawem będę musiał zrobić rzecz podobną tylko że dla Canvas w JavaScript.

 

Odpowiedz

 

Demo tej klasy nie dziala poprawnie. Niektore punkty znajdujace sie w wielokacie sa uznawane jako znajdujace sie poza.

Poza tym sama klasa bardzo brzydko napisana…

Oceniam na 2/6.
Widać starania.

 

Odpowiedz

 

Zgadzam się, wpisany domyślnie przykład nie działa. Kiepsko to świadczy o samym programie 🙂

 

Odpowiedz

 

Dzięki za info, rzeczywiście demo było nieaktualne, po ostatnich testach i poprawkach nie zaktualizowałem go.

 

Odpowiedz

 

Bardzo fajny artykuł. Zabrakło mi tylko opisu jak użyć tej klasy. Niestety jestem początkujący w PHP i sam sobie z tym nie poradzę. Przydałyby się źródła plików demo.

 

Odpowiedz

 

Tutaj jest bardzo szybka i prosta wersja algorytmu sprawdzająca przynależność punktu do wielokąta
http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html

 

Odpowiedz

 

正好用到,多谢

 

Odpowiedz

 

Dodaj komentarz

 
(nie będzie publikowany)
 
 
Komentarz
 
 

Dozwolone tagi XHTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
© 2009 - 2016 Vokiel.com
WordPress Theme by Arcsin modified by Vokiel