Hệ thống thông tin địa lý (gẻogaphic information sýtem – GIS) ra đời trên cơ sở phát triển của khoa học may tính và được ứng dụng rộng rãi trong nhiều nghành khoa học có liên quan đến xử lý dữ liệu không gian

TỔNG QUAN VỀ GIS VÀ BÀI TOÁN QUẢN LÝ MÔI TRƯỜNG

Các khái niệm cơ bản về GIS

Khái niệm Địa lý (Geography) nghiên cứu và mô tả Trái đất (Geo-Earth), thường được sử dụng thay thế cho khái niệm Không gian (Space) trong một số trường hợp Địa lý tập trung vào các mô tả về không gian hai chiều và khí quyển ba chiều của Trái đất, trong khi Không gian cho phép mô tả bất kỳ cấu trúc đa chiều nào mà không cần quan tâm đến vị trí địa lý Do đó, Địa lý có thể được xem như một phần cấu trúc nhỏ trong tổng thể cấu trúc Không gian.

Khi mô tả Trái đất, các nhà địa lý nhấn mạnh mối quan hệ không gian giữa các đối tượng trong thế giới thực, được thể hiện qua các bản đồ Những bản đồ này đồ họa hóa các đặc trưng trừu tượng và quan hệ không gian trên bề mặt Trái đất, chẳng hạn như bản đồ dân số, cho thấy số lượng dân cư tại từng vùng địa lý.

Dữ liệu bản đồ có thể được số hóa và cần được lưu trữ cũng như phân tích thông qua hệ thống thông tin địa lý (GIS).

1.1.1 Một số định nghĩa về hệ thông tin địa lý

Từ viết tắt GIS có nhiều cách diễn giải khác nhau, nhưng tất cả đều tập trung vào việc nghiên cứu thông tin địa lý và các khía cạnh liên quan.

Hệ thống thông tin địa lý (GIS) có khả năng nhập, tìm kiếm và quản lý dữ liệu lưu trữ, cung cấp thông tin cần thiết cho người dùng GIS cho phép lập bản đồ bằng máy tính, cải thiện việc biểu diễn dữ liệu so với phương pháp truyền thống Dưới đây là một số định nghĩa thường gặp về GIS.

• Định nghĩa của dự án The Geographer's Craft, Khoa Địa lý, Trường Đại học Texas

GIS là hệ thống cơ sở dữ liệu số chuyên dụng, sử dụng hệ trục tọa độ không gian làm phương tiện tham chiếu chính Hệ thống này tích hợp các công cụ cần thiết để thực hiện nhiều công việc khác nhau liên quan đến dữ liệu không gian.

- Nhập dữ liệu từ bản đồ giấy, ảnh vệ tinh, ảnh máy bay, số liệu điều tra và các nguồn khác

- Lưu trữ dữ liệu, khai thác, truy vấn cơ sở dữ liệu

- Biến đổi dữ liệu, phân tích, mô hình hóa, bao gồm cả dữ liệu thống kê và dữ liệu không gian

- Lập báo cáo, bao gồm bản đồ chuyên đề, bảng biểu, biểu đồ và kế hoạch

GIS liên quan chặt chẽ đến ứng dụng cơ sở dữ liệu, với thông tin trong GIS được liên kết với tham chiếu không gian Tham chiếu không gian đóng vai trò quan trọng trong việc lưu trữ và truy cập thông tin trong hệ thống GIS.

GIS là công nghệ tích hợp cung cấp khả năng phân tích đa dạng, bao gồm phân tích ảnh máy bay, ảnh vệ tinh, tạo lập mô hình thống kê và vẽ bản đồ Hệ thống GIS hỗ trợ quyết định bằng cách nhập, lưu trữ và phân tích dữ liệu một cách chính xác, phản ánh cách thông tin sẽ được sử dụng trong quá trình lập quyết định hoặc nghiên cứu cụ thể.

• Định nghĩa của David Cowen, NCGIA, Mỹ

