Mobile GIS

Các bác giúp em cái nào. Cứ góp ý, hỏi, chửi rủa cũng được... Em sắp phải bảo vệ trước hội đồng rồi
Bác nào biết được thuật toán tìm đường thực tế hay được sử dụng nhất là gì không.
Con tìm đường của em dựa trên nền tảng thuật tóan Dijkstra. Tốc độ tốt nhưng cần phải test cả những cái đang được dùng để compare.
 
cái link thứ 2 đây:
http://www.coding4living.com/temp/Draw labels Algorithm 2001-44.pdf

bác ko bao giờ lưu được dữ liệu theo kiểu mapinfo vì mapinfo đã đăng ký bản quyền cho định dạng file rồi.

Thuật toán tìm đường theo mình nghĩ áp dụng trong thành phố mà bạn ko có dữ liệu đường như đường to đường nhỏ thì Dijkstra khá hợp lý.
Tuy nhiên để tăng performance, bác thêm viết thêm 1 cái tool để giảm bớt point đi, chỉ lấy đầu các ngã rẽ thôi.

Còn về phần lưu giữ liệu, bác nói thế chứng tỏ bác chưa xem phần oracle spatial rồi, hay bất kỳ 1 sản phẩm nào dù opensource hay commercial, theo mình bác nên nghiên cứu những sản phẩm opensource thật kỹ đi đã, cái gì thiếu thì hãy nghiên cứu thêm vào, đừng sáng chế lại bánh xe nữa.

Mình lấy VD 1 chương trình của mapinfo, bên trong đó topology thì lấy của JIT, thuật toán vẽ của mapinfo, nhưng thuật toán render label lại lấy của 1 hãng khác nữa.

Như vậy để đặt nền móng cho những người đi sau phát triển tiếp hay hỗ trợ cho bác, bác nên làm mọi thứ theo chuẩn, ví dụ như bác làm phần topology ngon thì đã tốt lắm rồi.

Thân,
 
Thuật toán tìm đường em đã cải tiến rồi. Em đã cải tiến như sau :
1. Như bác nói là xét những ngã rẽ
2. Thêm giới hạn biên. Loc bot it nhat 9/10 số đỉnh cần xét. Bac xem sơ sơ cái hình thuyết minh của em chắc cũng hiểu ý tưởng của em :
Gioihanbien.jpg


3. Do em lưu trữ theo kiểu danh sách kề nên thuật toán dijkstra có độ phức tạp n*n xuống còn n (theo lý thuyết O(4*n)=O(n)). Nghe co ve vo ly nhung thuc su la vay. Bác cần em post doan code cua em lên cho bác xem
Em chưa đánh giá cụ thể nhưng con thuat toan tim duong cua em sau khi cai tien tang toc rất nhiều.
Đúng là cái lưu trữ của em vào DB hơi chuối thật, cấu trúc dữ liệu cũng theo ý thích chủ quan. Em đã đọc qua cái link 1 bác đưa cho, em tự tổ chức cũng không khác nó dạy là mấy.
Bác có kinh nghiệm, bác có ở HN không, em muốn gặp bác.
 
Tui cũng ở HN và cũng ở Cầu Giấy, làm GIS 3 năm rồi, bây giờ nghỉ để đi học tiếp. Khi nào anh em đi uống cafe trao đổi tí. Trao đổi thôi chứ mình ko muốn làm nữa.

Thực ra làm software này nếu có 1 team >6 người mới làm được, khoảng 1 năm thì xong. Chỉ có tiền thuê nhân công về code mới được thôi, kiếm người thực sự đam mê mà làm ko có tiền khó lắm.

Cái thuật toán dijkstra nếu rảnh thì bác nghiên cứu thêm phần tối ưu bộ nhớ đi, đảm bảo chạy file lớn vô tư, rất hợp cho PDA.

À còn phần ghi và đọc dữ liệu nhị phân thì đã thành chuẩn hoá rồi, bác làm theo chuẩn thì có thể đọc dữ liệu của các database như mysql spatial, postGIS... vô tư, sau này ko mất công sửa nữa.... Chương trình của mình có thể đọc data của chương trình khác, chương trình khác cũng đọc được data của chương trình mình. Ko chỉ riêng về data tất cả các phần khác cũng có chuẩn luôn, việc mình làm bây giờ chỉ là implement thôi.

