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

<?php
/**
 * @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;
			}
		}
 
		$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;
	}
 
	/**
	 * 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=0; $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+2) ]))
				){
					$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+1) ] )
					){
						$this->crosses++;
					}
				}
			}
		}
	}
 
	/**
	 *
	 * Sprawdzenie czy $check_point należy do odcinka ($strt_p|$stop_p)
	 * @param array $strt_p	Punkt startowy odcinka
	 * @param array $stop_p 	Punkt końcowy odcinka
	 * @param array $check_point	Sprawdzany punkt
	 */
	protected function pointCrossEdge($strt_p,$stop_p,$check_point){
		return $this->det($strt_p, $stop_p, $check_point) == 0 &&
			min( $strt_p['x'], $stop_p['x'] ) <= $check_point['x'] &&
			$check_point['x'] <= max( $strt_p['x'], $stop_p['x'] ) &&
			min ( $strt_p['y'], $stop_p['y'] ) <= $check_point['y'] &&
			$check_point['y'] <= max( $strt_p['y'], $stop_p['y'] );
	}
 
	/**
	 * Sprawdzenie czy odcinki $strt_p_1-$stop_p_1 i $strt_p_2-$stop_p_2 przecinają się
	 * @param array $strt_p_1	Punkt startowy pierwszego odcinka
	 * @param array $stop_p_1	Punkt końcowy pierwszego odcinka
	 * @param array $strt_p_2	Punkt startowy drugiego odcinka
	 * @param array $stop_p_2	Punkt końcowy drugiego odcinka
	 */
	protected function edgeCrossEdge($strt_p_1,$stop_p_1,$strt_p_2,$stop_p_2){
		return ($this->sng( $this->det($strt_p_1,$stop_p_1,$strt_p_2) ) != $this->sng( $this->det($strt_p_1,$stop_p_1,$stop_p_2) ) &&
				$this->sng( $this->det($strt_p_2,$stop_p_2,$strt_p_1) ) != $this->sng( $this->det($strt_p_2,$stop_p_2,$stop_p_1) ) ||
				$this->pointCrossEdge($strt_p_1,$stop_p_1,$strt_p_2) ||
				$this->pointCrossEdge($strt_p_1,$stop_p_1,$stop_p_2) ||
				$this->pointCrossEdge($strt_p_2,$stop_p_2,$strt_p_1) ||
				$this->pointCrossEdge($strt_p_2,$stop_p_2,$stop_p_1)
		);
	}
 
	/**
	 * Wyznacznik macierzy kwadratowej stopnia 3
	 * @param array $strt_p
	 * @param array $stop_p
	 * @param array $check_point
	 */
	protected function det($strt_p,$stop_p,$check_point){
		return $strt_p['x'] * ( $stop_p['y'] - $check_point['y'] ) + $stop_p['x'] * ( $check_point['y'] - $strt_p['y'] ) + $check_point['x'] * ( $strt_p['y'] - $stop_p['y']);
		/* druga metoda
		return ($strt_p['x'] * $stop_p['y'] + $stop_p['x'] * $check_point['y'] + $check_point['x'] * $strt_p['y'] - $check_point['x'] * $stop_p['y'] - $strt_p['x'] * $check_point['y'] - $stop_p['x'] * $strt_p['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.

W życiu programisty pojawiają się sytuacje, gdy programowanie styka się bardzo blisko z matematyką, w tym przypadku z geometrią. We wpisie postaram się przedstawić sposób na rozwiązanie problemu przynależności punktu do obszaru wielokąta (opisanego przez zbiór wierzchołków).

Geofencing

Ostatnio mam dość mało czasu na pisanie na blogu. Jest to związane przede wszystkim z lenistwem, a w drugiej mierze z mojego udziału w jednym, ciekawym projekcie. Z owym projektem wiąże się dzisiejszy wpis. W aplikacji tej zaplanowaliśmy ciekawą funkcjonalność: geofencing, czyli:

Geofencing is a term utilized primarily in the corporate world that refers to the practice of limiting mobile employees to a specific geographic location by tracking their whereabouts via the technology of a global positioning system (GPS).

W telegraficznym skrócie polega to na wyznaczeniu bezpiecznego obszaru, po którym może poruszać się urządzenie z zainstalowanym modułem GPS.

Zastosowań jest wiele, począwszy od śledzenia pracowników, po zabezpieczenia przesyłek. Przy wszystkich zastosowaniach pojawia się ta sama potrzeba sprawdzenia, czy raportowany z urządzenia GPS punkt znajduje się w obrębie zdefiniowanego obszaru, czy jest już poza nim. Możliwości sprawdzenia przynależności punktu do wielokąta jest wiele.

Przynależność do figury prostej

W najprostszym przypadku prostokąta sprowadza się do prostego, matematycznego porównania współrzędnych wierzchołków i sprawdzanego punktu. Nie wymaga skomplikowanych obliczeń, tym bardziej geometrycznych. Niestety sposób mało przydatny w realnym zastosowaniu. Kazać użytkownikom rysować prostokąty wzdłuż trasy Warszawa – Moskwa może kwalifikować się na nagrodę Worst UX. Dzielenie narysowanego skomplikowanego wielokąta na małe prostokąty, następnie sprawdzanie przynależności punktu do każdego z nich też nie wydaje się optymalnym rozwiązaniem.

Metody dla dowolnego wielokąta

Przeszukując otchłanie Internetu można napotkać rozważania nad różnymi metodami na rozwiązanie tego zagadnienia. Kilka z nich zebrał Eric Haines w artykule Point in Polygon Strategies.

źródło: erich.realtimerendering.com

Suma kątów

Ta metoda polega na zliczeniu sumy kątów liczonych od sprawdzanego punktu do poszczególnych wierzchołków z bokiem wychodzącym z tego wierzchołka. Jeśli suma tych kątów będzie bliska zeru to punkt będzie poza wielokątem, w przeciwnym wypadku będzie do niego należał. Niestety z powodu wykorzystania funkcji trygonometrycznych, konieczności wyznaczenia prostej od każdego wierzchołka do szukanego punktu i wyliczenia dla nich kątów, jest to metoda bardzo powolna.

Czytaj dalej tutaj (rozwija treść wpisu)
Czytaj dalej na blogu autora...

Zwiń
Czytaj na blogu autora...

Przeglądarka Google Chrome powoli, lecz systematycznie, zdobywa rynek. Wraz z ilością użytkowników przeglądarki rośnie ilość potencjalnych odbiorców rozszerzeń. W przeciwieństwie do Firefoxa, rozszerzenia tworzy się bardzo prosto i nie wymagają one poznawania nowej technologii. Wszystko możemy wykonać w znanym i lubianym JavaScripcie, a o wygląd rozszerzenia zadba HTML oraz CSS.

Rozszerzenie zbudowane jest przede wszystkim z pliku manifestu – manifest.json. Możemy w nim zdefiniować takie elementy jak nazwa rozszerzenia, wersja oraz opis. Ponadto w manifeście zamieszczamy informacje o wszystkich stworzonych przez nas dokumentach HTML, ikonach oraz dodatkowych elementach.

Jednak sam manifest na niewiele się przyda bez chociażby wiersza JavaScript. Tutaj z pomocą przychodzi HTML, przy pomocy którego tworzymy dokumenty wykorzystywane przez rozszerzenie. Pierwszym z nich jest popup, czyli to, co pokaże się w chmurce, po kliknięciu w ikonę rozszerzenia. Kolejnym plikiem jest background page, czyli dokument działający w tle (co oznacza, że działa jako osobny proces). To właśnie background page może reagować na akcje użytkownika, przeglądarki lub strony. Ostatnim dokumentem są opcje pozwalające na dostosowanie rozszerzenia do naszych potrzeb.

Wartym uwagi są również content scripts, czyli skrypt JavaScript, które rozszerzenie może wstrzyknąć bezpośrednio do kodu odwiedzanej strony. Pozwala to na manipulowanie drzewem dom. Ze względów bezpieczeństwa content scripts nie mają dostępu do API rozszerzeń.

I to wszystko. Te kilka plików składa się na rozszerzenie, które może wyświetlać godzinę w chmurce lub łączyć się do zdalnych serwerów w celu pobrania interesujących dla użytkownika treści.

W następnej części serii, zajmiemy się czymś bardziej praktycznym – bliżej poznamy plik manifestu.

Minęło już półtora tygodnia od czasu jak zacząłem moją pracę w Sabre i myślę, że jest to dobry czas by pokusić się o małe podsumowanie tego jakie są moje wrażenia i czy moje oczekiwania, które przedstawiłem w poprzedniej części artykułu w jakimś stopniu miały okazję się spełnić.

Dla przypomnienia, powody, dla których postanowiłem zmienić środowisko z PHP na Javę:

1. Rodzaj projektów – miałem dość projektów typu „strona – wizytówka”, portali, cms-ów etc
2. Organizacja pracy – brak sformalizowanego procesu wytwarzania oprogramowania, brak specyfikacji, metodologii etc
3. Zarobki

Czy wobec perspektywy tych trzech powodów, zmiana miała sens ? Jak najbardziej ! Po półtora tygodnia pracy mogę powiedzieć że:

1. Uczestniczę w projekcie a raczej w rozwoju produktu ze skomplikowaną logiką biznesową
2. Proces wytwarzania kodu jest ściśle sformalizowany
3. Oprócz zdecydowanej podwyżki, w stosunku do „PHP-owego okresu mojej kariery”, mam do dyspozycji wiele bonusów (tzw. socjału oraz szkoleń)

Największą różnicą między tym co dotychczas robiłem a tym co teraz robię jest  przede wszystkim rozmach. Realizując projekty PHP-owe dotychczas pracowałem zwykle sam, lub maksymalnie w około 5-cio osobowym zespole, który pracował zwykle w jednym pokoju biurko w biurko.

W obecnej pracy, jestem członkiem działu (nie mylić z oddziałem), który tylko w Polsce liczy ponad 100 osób (w firmie, która tylko w Polsce zatrudnia około 1200 osób), jestem członkiem jednego z 4ech zespołów pracujących nad jednym produktem i bezpośrednio współpracuje z około 20-toma osobami. To dość duża zmiana mentalna.

Jeszcze większą mentalną zmianą jest to, że często się zdarza, że nad jednym „user story” (odpowiednik pojedynczego „ficzera”) pracuje nierzadko z kilkoma osobami. Zmienia to zupełnie sposób pracy i wymaga ciągłej komunikacji, zrozumienia i trzymania się ściśle ustalonych standardów.

Kolejnym faktem, który wiele zmienia, są Unit Testy. Pierwszy raz, rozwijam aplikację, której część biznesowa jest prawie w całości pokryta testami jednostkowymi (bo w przypadku frameworków to jest norma).

Generalnie wiele rzeczy prowadzonych jest „książkowo”, jak np. praca w metodyce Scrum. Codzienne „standupy”, iteracje i ich planowanie – uczestniczę w nich i widzę, że ma to sens.

Wracając do rzeczy czysto programistycznych mogę powiedzieć tyle, że łyknąłem już dość dużo Javy, przede wszystkim wszelakich adnotacji i typów generycznych, sposobu obchodzenia się z projektami – Maven, integracja z IDE, debbugger, Tomcat oraz frameworki JUnit oraz Mockito.

Cały czas tutaj wymieniam plusy i zalety, natomiast nie wspomniałem o kilku rzeczach, które można by nazwać wadami tej roboty. Pierwsze co od razu rzuciło mi się w oczy to dość duża biurokracja – na wstępie musiałem wypełnić 11-stronnicowy formularz. Druga kwestia to niestety nieproporcjonalność wyposażenia mojego laptopa do ogromu projektu (poranny update potrafi trwać nawet  15 minut !) – niestety nawet 4gb ramu i najnowszy Core i5 nie zapewniają w jego przypadku komfortowej pracy.

Czytaj dalej tutaj (rozwija treść wpisu)
Czytaj dalej na blogu autora...

Zwiń
Czytaj na blogu autora...

Kolejna okazja do przetestowania swojej wiedzy z dziedziny HTML, CSS oraz JavaScript. Tym razem zmierzymy się z pytaniami z zakresu HTML5. Test został przygotowany przez serwis js do.it i znajduje się pod adresem http://jsdo.it/event/html5cat/2011/summer/. Jeszcze nie brałem w nim udziału, więc nie mam czym się pochwalić. Jak wam poszło?

P.S. Test wymaga zalogowania z konta Google, Facebooka lub Twittera.