Hệ thống Thông tin Địa lý (GIS) bao gồm phần cứng, phần mềm và quy trình nhằm thu thập, quản lý, xử lý, phân tích, mô hình hóa và hiển thị dữ liệu không gian GIS được thiết kế để giải quyết các vấn đề phức tạp trong quản lý và lập kế hoạch.

Một cách đơn giản, có thể hiểu GIS như một sự kết hợp giữa bản đồ (map) và cơ sở dữ liệu (database)

GIS = Bản đồ + Cơ sở dữ liệu

Bản đồ trong GIS là công cụ quan trọng giúp xác định vị trí các địa điểm Kết hợp giữa bản đồ và cơ sở dữ liệu, người dùng có thể truy cập thông tin chi tiết về từng đối tượng tương ứng với địa điểm trên bản đồ Chẳng hạn, khi xem bản đồ các thành phố, người dùng có thể chọn một thành phố để tìm hiểu thông tin như diện tích, dân số, thu nhập bình quân và số quận/huyện của thành phố đó.

1.1.2 Các thành phần của hệ thông tin địa lý

Một hệ thông tin địa lý thường bao gồm 5 thành phần:

Hình 1 1 Thành tố của GIS

- Phương pháp phân tích dữ liệu

Các thành phần này kết hợp với nhau nhằm tự động quản lý và phân phối thông tin thông qua biểu diễn địa lý

Hình 1.2: Mối quan hệ giữa các thành phần của GIS

Con người đóng vai trò quan trọng nhất trong việc vận hành hệ thống GIS, tham gia với nhiều vai trò khác nhau Họ thực hiện các thao tác cần thiết để đảm bảo hệ thống thông tin địa lý hoạt động hiệu quả.

Người xây dựng bản đồ sử dụng nhiều lớp bản đồ từ các nguồn khác nhau để chỉnh sửa dữ liệu, nhằm tạo ra các bản đồ theo yêu cầu.

- Người thiết kế CSDL: xây dựng các mô hình dữ liệu lôgic và vật lý

- Người phát triển: xây dựng hoặc cải tạo các phần mềm GIS để đáp ứng các nhu cầu cụ thể

Người dùng GIS là những cá nhân sử dụng phần mềm GIS để giải quyết các vấn đề không gian theo nhu cầu cụ thể của họ Thông thường, họ là những chuyên gia hoặc những người có trình độ đào tạo cao trong lĩnh vực GIS.

Dữ liệu là thành phần thiết yếu trong một hệ thống thông tin, đóng vai trò là nguồn đầu vào và nguyên liệu cho quá trình phân tích, xử lý, nhằm cung cấp kết quả phục vụ nhu cầu khai thác thông tin của người dùng Trong hệ thống GIS, dữ liệu thường được phân loại thành hai loại chính.

- Dữ liệu không gian (spatial) cho ta biết kích thước vật lý, hình dạng và vị trí địa lý của các đối tượng trên bề mặt trái đất

- Dữ liệu thuộc tính (non-spatial) là các dữ liệu ở dạng văn bản, cung cấp thêm thông tin mô tả về đối tượng dữ liệu không gian

Phần cứng GIS đóng vai trò quan trọng trong việc xây dựng và lưu trữ dữ liệu địa lý, cũng như kết nối các thiết bị khai thác và sử dụng hệ thống để trình bày thông tin địa lý Các thiết bị phần cứng này bao gồm máy tính điện tử như PC, mini computer và smartphone, cùng với các thiết bị mạng cần thiết cho việc triển khai GIS trong môi trường mạng Ngoài ra, GIS còn yêu cầu các thiết bị ngoại vi đặc biệt để nhập và xuất dữ liệu, chẳng hạn như máy số hóa, máy vẽ và máy quét.

Biểu diễn dữ liệu địa lý

1.2.1 Các thành phần của dữ liệu địa lý

Trong GIS, dữ liệu được phân loại thành hai loại chính: thành phần không gian và thành phần phi không gian (thuộc tính) Hai loại dữ liệu này được kết hợp thông qua một chỉ số chung, giúp mô tả một đối tượng thực Sự kết hợp này thể hiện đặc trưng không gian của đối tượng, tạo điều kiện cho việc phân tích và quản lý thông tin địa lý hiệu quả hơn.