Người ta quy định chuẩn để tất cả mọi người phải theo mà.

Ngoài ra bác nên làm theo xu hướng tách phần engine và phần interface ra, sau này rất có lợi.
 
Giả sử như đoạn EF bỏ đi thì sao ?
 

Đính kèm

  • aaa.jpg
    aaa.jpg
    17.2 KB · Lượt xem: 22
Em tính đến chuyện đó rồi. Nếu không có EF, biên k sẽ tự động tăng lên gấp đôi và tiến hành tìm kiếm lại. Nhưng em lấy biên K ban đầu bằng 1,5* trung bình cộng các độ dài các đoạn thì kết quả tìm được trên 95%. Còn lại thì sau khi mở rộng biên đến 2*2*1,5 trung bình là tìm được hết.
Em muốn gặp bác lắm rồi, bác hỏi toàn vào đúng những chỗ em từng trăn trở & mất thời gian giải quyết
 
cái thuật toán của bác áp dụng cho phố cổ thì sẽ phát huy được tác dụng, nếu áp dụng cho cả thành phố sẽ ko phù hợp lắm. Theo mình giữ nguyên thuật toán nguyên bản của nó và thêm phần tối ưu bộ nhớ là OK rồi.
Nên nhớ thuật toán này chỉ áp dụng trong phạm vi nhỏ, càng ít point càng tốt, sau này làm cho toàn thành phố ta phải phân ra đường to đường nhỏ nên thuật toán sẽ biến đổi theo hướng khác, ở đây hướng khác nghĩa là hướng thông mình theo tư duy của con người.

Sẽ upload lên ảnh ví dụ sau nhé
 
Em nghĩ ra cái giới hạn biên cũng nhờ theo suy diễn của con người lúc sử dụng bản đồ. Nhưng mới chỉ dừng lại đến đấy.
Mong anh chỉ giáo thêm.
 
cách tìm kiếm áp dụng trong thành phố mà các chương trình hay áp dụng là từ những đường nhỏ, ngõ nhỏ đi ra đường lớn ngõ lớn.

Trong phần ảnh ví dụ của mình vẫn chưa thực sự rõ ràng lắm nhưng cũng tạm đủ hỉêu, giả sử ta đi từ A đến B. Nếu tìm đường ngắn nhất chắc chắn nó sẽ chỉ theo đường Đê La Thành -> Khâm Thiên, nhưng ngừời đi thường đi theo đường Kim Mã -> Nguyễn Thái Học -> Lê Duẩn

Như vậy, Nếu giữ nguyên thuật toán cho cả thành phố chương trình sẽ chạy tốn nhiều tài nguyên và thời gian. Chính vì thế mà ta phải phân loại đường, giả sử phân làm 2 loại: đường 2 chiều nhỏ (như Đê La Thành) và đường 2 làn đường lớn(như Kim Mã). Vậy thuật toán sẽ được chạy làm 3 lần, lần thứ nhất chỉ áp dụng cho đường lớn, lần thứ 2 áp dụng cho điểm xuất phát tới đường lớn và lần cuối cùng từ đường lớn tới điểm đích.
Số loại đường phân loại tuỳ thuộc vào từng bản đồ cụ thể, ví dụ Hà nội thì theo mình phân ra làm 2 loại là OK, khi nào chạy ngon ta sẽ update lên nhiều loại hơn, càng nhiều loại thì độ chính xác phù hợp với con người càng cao.

Việc phân loại này vừa giảm được points mà kết quả lại sát với thực tế hơn.
Hơn nữa khi chạy Dijk thì 2 lần 100 points luôn luôn nhanh hơn rất nhiều so với chạy 1 lần 200 points. Cái này chắc bác cũng dễ hiểu

Làm dữ liệu cũng ko khó, nửa ngày là OK, HN chỉ có vài trăm con đường thôi, mua 1 tấm bản đồ về là biết đường nào to đường nào nhỏ.
 

Đính kèm

  • aaaaa.JPG
    aaaaa.JPG
    35.6 KB · Lượt xem: 30
