Mobile GIS

[Tư Triều]

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.

 

[c4l]

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,

 

[Tư Triều]

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 :

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.

 

[c4l]

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.

 

[Tư Triều]

Bác xem lại cái cải tiến của em nhé .. Em up hình rồi đáy

 

[c4l]

Giả sử như đoạn EF bỏ đi thì sao ?

 

[Tư Triều]

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

 

[c4l]

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é

 

[Tư Triều]

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.

 

[comart]

anh c4l co' project na`y hay that:
http://www.coding4living.com/index.htm

Sao anh khong la`m tie^'p nhi ? Ra^'t co' trien vo.ng