- Mô tả “vị trí, hình dạng”: vị trí tham chiếu, đơn vị đo, dạng hình học của thực thể địa lý

- Mô tả “quan hệ và tương tác” giữa các thực thể địa lý: những thửa đất nào liền kề với khu công nghiệp ?

- Mô tả “thông tin” của các đối tượng địa lý: ai là chủ sở hữu của thửa đất này, thuộc quản lý của địa phương nào?

Dữ liệu không gian, hay còn gọi là dữ liệu hình học hoặc dữ liệu bản đồ trong GIS, là thông tin về các đối tượng có vị trí xác định trên bề mặt trái đất Trong hệ thống địa lý, dữ liệu không gian được xây dựng dựa trên một hệ thống tọa độ, bao gồm các tọa độ, quy luật và ký hiệu cần thiết để xác định hình ảnh bản đồ cụ thể trên mỗi bản đồ.

Hệ thống GIS sử dụng dữ liệu không gian để tạo ra bản đồ hoặc hình ảnh bản đồ hiển thị trên màn hình hoặc in ấn Mỗi hệ thống GIS có khả năng tích hợp và phân tích thông tin địa lý, giúp người dùng dễ dàng quản lý và trực quan hóa dữ liệu không gian.

GIS sử dụng nhiều mô hình khác nhau để mô phỏng thế giới thực, giúp giảm thiểu sự phức tạp không gian mà vẫn đảm bảo dữ liệu cần thiết để mô tả chính xác các đối tượng Hệ thống GIS 2D áp dụng ba loại dữ liệu cơ sở để thể hiện các đối tượng trên bản đồ vector.

Điểm được xác định bởi cặp tọa độ (x, y) và thường được sử dụng để mô tả vị trí địa lý của các đối tượng đơn Các đối tượng này chỉ bao gồm thông tin về vị trí, được thể hiện qua các đối tượng điểm.

Các đối tượng được biểu diễn bằng kiểu điểm thường chỉ có tọa độ đơn (x, y) mà không cần thể hiện chiều dài hay diện tích Ví dụ, trên bản đồ, các vị trí như bệnh viện, cây xăng và các điểm kinh tế - xã hội khác có thể được biểu diễn bằng các điểm.

Hình 3 minh họa các vị trí nước ô nhiễm, mỗi điểm trên bản đồ được xác định bởi cặp tọa độ (x, y) Mỗi vị trí này có các thuộc tính như độ sâu và tổng lượng nước bị ô nhiễm, và thông tin này được lưu trữ trong các bảng dữ liệu.

Hình 1 3 Ví dụ biểu diễn vị trí nước bị ô nhiễm

Đường, hay còn gọi là cung, được xác định bởi một dãy các điểm hoặc bởi hai điểm đầu và cuối Nó thường được sử dụng để mô tả các đối tượng địa lý có dạng tuyến, như đường giao thông, sông ngòi, và các tuyến cấp điện, cấp nước.

Các đối tượng được biểu diễn bằng kiểu đường thường có dãy các cặp tọa độ, với các đường bắt đầu, kết thúc hoặc cắt nhau tại các điểm Chẳng hạn, bản đồ hệ thống đường bộ, sông và đường biên giới hành chính thường sử dụng đường để thể hiện, kèm theo các điểm (vertex) nhằm xác định vị trí và hình dáng của chúng.

Hình 1.4 Ví dụ biểu diễn đường

Vùng được xác định bởi một đường gấp khúc, với điểm đầu và điểm cuối trùng nhau Các đối tượng địa lý có diện tích và nằm trong đường gấp khúc thường được thể hiện dưới dạng vùng.

Các đối tượng vùng được mô tả bằng tập hợp các đường bao quanh và điểm nhãn để xác định đặc điểm của từng khu vực, như các khu vực hành chính hay hình dạng các công viên Hình 1.5 minh họa cách lưu trữ đối tượng vùng một cách trực quan.