Em hiểu ý bác rồi.Hay nhỉ, em thì hồi xưa cũng nghĩ gần giống, em phân bản đồ ra 2 loại đường, đường quan trọng và ko quan trọng. Loại quan trọng là loại đường hay đi, ví dụ như KIM MÃ,cầu giấy, Giai phong ..., tóm lại là nhưng tuyến đường của xe buýt đi. Những tuyến này em lưu sẵn đường đi trong CSDL. Lúc tìm đường giữa 2 diểm bất kì thì em tìm đường từ điểm đó đến các tuyến chính rồi ốp vào. Tuy nhiên sau đó em thấy không khả thi cho khu phố cổ nên thôi. Nhưng nếu tìm xa thì cách đó sẽ cực kỳ hợp lý.
Nếu ghép cả 2 cách vào thì có được ko hả bác, thông thường họ có mấy thuật toán tìm đường trogn 1 chương trình ?
Em sẽ test thử. Nhưng cách này để tìm đường đi hợp lý thì đúng hơn là tìm đường đi ngắn nhất.
 
Em xem con giao dien chương trình của bác rồi. Tên bác đặt đúng là trông đẹp hơn em, Nhưng em ko thể làm thế được. Em ko thể để đường song song như thế trên màn hình hiển thị của PDA. Đã thử và Cực ... xấu.
Do you have any ideal to solve my problem ?
Thanks bác nhé
 
Mình rất khâm phục các bạn đã bỏ nhiều công sức cho miệc lập trình thể hiện bản đồ.
Tuy nhiên mình cảm thấy các bạn bỏ quá nhiều công sức để "phát minh lại cái bánh xe". Các bạn có thể sử dụng các nguồn tư liệu opensource để làm các việc này.
Theo mình nghĩ là chúng ta nên tìm cách đứng trên vai người khổng lồ.
 
Farmer nói:
Mình rất khâm phục các bạn đã bỏ nhiều công sức cho miệc lập trình thể hiện bản đồ.
Tuy nhiên mình cảm thấy các bạn bỏ quá nhiều công sức để "phát minh lại cái bánh xe". Các bạn có thể sử dụng các nguồn tư liệu opensource để làm các việc này.
Theo mình nghĩ là chúng ta nên tìm cách đứng trên vai người khổng lồ.
Nhấn để mở rộng...

đúng đấy, nên làm base trên nó. Tuy nhiên opensource software cho GIS ko được tốt lắm. Thứ 2 là bị rằng buộc về license. Đặc biệt là map-engine của các sp opensource rất tồi.
 
mấy bồ đừng dùng Gps nữa vì trong trường hợp này cho độ chính xác k cao. Nên sài DGps thì hay hơn.
 
DGPS độ chính xác cao hơn GPS nhiều, nhưng ko biết ở VN đã có station nào chưa...
 
Em còn là sinh viên bách khoa trong khoảng 2 tuần nữa, hi hi. Làm eVC đợt này là lần đầu tiên em sờ đến đấy, mà đâu đó cũng chỉ 1 tuần tìm hiểu và 2 tuần code. Đụng đâu có google rồi, ha ha. Nhưng không vướng mắc vì phần hiển thị chỉ là một phần nhỏ mà chương trình dựng bản đồ em làm trên Java đã cover. Bác nhìn cái giao diện chắc đủ biết em chưa rành C mà, nhưng cái lõi thì em nghĩ không tệ bác à.
Mình thì làm gì có station mà DGPS. Mà GPS ở VN độ lệch 10m thì quá tốt cho bản đồ rồi. Cái chính là phải bỏ ra công sức để hiệu chỉnh thôi, tỉ lệ thực tế và tỉ lệ trên bản đò mình có đâu có chính xác, theo phân tích của em thì chỉ sẽ mất thời gian để khớp số liệu thực. Nhưng làm được
À các bác biết vì sao em kiên quyết ko đọc open source ko, vì trước lúc nhận đồ án, em không biết tí gì về GIS, không biết tí gì về eVC, em chỉ muốn xem mình làm được đến đâu, và buiding một hệ thống từ đầu sẽ chuối đến thế nào. Sau này khi làm xong em mới từ từ đọc lại để kiểm chứng. Em nghĩ VN giỏi thì nhiều nhưng điên điên như thế thì ít, nên em làm.
 
Bạn phải đăng nhập hoặc đăng ký để bình luận.
Back
Top