Hình 1.5 Ví dụ biểu diễn khu vực hành chính

Một đối tượng có thể được thể hiện qua nhiều kiểu khác nhau tùy thuộc vào tỷ lệ của bản đồ Chẳng hạn, một công viên có thể được biểu diễn dưới dạng điểm trên bản đồ tỷ lệ nhỏ, trong khi trên bản đồ tỷ lệ lớn, nó có thể được thể hiện dưới dạng vùng.

 Thành phần phi không gian

Dữ liệu phi không gian, hay còn gọi là dữ liệu thuộc tính, mô tả các đặc tính, số lượng và mối quan hệ của hình ảnh bản đồ với vị trí địa lý thông qua một cơ chế thống nhất Hệ thống GIS cho phép liên kết dữ liệu không gian và phi không gian của cùng một đối tượng, giúp xử lý đồng thời dữ liệu bản đồ và dữ liệu thuộc tính, một trong những chức năng đặc biệt của công nghệ GIS.

Dữ liệu thuộc tính trong hệ thống GIS bất kỳ thường phân thành 4 loại sau:

Bộ xác định là một tập hợp dữ liệu có thể bao gồm số duy nhất, số liên tục, số ngẫu nhiên hoặc chỉ báo địa lý, dùng để xác định vị trí lưu trữ thông tin Nó chứa tọa độ phân bố của thực thể, số hiệu mảnh bản đồ, mô tả khu vực hoặc chỉ dẫn đến vị trí lưu trữ dữ liệu liên quan Thông thường, bộ xác định được lưu trữ kèm theo các bản ghi tọa độ hoặc mô tả khác về hình ảnh không gian và các bản ghi thuộc tính liên quan.

Số liệu hiện tượng và tham khảo địa lý cung cấp thông tin quan trọng về các hoạt động liên quan đến vị trí địa lý cụ thể, như cho phép xây dựng, báo cáo tai nạn và nghiên cứu y tế Những thông tin này được lưu trữ và quản lý trong các tệp hoặc bảng độc lập, với mỗi bản ghi chứa yếu tố xác định vị trí của sự kiện hoặc hiện tượng được quản lý.

Ứng dụng GIS trong bài toán quản lý và cảnh báo ô nhiễm

1.3.1 Các lĩnh vực liên quan với hệ thông tin địa lý

Công nghệ GIS đóng vai trò quan trọng trong nhiều lĩnh vực như bản đồ học, đầu tư, quản lý tài nguyên và tài sản, khảo cổ học, phân tích điều tra dân số, đánh giá tác động môi trường, quy hoạch đô thị và nghiên cứu tội phạm Hệ thống GIS giúp trích xuất thông tin từ dữ liệu địa lý thông qua việc trả lời các câu hỏi cơ bản liên quan đến các lĩnh vực này.

Nhận diện là quá trình xác định tên hoặc thông tin khác của đối tượng thông qua việc chỉ ra vị trí cụ thể trên bản đồ, chẳng hạn như xác định có gì tại tọa độ (X, Y).

- Vị trí (location): Câu hỏi này đưa ra một hoặc nhiều vị trí thỏa mãn yêu cầu

Tọa độ hoặc bản đồ có thể chỉ ra vị trí cụ thể của một đối tượng, hoặc toàn bộ các đối tượng trong khu vực Chẳng hạn, chúng có thể hiển thị vị trí các văn phòng của một công ty trong thành phố.

- Xu thế (trend): Câu hỏi này liên quan đến các dữ liệu không gian tạm thời

Câu hỏi về xu hướng phát triển đô thị đã làm nổi bật chức năng hiển thị bản đồ của GIS, cho phép xác định các khu vực lân cận được xây dựng trong khoảng thời gian từ 1990 đến 2015.

Tìm đường đi tối ưu giữa hai vị trí cụ thể là một nhiệm vụ quan trọng trong hệ thống giao thông, bao gồm cả đường bộ và đường thủy Mục tiêu là xác định lộ trình ngắn nhất hoặc rẻ nhất, giúp tiết kiệm thời gian và chi phí di chuyển Việc áp dụng các thuật toán và công nghệ hiện đại sẽ hỗ trợ trong việc tìm kiếm lộ trình hiệu quả nhất, từ đó nâng cao trải nghiệm di chuyển cho người dùng.

Câu hỏi này liên quan đến mối quan hệ phức tạp giữa khí hậu địa phương và vị trí của các nhà máy cũng như công trình công cộng trong khu vực lân cận, ảnh hưởng đến nhiều tập dữ liệu khác nhau.

Mô hình lập kế hoạch và dự báo đóng vai trò quan trọng trong việc phát triển hạ tầng đô thị Chẳng hạn, khi mở rộng khu dân cư về phía bắc thành phố, cần xác định cách nâng cấp và xây dựng hệ thống mạng lưới giao thông và điện để đáp ứng nhu cầu phát triển.

1.3.2 Những bài toán của GIS

Một số ứng dụng cụ thể của GIS thường gặp trong thực tế bao gồm:

Quản lý và lập kế hoạch mạng lưới giao thông đường bộ đóng vai trò quan trọng trong việc đáp ứng các nhu cầu như tìm kiếm địa chỉ, chỉ dẫn đường đi, phân tích không gian, lựa chọn địa điểm xây dựng và lập kế hoạch phát triển mạng lưới giao thông hiệu quả.

Giám sát tài nguyên thiên nhiên và môi trường đóng vai trò quan trọng trong việc quản lý hệ thống sông ngòi, vùng đất nông nghiệp, thảm thực vật và vùng ngập nước Hoạt động này giúp phân tích tác động môi trường, từ đó đưa ra các giải pháp bảo vệ và phát triển bền vững.

- Quản lý đất đai: giám sát, lập kế hoạch sử dụng đất, quy hoạch…

Quản lý và lập kế hoạch các dịch vụ công cộng bao gồm việc xác định địa điểm lý tưởng cho các công trình công cộng, điều chỉnh tải điện một cách hợp lý và phân luồng giao thông hiệu quả.

- Phân tích, điều tra dân số, lập bản đồ y tế, bản đồ vùng dịch bệnh…

1.3.3 Bài toán của GIS trong quản lý và cảnh báo ô nhiễm môi trường:

Bài viết tổng hợp và phân tích dữ liệu ô nhiễm môi trường từ khu công nghiệp Đồng Văn, cung cấp thông tin về hiện trạng ô nhiễm, đồng thời đề xuất các giải pháp và biện pháp chỉ đạo nhằm ngăn ngừa sự gia tăng ô nhiễm và giảm thiểu tác hại của ô nhiễm đối với môi trường.

Vận dụng hệ thống thông tin địa lý (GIS) để quản lý và cảnh báo ô nhiễm môi trường tại khu công nghiệp Đồng Văn, dựa trên dữ liệu đã thu thập và tổng hợp, là một giải pháp hiệu quả Việc áp dụng GIS giúp phân tích, trực quan hóa và đưa ra những biện pháp kịp thời nhằm giảm thiểu tác động của ô nhiễm, bảo vệ sức khỏe cộng đồng và môi trường.

PHÂN TÍCH KHÔNG GIAN HỖ TRỢ VÀ CẢNH BÁO Ô NHIỄM MÔI TRƯỜNG

Kỹ thuật xây dựng vùng đệm trong GIS

2.1.1 Giới thiệu về xây dựng vùng đệm trong GIS

Logic mờ là công cụ thiết kế hiệu quả cho việc ra quyết định trong không gian Mỗi bước thu thập, lưu trữ và xử lý dữ liệu trong GIS nhằm mô tả khái niệm thực tế Tuy nhiên, kết quả thường không đạt yêu cầu do sự trừu tượng và phức tạp của thế giới thực.

Các hệ thống GIS truyền thống thường gặp phải nhiều hạn chế, ảnh hưởng đến hiệu quả ra quyết định không gian Trước đây, các hệ thống này chủ yếu dựa trên logic kinh điển, gây khó khăn trong việc xác định mô hình phù hợp để mô tả sự biến đổi của môi trường tự nhiên Do đó, việc áp dụng logic mờ trong GIS, hay còn gọi là các Hệ mờ trong GIS, đã được xem xét Logic mờ cung cấp một cơ sở lý thuyết phù hợp với nhiều khái niệm, giúp xử lý dữ liệu không gian hiệu quả hơn và quan sát tính mập mờ trong thông tin, nhận thức và suy nghĩ của con người Điều này trở nên cần thiết để giải quyết các vấn đề thực tiễn trong thế giới hiện đại.

2.1.2 Vùng đệm của điểm dữ liệu

Để xác định tác động của nguồn nước ô nhiễm, cần nhận diện các làng mạc nằm trong bán kính 1 km từ nguồn nước So sánh số người mắc bệnh do ô nhiễm môi trường giữa các làng gần và xa sẽ giúp hiểu rõ hơn về ảnh hưởng của ô nhiễm Nguồn nước ô nhiễm được biểu diễn trên bản đồ như một điểm, và vùng đệm hình tròn có bán kính 1 km được xác định với tâm là tọa độ của nguồn nước Trong vùng đệm này, các làng có người mắc bệnh sẽ được định vị và dữ liệu về vị trí cùng số liệu bệnh nhân sẽ được lưu trữ trong cơ sở dữ liệu địa lý Quy trình thực hiện vùng đệm bao gồm các bước cụ thể để đảm bảo tính chính xác và hiệu quả.

1 Tâm O là toạ độ của nguồn nước và bán kính r cho truớc, ta có đường tròn làm đệm

2 Tìm tất cả các toạ độ của làng mạc có khoảng cách đến tâm O nhỏ hơn r

3 Hiển thị các làng mạc vừa tìm được và có người bị mắc bệnh

2.1.3 Vùng đệm của xâu đoạn thẳng

Giả sử ta có một đoạn đường quốc lộ được tạo bởi các đoạn thẳng như trên

Hai bên đường quốc lộ, các trạm bán xăng dầu được xây dựng để phục vụ nhu cầu của người dân Người lập kế hoạch cần xác định số lượng trạm xăng dầu trong bán kính 500 m từ đường quốc lộ, coi chúng là các tiện ích trong hệ thống Để thực hiện việc này, cần sử dụng chức năng buffering trên bản đồ để xác định vị trí các trạm xăng dầu như các đối tượng điểm.

Hình 2.1 Vùng đệm của xâu đoạn thẳng

Để tạo ra một đa giác bao bọc xung quanh chuỗi các đoạn thẳng, chúng ta cần đảm bảo rằng các cạnh của đa giác này cách đoạn đường một khoảng l được chỉ định Sau khi hoàn thành, nhiệm vụ tiếp theo là xác định các trạm bán xăng nằm trong khu vực của đa giác đó.

Sau đây là thuật toán đã được nghiên cứu và cài đặt để thực hiện buffering:

Vùng đệm của đoạn đường được xác định bởi các điểm P1, P2, P3, P4 tạo thành một đa giác với các điểm P11, P21, , P22, P12, P11 Các điểm này được bố trí cách đều đoạn đường một khoảng b, đồng thời hai nửa đường tròn ở hai đầu đường có bán kính b (ví dụ: 500 m) cũng được tính vào vùng đệm.

1 Tìm các điểm P11, P21, của đa giác Giả sử ta phải tìm điểm P12 cách P1 một khoảng c cho trước như trên Hình 2.2

Xét tam giác vuông tạo bởi các điểm P1, P , P12 Hai điểm P1(x1, y1) và P2(x2,y2) tạo thành đoạn thẳng và có góc  (Theta) được tính từ biểu thức sau: tang  = (y2 - y1) / (x2 - x1)

Từ đó suy ra góc  (Anpha):  = 90 -  b = c / cos  a = c / sin  Vậy điểm P12(x12, y12) có toạ độ: x12 = x1 + b y12 = y1 + a

2 Tìm điểm P22 Cần phải phân biệt hai trường hợp xảy ra ở đây

Hình 2.3 Trường hợp góc tù a) Khi góc tạo bởi hai đoạn thẳng [P1, P2] và [P2, P3] nhỏ hơn 180 (Hình

Toạ độ của điểm P22'(x22', y22') được tính như trên và có: x22' = x2 + b y22' = y2 + a

Tính tương tự cho các điểm P22'' và P32, hai đoạn thẳng từ P12 đến P22' và từ P22'' đến P32 sẽ giao nhau tại điểm P22 Toạ độ giao điểm P22 được xác định theo thuật toán đã trình bày Do đó, các điểm P12 và P22 nằm trong đa giác bao quanh Tương tự, chúng ta cũng xem xét các điểm từ P3 trở đi Khi góc giữa hai đoạn thẳng [P1, P2] và [P2, P3] lớn hơn 180, tình huống sẽ thay đổi.

Hình 2.4 Trường hợp góc bẹt

Các điểm P12, P22', P22'', và P32 được xác định theo quy trình đã mô tả trước đó Để đơn giản hóa quá trình cài đặt và nâng cao tốc độ thực hiện, điểm P22 được tính toán theo một phương pháp cụ thể trong thuật toán này.

Chọn điểm M làm trung điểm của đoạn thẳng P22' và P22'' Nối P2 với M, sau đó chọn điểm P22 trên đường thẳng kéo dài sao cho khoảng cách giữa P2 và P22 bằng c đã cho Như vậy, các điểm P12, P22', P22, P22'', và P32 đều nằm trong đa giác bao quanh.

Các toạ độ được tính cụ thể như sau:

Toạ độ của điểm M: xM = x22'' + (x22' - x22'')/2 y M = y22'' + (y22' - y22'')/2

Xét tam giác tạo bởi các điểm P2, P22 và N, với góc nghiêng của đường thẳng qua hai điểm P2 và M được ký hiệu là  Đoạn thẳng P2, P22 có độ dài c đã cho Các cạnh còn lại của tam giác được tính bằng công thức b = c/cos  và a = c/sin  Do đó, tọa độ của điểm P22 được xác định như sau: x22 = x2 + b và y22 = y2 - a.

3 Vùng đệm của hai đầu của đoạn đường là hai nửa hình tròn như trong

Hình 2.9 với bán kính bằng c và tâm là P1 và P4

4 Tìm những đối tượng điểm là các trạm bán xăng dầu ở trong vùng đệm Công việc này được thực hiện theo hai bước a) Tìm các đối tượng điểm nằm trong đệm của hai đầu đoạn đường, có nghĩa ta tìm các điểm từ cơ sở dữ liệu sao cho toạ độ của chúng cách P1 hoặc P4 một khoảng c cho trước b) Tìm các đối tượng điểm nằm trong đa giác vừa được xác định trên đây Thuật toán xác định một điểm có nằm trong một đa giác hay không được mô tả trong Newsgroups “comp.graphics.algorithms” trên mạng Internet Trong bài báo của mình, ông Anson Tsao có khẳng định: ” Đoạn mã chương trình trong quyển sách Algorithms của Sedgewick là không đúng” Sau đó, ông ta đã giới thiệu thuật toán của Prof Randolph Franklin Trong hệ thống này, để xác định điểm có nằm trong đa giác hay không, có thể sử dụng thuật toán đang đề cập trên vào việc cài đặt bằng ngôn ngữ C như sau:

// Toạ độ của điểm: x,y // Tổng số toạ độ của đa giác: npol // Các toạ độ của đa giác: xp[], yp[]

// Output: c = 1 Điểm đang xét nằm trong đa giác int pnpoly(int npol, float *xp, float *yp, float x, float y) { int i, j, c = 0; for (i = 0, j = npol - 1; i < npol; j = i++) { if((((yp[i]