دانلود با لینک مستقیم و پر سرعت .
1-مقدمه:
نرخ پذیرش جهانی تلفن سیار بسیار وسیع است ودر حالیکه اخیرا"تلفن های همراه عمدتا"برای ارتباطات صوتی مورداستفاده قرار می گیرند حجم داده های ارتباطی در حال افزایش است.با فن آوری هایی از جمله GPRS,2.5G,3Gکاربرمیتواند همیشه هزینه اضافی پرداخت نکرده و پهنای باند هم در حال افزایش است.
با ظهور سیستم ناوبری جهانی ماهواره گالیله وهمچنین پیشرفت های تنظیم قانون از جمله فرمان USE911وپیشرفتهای مشابه در آسیا واروپا موجب افزایش دسترسی توانمندیهای موقعیت یابی شده است.بنابر این یک ساختار زیر بنایی در حال ظهور است که دامنه ای از خدمات موبایل مستقیم در محل را پشتیبانی می کند.
با وجود این سرویس های موبایل به وسایلی منتقل می شوند که به طور معمول بدون صفحه کلید بوده و فقط صفحه نمایش هایی کوچک دارند.بعلاوه ممکن است از این سرویس ها انتظار رود در موقعیت هایی انتقال پیدا کنند که نقطه توجه اصلی کاربر به سرویس نیست بلکه بیشتر فی المثل به ناوبری ایمن در عبور و مرور است.به این دلایل نسبت به یک موقعیت محاسباتی کامپیوتر رومیزی اهمیت بسیار بیشتری دارد که کاربر فقط اطلاعات و سرویس مربوطه را با حداقل تعامل ممکن با سیستم دریافت کند.یک شیوه جهت کسب این مقادیر اطلاعات مطلع ساختن از زمینه کاربر است.یک زمینه احتمالی موقعیت فعلی کاربر است و دیگری مقصد کاربر است.در عین حال دیگری مسیر کاربر از موقعیت فعلی تا مقصد است.تحقیق حاضر بر این موضوع متمرکز شده است.
مسیر ها به دو دلیل قابل توجه هستند نخست عقل سلیم حکم میکند کاربران موبایل به طور معمول به سوی یک
مقصدسفر کنند (به جای این که بی هدف پرسه بزنند)واینکه هنگامی که کاربر از جایی به جایی دیگر میرود اغلب یا به طور معمول مسیر مشابهی را طی می کند.به عنوان مثال یک کاربر به طور معمول از خانه به محل کار میرود.دوم اینکه مسیر ها به عنوان زمینه برای انواع سرویس ها اهمیت دارند.فی المثل سرویسی که از مسیر کاربر اطلاع دارد ممکن است به کاربر در مورد شرایط مسیر هشدار دهد مثلا":ازدحام و ساخت و سازوتصادف های مسیر در حالیکه کاربررا با شرایطی که مربوط به مسیر او نیستند آزار نمی دهد. به عنوان مثالی دیگر ممکن است هنگامی که یک کاربر در مورد محل هایی جالب توجه که مجاور هستند درخواست کند از مسیر ها استفاده میشود.
به ویژه ممکن است یک سرویس به جای اینکه صرفا"رستوران ها و پمپ بنزین های نزدیک موقعیت فعلی کاربر
راپیشنهاد کند موقعیت آنها در مسیر را اطلاع دهد .همچنین میتوان از اطلاعات مسیر های کاربران موبایل در خدمات رد گیری استفاده کرد تا موفق به ردگیری موثر تر کاربران شوند .
اهداف تحقیق:
این تحقیق تکنیک های اصلی موجود در یک نرم افزار را شرح می دهد تا بر اساس ردگیری موقعیتGPSمسیر های هر کاربر را میسازد. این مسیر ها به عنوان توالی های قسمت های جاده همراه با جهت های رانندگی مدلسازی میشوند ..هرمسیر یک شروع را به یک مقصد متصل مینماید.هر مقصد متعلق به یک کاربر است.مسیرها به وسیله داده های مبنااز جمله زمان های استفاده مربوط میشوند.اطلاعات تجمعی کاربرد هر مسیر نگهداری میشوند.در ساختار سیستم طرح شده یک ایستگاه پردازش کوچک مسئول با کاربر در تعامل است تا اطلاعات فیلتر شده را به سرور بفرستد و واطلاعات را از سرور دریافت کند.ایستگاه های کوچک پردازش توالی های قسمت های جاده را نگهداری نمی کنندزیرا از زیرساخت حمل ونقل نیابت ندارند بلکه بیشتر مسیرها را به مقاصد مورد نظر واطلاعات کاربردی مربوط میکنند .سرور از ارجاع خطی جهت بدست آوردن زیر ساخت موجود در حمل ونقل وبدست آوردن مسیر ها استفاده می کند.این تحقیق سناریوهای ممکن جهت تعامل ایستگاه پردازش- سرور را پوشش میدهد.
در این ساختار کاربران ثبت مسیر را کنترل می کنند .مسائل مربوط به ساختن مسیر حاصل از موقعیت های GPS
تحلیل شدند.الگوریتم هایی که مسائل را حل میکنند بصورت مشروح پوشش داده شدند.این ها شامل الگوریتم هایی
جهت تطبیق نقشه ای, ساخت عناصر مسیر, تقریب عناصر مسیرو پرکردن شکاف ها می باشند.این مولفه با استفاده
ازJAVA,ORACLEPL/SQL, واوراکل فضایی اجرا میشود.اثبات مفهوم آزمایشاتی که از سوابق سیستم موقعیت جهانی استفاده می کنند از وسایل نقلیه موجود دریک منطقه وبا استفاده از یک شبکه جاده ای برای این منطقه بدست آمد.مولفه مطرح شده را میتوان در سیستم های بزرگ مورد استفاده قرار داد که سرویس های موبایل را تدارک می بینند .چنین سیستم هایی میتوانند مسیرهای کاربر را در خواست کنند تا بر مبنای زمان وموقعیت فعلی حرکت او را پیش بینی کنند تا شرایط ترافیکی مربوطه را کنترل کنند , پارکینگ پیدا کنند و... .
ساختار تحقیق:
این تحقیق به صورت زیر ساختار بندی شده است.ساختار سیستم ومولفه ثبت مسیر در بخش دوم شرح داده شده اند.ساختار ضروری داده ها جهت بدست آوردن مسیرهااز جانب سرور در بخش سوم موجود است و والگوریتم های اصلی مورد استفاده این مولفه جهت ثبت مسیرها در بخش چهارم پوشش داده شده اند. اعمال مولفه ثبت مسیردر
بخش پنجم شرح داده شده است.بینش هایی از یک تصدیق آزمایشی در بخش ششم گزارش شده اند. بخش هفتم تحقیق مربوطه را پوشش می دهد وبخش هشتم خلاصه سازی کرده وجهت هایی برای کار آتی پیشنهاد میکند.یک پیوست الگوریتم مسیر یابی مورد استفاده از تکنیک های ارائه شده در قسمت اصلی تحقیق را ارائه می کند.
2.ساختار سیستم
بدنبال یک باز بینی از طرف ایستگاه پردازش و سرور این بخش شرح میدهد که چگونه طرفین طی ثبت مسیر
همکاری کرده وچگونه موارد ثبت شده مسیر در هر دو طرف ایستگاه پردازش وسرور انجام میشوند.
1-2: طرفهای ایستگاه پردازش و سرور
در این ساختار یک ایستگاه پردازش نازک موقعیتهای GPSرا جمع آوری کرده سپس آنها را فیلتر کرده واطلاعات فیلتر شده را به سرور میفرستد.سرور از این اطلاعات جهت ایجاد مسیر استفاده میکند.فرض میکنیم که هر وسیله ایستگاه پردازش دارای یک گیرندهGPS, ارتباط داده ها به سرور, ومحاسبه وذخیره قابلیت های یک تلفن موبایل مدرن تیپیکال می باشد.مثال فعلی نوکیا3650 با یک ارتباط GPS GPRS, و blutooth Emtac است.گیرندگان GPSجملات NMEA را انتقال میدهد.موقعیت/زمان /تاریخ میباشندوهمچنین اطلاعات اضافی که بمنظور اهداف ما دارای اهمیت کمتری میباشند.ایستگاه پردازش اطلاعات شخصی کاربر, کد شناسایی سیستم کاربر ومقاصد ومسیر های کاربر را ثبت میکند.هر موضوع مقصد دارای کد شناسایی محلی – جهانی است.موقعیت به وسیله یک منطقه مدور و با یک توصیف داده میشود.کاربراطلاعات مشخص و نام مقاصد را هنگامی که توسط ایستگاه پردازش در خواست شوند را وارد میکند .این توصیف نامی است که برای کاربر معنی دار است .همچنین هر مسیردارای کد شناسایی محلی- جهانی است.مسیر ها دارای شروع و مقصد های مربوطه و زمان های استفاده میباشند.ولی ایستگاه پردازش بخش هایی از جاده را از مسیر بدست نمی آورند.
سرور اطلاعات در یافت شده از ایستگاه های پردازش را ثبت و آنالیزمیکند .همه چیز های مربوط به مسیر یعنی
قسمت های تشکیل دهنده, شبکه جاده ای, کاربردآن ومقاصد آن همچنین اطلاعات مشخص هر کاربر در سرور ذخیره میشوند.اینکار جهت اجتناب از فقدان اطلاعات انجام میشوند کاربرانی که یک ابزار ایستگاه پردازش جدید گزینش میکنند میتوانند کلیه اطلاعات مربوطه را از سرور بدست آورند.
در حالیکه در این رابطه بحث بیشتری در این تحقیق انجام نمیگیرد معتقدیم که امکان دارد رمزی کردن در پاسخ به نگرانی های حفظ حریم خصوصی مورد استفاده قرار گیرد.
2-2:عاملیت ثبت مسیر
ما نخست تعامل میان کاربر و سرور را پوشش میدهیم وسپس ثبت مسیر را از طرف ایستگاه پردازش وسرور پوشش
میدهیم.
2-2-1تعامل ایستگاه پردازش و سرور
کاربر فرآیند ثبت مسیر را فعال وغیر فعال میکند.هنگام فعال بودن دستگاه ایستگاه پردازش اطلاعات زمانی-موقعیتی حاصل از گیرندهGPS رافیلتر ومیانگین گیری می کند.سر انجام این اطلاعات همراه با اطلاعات در مورد کاربر ومقاصد کاربر منتقل می شوند. توالی انتقال به طول مسیر, توانایی های تکنیکی دستگاه پردازش وکیفیت اتصال بستگی دارد. هنگامی که سروراطلاعات ضروری داشته باشد سرورمسیرسازی را انجام داده وزمان استفاده راثبت کرده وبه مسیر
یک کد شناسایی می دهد.نتیجه در پایگاه داده ها ذخیره شده و به ایستگاه پردازش نیز ارسال میکند
اطلاعات ارسالی به سرور از ایستگاه پردازش از سه قسمت تشکیل شده اند:کاربروموضوع و اطلاعات استاندارد.
فرمت به این بستگی دارد که در که در حال حاضر چه اطلاعاتی موجود است.
اطلاعات کاربر:اگر کاربر ثبت نام کرده باشد, بلوک اطلاعاتی شامل یک IDخواهد بود.برای کاربران جدید شرح
کاربرگنجانده میشود.بنابراین در این بلوک IDکاربر وشرح کاربر را داریم .
اطلاعات موضوع:نقاط شروع و پایان مسیرها موضوعات میباشند.موضوعات مقصد یک مسیر جدید ممکن است در
حال حاضر جهت تعیین نقاط شروع و پایان سایرمسیرها استفاده شود.در این مورد سرور میتواند خودش مطابق با
مختصاتGPSمقصد را تعیین کند.اگر هر دو مقصد ومبدا معلوم باشند این بلوک خالی است و اگر یک مقصد را تعیین کند.اگریک مقصد تعیین شده باشد بلوک حاوی یک شرح مبدا یا مقصد است.اگر نقاط شروع وپایان هنوز تعریف نشده باشند برای هر دو آنها داریم :
اطلاعات استاندارد:اطلاعات موقعیتGPS ،زمان وتاریخ همیشه موجود هستند .این بلوک شامل سه عنصر
GPS]،زمان و تاریخ[ است.
هنگامی که سرور اطلاعات را به یک ایستگاه پردازش میفرستد همیشهIDرا برای یک مسیر که به تازگی ثبت شده
است بر میگرداند.اگر هر یک از پارامتر های مسیر تعریف نشده باشد ایستگاه پردازش فرض میکند که جریان حاصل
از سرور شامل اطلاعات گم شده است.سرور IDها را برای کاربران ایجاد کرده و کاربران موضوعات مقصد را بوجود می آورند.اینIDها به ایستگاه پردازش باز میگردند.
همچنین سرور یک موقعیت مرکزی را برای یک مقصد جدیدا"ثبت شده باز میگرداند در صورتی که موقعیت مرکزی
موضوع با مختصات GPSنخست ونهایی متفاوت باشند.
اگر سرور شعاعی را انتخاب کند که با مقدار تعریف شده متفاوت باشد یک شعاع را همراه با موقعیت مرکز باز میگرداند.
بنابر این از سرورID ]کاربر ،موضوع شروع،موضوع پایان، IDمسیر،مختصات شعاع شروع،مختصات پایان[میباشد
که IDمسیر تنها پارامتری است که همیشه موجود است .ایستگاه پردازش جریان را از سرور دریافت کرده،آنالیز میکندواطلاعات موجود در آن را ثبت میکند.
2-2-2ثبت مسیر از طرف ایستگاه پردازش
ایستگاه پردازش سهم خود را در ثبت مسیر به وسیله آماده سازی یک مسیر که در بخش قبل شرح داده شد ایفا میکندکه به سرور ارسال میشود.بلوک های کاربر موضوع اطلاعات موجود در جریان با استفاده از اطلاعات ذخیره شده ی محلی ساخته میشود.اطلاعات استاندارد بلوک به وسیله آنالیز اطلاعات گیرنده GPSساخته میشوند ترتیب مراحل ثبت مسیر در ابزار ایستگاه پردازش در شکل یک ارائه شده اند.هنگامی که کاربر ثبت مسیر را فعال می سازد و ایستگاه پردازش شروع به کسب اطلاعات از گیرنده GPSمیکند.با دریافت نخستین جفت مختصات ایستگاه پردازش زمان مربوط کاربر ومسیر ثبت شده را حفظ میکند.ایستگاه پردازش به استخراج مختصات از جریان GPSادامه میدهدتا اینکه ثبت کردن غیر فعال شودبا غیر فعال شدن پایان مسیر جهت آنالیز بیشتر مورد توجه قرار میگیرد.نتیجه عبات است از بلوک استاندارد برای جریانی که به سرور ارسال می شود.
اگر کاربر در سیستم ثبت نام کرده باشد IDکاربر به جریان افزوده میشودو در غیر این صورت ایستگاه پردازش در
خواست شرح کاربر را میکند.دستگاه شرح محلی را ثبت کرده،کاربر را به صورت تعریف نشده در جریان قرار داده،
وتوصیف را به جریان می افزاید.
آخرین وظیفه ساختن بلوک موضوع مقصد است اگر موضوعات مبداءو مقصدبه صورت تعریف نشده باشند یا کاربر
جدید باشد ابزار توصیفات را از موضوعات مقصد بدست می آورد.موضوعات مقصد به صورت تعریف نشده در
جریان قرار داده می شوند و توصیفات آنها به جریان افزوده می گردد.دستگاه توصیفات ،شعاع های از پیش تعیین شده و و موقعیت های محلی را همراه با IDمحلی ثبت میکند.اگر فقط یک موضوع مقصد ثبت نشده باشد ،همان مراحل ولی فقط برای یک موضوع انجام میشود .اگر هر دو موضوع مقصد تعریف نشده باشند ،بلوک خالی است.
هنگامی که هر سه بلوک ساخته شد ،مسیر با استفاده از پارامتر های محلی ساخته می شود و پارامتر های کلی تعریف نشده رها میکند.در پایان جریان ها برای سرور ارسال می شوند.
2-2-3ثبت مسیر از طرف سرور
سرور ثبت مسیر اصلی را انجام می دهد که از تبدیل اطلاعات در یافتی از بعضی ایستگاه های پردازش به مسیر معین به وسیله یک توالی قسمتهای شبکه جاده ای می باشد.همچنین یک IDبرای مسیر تولید میشود و هر گونه داده دریافتی از ایستگاه پردازش که موضوعات مقصد را شرح داده وکاربر ثبت کرده را شرح میدهد.
ثبت مسیر از طرف سرور در شکل 2 موجود است.با داشتن اطلاعات حاصل از یک ایستگاه پردازش سرور چک
میکند که کاربر جدید است یا نیست اگر چنین بود سرور شرح کاربر را از جریان دریافت کرده،یک IDبه کاربر
اختصاص داده ،این اطلاعات را ذخیره وIDکاربر را در جریان ارسالی به ایستگاه پردازش می گنجاند.
سپس سرور به بررسی موضوعات مقصد می پردازد .اگر هر دو (مقصد و مبداء) تعریف نشده باشند.سرور اطلاعات
موضوع مقصد را از جریان استخراج ،IDها را ایجاد کرده ،موضوعات مقصد جدید را ثبت وID ها را به جریان
ایستگاه پردازش می افزاید.
اگر فقط یک موضوع مقصد تعریف نشده باشد این مراحل برای یک موضوع انجام میشوند
اگر نقطه شروع معلوم نباشد اطلاعات مربوط به آن تولید شده و ثبت می گردد. سپس موضوع پایانی با استفاده از
آگاهی ها پیرامون موضوعات کاربر تعیین میشوند اگر فقط موضوع مقصد تعیین نشده باشد مراحل مشابه اتخاذ می
گردد. اگر هر دو موضوع مقصد تعیین شده باشند با استفاده از اطلاعات ذخیره شده معین میشوند.
بالاخره سرور قسمت سوم جریان اطلاعات را که شامل اطلاعات استاندارد است را آنالیز میکند سرور مسیر را از
اطلاعات GPS کشف کرده،یک ID برای مسیر ایجاد کرده و این ID را به جریان ارسالی به ایستگاه پردازش می
افزاید و مسیر را در پایگاه داده ها ثبت میکند و اگر مختصات آنها با نقطه شروع یا پایانی جریان GPSمتفاوت باشد
و یا اگر شعاع ها مقادیر از پیش تعیین شده نباشند شعاع آنها را اضافه میکند .سپس سرور اولین زمان کاربرد از
مسیر را ثبت میکند.جریان ساخته شده برای پایان رساندن ثبت مسیر به ایستگاه پردازش ارسال میگردد.
3.مسیرها وشبکه های جاده ای
ما ساختارهای اصلی داده های مورد استفاده جهت بدست آوردن مسیرها در سمت سرور را تعیین کردیم.ما شبکه
واقعی جاده ای را در فضای دو بعدی ترسیم کردیم و نتیجه را بصورت یکسری پلی لاین نمایش دادیم . یک پلی لاین توالی Base Point است که به B c متعلق می با شند.انتخاب Base Point های متفاوت منجر به نمایش شبکه جاده ای متفاوت میشود.به طور کلی،استفاده از Base Point های فراوان منجر به صحت بالاتر میشود. مجموعه پلی لاین ها به صورت تعریف میشود که و به ترتیب نقاط شروع وپایان پلی لاین می باشند .
مثال 3-1 :شکل 3 دو پلی لاین متقاطع را ترسیم کرده است. ( =( و ( =( نقطه شروع ، و نقطه پایان آن است .
در مدل شبکه جاده ای ما هر پلی لاین بیانگر یک جاده دو طرفه است.بدون مراجعه به جهات ترافیکی جاده ها پلی لاین ها دارای "جهت هایی" هستند که از نقطه شروع به Base Point پایانی میرود.
با وجود آنکه شکل جغرافیایی جاده بطور تقریبی در پلی لاین موجود است ،محاسبه فواصل در طول جاده با جمع
فواصل اقلیدسی قسمتها بسیار کم دقت است.به جای آن ما فرض میکنیم فواصل دقیق نقطه شروع به تمام یا بعضی
Base Pointها را در پلی لاین تقریبی جاده داریم ،و این فواصل را به Base Point ها ارتباط میدهیم.این امر تصویر پلی لاین جاده را از بدست آوردن فواصل در طول جاده ،مجزا کرده ومدیریت جاده ای فعلی را حفظ می کند.استفاده از فواصل واقعی جاده محاسبات را دقیق تر می کند.معیار یک Base point ، به صورت داده شده است.این معیار بر آخرین نقطه یک پلی لاین مربوط است.و نشاندهنده طول واقعی جاده ارائه شده توسط پلی لاین می باشد.همیشه مقدار مربوط به اولین Base Point صفر است.اگر یک مقدار برای در پلی لاین موجود نباشد نزدیکترین نقاط Base point قبلی وبعدی با مقادیر مشخص را تعیین میکنیم معیار رابه وسیله میان یابی خطی تقریب میزنیم.
طول واقعی پلی لاین میان نقاط Base point با مقادیر معلوم تقسیم بر فاصله اقلیدسی جاده ما بین این نقاط میشود.این مقدار در فاصله اقلیدسی روی جاده میان دو نقطه با مقدار معلوم و نقطه قبلی با مقدار معلوم ضرب میشود.حاصل به مقدار نقطه پیشین افزوده میشود.اگر وجود نداشت از فاصله اقلیدسی رو بجلو استفاده میکنیم.
مثال 2-3:شکل 4 محاسبه طول base pointهای( pl=( را مثال زده است.اعداد فوق قسمت های خط نشاندهنده فواصل اقلیدسی میان جفت های base pointمیباشند.اعداد زیریbase pointها مقادیر دقیق ترمقایسه شده توسط اطلاعات جاده را نشان میدهند.در شکل 4-الف هنگام محاسبه مقدار برای و i=2وj=4است.
با استفاده از فرمول تایید میشود که=10.4 میباشد.شکل 4bفاقد مقادیر دو base pointپایانی و است.
بمنظور محاسبات طولی از ساختار داده ای Mاستفاده میکنیم که مجموعه متناهی از نقاط سه گانه I،b،plاست که pl є PLیک پلی لاین است.b єBیک base pointاز plاست و l єRمقدار base point ،bروی پلی لاین pl است.
تعریف 1-3 : تابع(طول): Lm :PL×B→R ، شناسه ها را به عنوان یک پلی لاین (b1,…bn)=pl و یک نقطه مبنا bi، 1≤ i ≤ n در نظر می گیرد. تابع ، فاصله راه، از آغاز پلی لاین را به نقطه ی مبناbase poin باز می گرداند.
در این جا ، Lm(pl,b1)=◦ و Lm(pl, bn)، طول پلی لاین است. برای نقاط bi و bj که 1≤i<j≤n ، رابطه Lm(pl, bi) – Lm(pl,bj) حد اقل فاصله اقلیدسی(Euclidation distance) بین bi , bj است. علاوه بر این، اگر Lm(pl,bi)=1 باشد، پس
، به عبارت دیگر، برای هر base pointاز پلی لاین، مقیاس و اندازه ای وجود دارد و تنها یک اندازه را می توان به نقطه مبنا در رابطه با همان پلی لاین متصل کرد.
در مرحله بعدی، یک زیر پلی لاین، بخشی از یک جاده را نمونه سازی می کند( طرح ریزی می کند). یک زیر پلی لاین، سه جمله ای است که حاوی یک خط مبنا و دو عدد واقعی است. عدد واقعی اول نمایانگر فاصله ای است که بر روی آن زیر پلی لاین بر روی پلی لاین آغاز شده است و عدد واقعی دوم نمایانگر فاصله ای است که زیر پلی لاین بر روی پلی لاین خاتمه می یابد.
تعریف2-3 :subpolyline(زیر- چند خطی).
قرار دهید SPL CPL×R² ، مجموعه بی انتهایی از زیر پلی لاین ها را.
یک زیر پلی لاینSPL=(PL , ) ، که در آن 0≤ < ≤Lm (Pl,Bn) است، بخشی از پلی لاین (PL) است که در اندازه آغاز و و در اندازه پایان می یابد.
ارزش نهایی ساب پلی لاین همیشه بزرگتر از ارزش آغازین آن است و اندازه نهایی نمی تواند از اندازه نقطه مبنای نهایی پلی لاین تجاوز کند.
در شکل، قسمت برجسته پلی لاین PL2 ، یک زیر پلی لاین SPL2 است. ما ارتباط بین جاده ها را به دست خواهیم آورد.برای این کار ارتباطی را به صورت مجموعه ای از چند خطی ها، فواصلی که نشانگر محل ارتباط بر روی پلی لاین ویژه می باشند را طراحی می کنیم.
تعریف3-3 : (ارتباط).
قرار دهید:
بنابراین، C مجموعه نامتناهی از رابطه ها است.
شکل الف را نگاه کنید، پلی لاین های PL1 و PL2 هر یک دارای نقطه اتصالی در محل تقاطع خود می باشند. در فاصله از آغاز PL1 ، یک خط اتصال وجود دارد و در فاصله از آغاز PL2 نیز یک نقطه اتصال وجود دارد. بنابراین ما دارای اتصال C={(PL1 , ) , (PL2 , )}ЄC می باشیم. نقاط اتصال در شکل های ب و ج، مشابه هم اند اما شرایطی را نمایان می سازند که در آن نقاط اتصال با نقاط مبنا منطبق می شوند. به خاطر داشته باشید وقتی ما اتصالات را به دست می آوریم، در واقع نمایش نموداری شبکه جاده ای را به دست می آوریم.
همانگونه که قبلاً توضیح داده شد، کاربران خدماتی ما از طریق شبکه جاده ای سفر خود را به مقاصد دیگر یا از مقاصد دیگر آغاز می کنند. این مقصد ها را ما «اشیاء مقصد» (Destination Objects) می نامیم. ما شیء مقصد را به عنوان دایره ای با زیرچندخط هایی می نامیم که داخل دایره وجود دارند. هر شیء مقصد، به یک کاربر مربوط می شود.
تعریف 4-3 (شیء مقصد):
قرار دهید Do را مجموعه بی انتهایی از اشیاء مقصد. هر شیء مقصد، odo є D ، 3 جمله ای (SPLS ، دایره ، U ( است که:
(1) u به U متعلق است، مجموعه کاربران خدماتی.
(2) circle=(xo , yo , rd)ЄR2×R ، دلالت گر دایره تعریف شده از طریق (x-xo)2 + (y-yo)2= rd2 می باشد.
(3) ،
که در آن تابع gєt SPLS ، مجموعه همه زیر چند خط های SPLS که درون دایره وجود دارند را باز می گرداند.
ما می گوییم شیء مقصد do به کاربر u تعلق دارد و در ناحیه دورانی با مرکز (xo , yo) و شعاع rd قرار گرفته است.
به خاطر بسپارید درست است که طراحی اشیاء مقصد به صورت نقاط، ساده تر از طراحی نواحی دورانی است، اما چندان مناسب نیست. برای نمونه، ممکن است هر روز یک کاربر در نواحی مختلف در همان پارکینگ پارک کند و یا حتی در پارکینگ دیگری در نزدیکی محل کار کاربران. بنابراین، مقصد مشابه ممکن است انتهاهای مختلفی داشته باشد و در روزهای مختلف، موقعیت های مختلفی را آغاز کند. به اشیاء مقصد می توان شعاع های مختلفی داد که به الگوهای کاربری و تعداد پلی لاین های اطراف آنها بستگی دارند.
در مرحله بعدی، ما زمان های کاربری به جاده ها ربط می دهیم. برای به دست آوردن ترتیب های کاربری از جاده ها، ما سال، ماه، روز، ساعت، دقیقه و ثانیه هر کاربری را به طور جداگانه به دست می آوریم( به خاطر داشته باشید که زمان کاربری یک جاده، زمان آغاز استفاده از جاده است).
تعریف 5-3 (زمان کاربری):
بگذارید زمان کاربری T مجموعه متناهی از 6 جمله ای (y, m, d, h, m n, s) به ترتیب دلالت گر سال، ماه، روز، ساعت، دقیقه و ثانیه می باشند.
با تعاریف قبلی در خصوص مکان، ما می توانیم مفهوم مسیر را تعریف کنیم. یک مسیر دنباله ای از زیر پلی لاین های متصل به هم می باشد. نیمه پلی لاین اول در یک شیء مقصد آغازین آغاز می شود و انتهاهای نیمه چند خط آخر در شیء مقصد نهایی خاتمه می یابد.
تعریف 6-3 (مسیر):
بگذارید R، مجموعه متناهی از مسیرها باشد، هر مسیر یک 4تایی (RE, dos, doe, ST) است که در آن:
(1) RE=((spl1 , dir1),…,(splN , dirN) ، توالی زیر چند خط هایی با مسیرهای حرکتی مرتبط با هم می باشد. توالی، مسیر را شکل می بخشد. برای عناصر مسیر (spli , diri) که در آن
SPL є spli =(pli , , ) ، diri مسیری حرکتی در طول pli مورد استفاده می باشد:
چنانچه مسیر حرکتی بر روی زیر پلی لاین spli با مسیر پلی لاین pli منطبق شود :1 diri =
و اگر نه :-1
آیتم (1) تضمین می کند که یک مسیر، توالی زیر چند خط هایی است که با مسیرهای حرکتی ارتباط دارند. به یک زیر نیمه خط با یک مسیر حرکتی ارتباطی، عنصر مسیر (route element) می گویند.
آیتم (2) تضمین می کند که عنصر مسیر نخست با شیء مقصد آغازین مرتبط است. عنصر مسیر نخست در صورتی در شیء مقصد آغازین آغاز می شود که مسیر حرکت، 1 باشد( مسیر حرکت پلی لاین نیز باید عدد یک باشد) و عنصر در صورتی در شیء مقصد پایان می یابد که مسیر حرکت 1- باشد( درست عکس حالت پلی لاین).
آیتم (3) تضمین می کند که عنصر مسیر نهایی با شیء مقصد نهایی در ارتباط است. عنصر در صورتی در شیء مقصد نهایی پایان می یابد که مسیر حرکتی 1 باشد(درست مانند مسیر حرکت پلی لاین) و عنصر در صورتی در شیء مقصد نهایی آغاز می شود که مسیر حرکت 1- باشد(عکس مسیر پلی لاین).
آیتم (4) تضمین می کند که عناصر مسیر به هم ربط دارند. یک عنصر مسیر جایی آغاز می شود که عنصر قبلی پایان می یابد: در اتصالی که در آن پلی لاین ها متفاوتند و یا در صورت تعلق عناصر مسیر به همان پلی لاین، در نقطه ای بر روی یک پلی لاین قرار می گیرند. بر اساس تعریف ما از یک پلی لاین، فاصله آغازین باید همیشه کمتر از فاصله انتهایی باشد. بنابراین فواصل آغازین و انتهایی توسط مسیر حرکت تعریف می شوند.
مثال 3-3 : در شکل 6 شبکه جاده ای آمده است که شامل سه پلی لاین ذیل می باشد:
PL1 = (b11, b8, b4, b12)
PL2 = (b1, b2, b3, b4, b)
PL3 = (b6, b2, b7, b8, b9, b10)
مسیر برجسته r =(RE, uos, uoc, ST) از بخش های هر سه پلی لاین استفاده می کند.RE ، توالی 4 عنصر مسیر است. زیر پلی لاین عنصر مسیر اول توسط (PL3, L, Lm(pl3,b2)) تعیین می شود، که در آن L اندازه ای در طول زیرپلی لاینsub poly line است. این زیرپلی لاین نقطه ای را مشخص می کند که به ناحیه دورانی شیء مقصد کاربر uos تعلق دارد. مسیر حرکتی زیر چند خط با مسیر پلی لاین pl3 منطبق است.
4. روش های ساخت مسیر:
نخست روش هایی را ارائه می دهیم که شناسائی کننده چندخطی هائی اند که بر روی آنها یک کاربر حرکت می کند. سپس به معرفی بخش ها و الگوریتم های پوششی چرخشی (turn cover algorithms) می پردازیم و سپس به تعریف ساب پلی لاین هایی که عناصر مسیر هستند که این عناصر در تمامی مسیرها ترکیب می شوند و مسیر را می سازند.
ما بین موقعیت ها و نقاط GPS تمایز ایجاد می کنیم. بنابراین «GPS position» به جملات NMEA حاصل از یک گیرنده GPS نمونه گفته می شود و «GPS point» به جفت مختصات (x , y) که بخشی از موقعیت GPS است اطلاق می گردد. در الگوریتم مختص این قسمت تنها از اطلاعات مربوط به نقطه استفاده می شود، بنابراین، آنها از نقاط GPS استفاده می کنند.
14- : شناسائی پلی لاین:
مرحله اول در ایجاد یک مسیر از داده های دریافت شده از یک مشتری، شناسائی پلی لاین هایی است که بر روی آنها مشتری در حال حرکت است و از طرف دیگر شناسائی موقعیت های مشتری بر روی پلی لاین ها. ما فرض می کنیم که نقاط GPS دقیق نیستند و نقاط GPS در محدوده فاصله D مربوط به موقعیت واقعی هستند.
تصویر نقطه در بخش خط point projection on to line segment:در الگوریتم های بعدی باید یک نقطه GPS در بخش خطی یک پلی لاین project شوند. Project باید به عنوان اندازه ای در طول پلی لاین تعریف شود و فاصله بین نقطه GPS و project آن را باید محاسبه کرد.
در شکل 7 سه حالت برای این project آمده است. پاره خط bibi+1 مشخص شده است و دایره های کوچک نشان گر توالی نقاط GPS می باشند که از میان آنها g ,g1 ,g2، مطلوب می باشند. دایره های بزرگ با شعاع D یا همان maximum بی دقتی مجاز، نشانگر بی دقتی نقاط GPS می باشد. می توان یک نقطه GPS را در طول پاره خط به دست آورد، همانند g در شکل الف. تصویر آن، موقعیت o است و فاصله اقلیدسی بین موقعیت های o و g به صورت d<D می باشد.
مختصات ممکن است قبل یا پس از پاره خط باشد، به طوریکه در شکل ب به صورت g1 و g2 مشخص شده است.
با توضیح مسأله تصویر، اینک می خواهیم به مسأله تصویر کردن نگاه دقیق تری بیندازیم. ما به فاصله d از یک نقطه GPS به تصویر آن نیاز داریم. از این حالت برای تعیین تصویر نقطه GPS در شبکه جاده ای استفاده می کنیم. علاوه بر این، ما به فاصله از آغاز پلی لاین تا تصویر نیاز داریم.
فاصله d را می توان با استفاده از حسابان بردار محاسبه کرد. قرار دهید پاره خط bibi+1 بخشی از یک پلی لاین (b1,…,bn) باشد. پاره خط مسیر پلی لاین را تعیین می کند. با bi که نقطه آغاز است، ما دو بردار داریم که از bi ساطع می شوند. یکی از این بردارها در bi+1 پایان می یابد و دیگر در نقطه GPS (g) (رجوع کنید به شکل8).
از زاویه α بین این بردارها در محاسبه فاصله d استفاده می شود. محاسبه با استفاده از ضرب اسکالر صورت می گیرد:
چنانچه زاویه، منفرجه باشد(شکل الف)، لذا فاصله d فاصله اقلیدسی از نقطه GPS به آغاز پاره خط است. اندازه نقطه project شده، اندازه نقطه آغاز پاره خط است:
چنانچه زاویه حاده باشد، دو احتمال وجود دارد که در شکل ب و ج آمده است. اگر طول تصویر big در 1bibi+ (|big′| )از 1bibi+ تجاوز کند(شکل b)، فاصله d همان فاصله بین نقطه انتهایی bi+1 مربوط به پاره خط و نقطه GPS (g) است. اندازه نقطه تصویر شده، به اندازه نقطه پایانی پاره خط است
چنانچه طول تصویر کمتر از طول پاره خط شکل ج باشد،فاصله d،فاصله عمود از مختصات GPSبه قسمت پلی لاین است.اندازه نقطه تصویر شده،حاصل جمع طول تصویر و اندازه است.
ما محاسبه های انجام شده در بالا را در یک تابع Calc param (رجوع کنید به الگوریتم 1-4) خلاصه بندی می
کنیم. تابع سه جمله ای (g, pl, pls) را به عنوان شناسه در نظر می گیرد و زوج (d , ) را باز می گرداند، در اینجا d فاصله نقطه GPS به پاره خط pls بر روی پلی لاین pl است و اندازه در طول pl مربوط به فراکنش g در pls است.
الگوریتم 1-4: محاسبه پارامتر های تصویر(تابع Calc param).
کار ما بهتر از طراحی نقطه های GPS در نزدیکترین چندخطی با کمترین مقدار d است. برای نمونه، وقتی که نقطه یک GPS نزدیک یک چهارراه است، پلی لاین واقعی، پلی لاین است که از نزدیک پلی لاین عبور می کند. نمونه دیگر زمانی رخ می دهد که جاده ها نزدیک هم باشند. در شکل 9 نشان می دهد که چطور دو نقطه GPS (g2 , g1) در نزدیک ترین حالت به یک جاده نادرست اند. برای بررسی صحیح این موارد، نقاط قبلی GPS را برای نقاط GPS قبلی طراحی می کنیم.
نقطه GPS ابتدایی :برای نقطه GPS اولیه، هیچ داده جمع آوری شده ای، در زمان طراحی آن برای یک پلی لاین وجود ندارد. نقطه GPS ابتدایی در صورتی برای یک پلی لاین طراحی می شود که یک پلی لاین دارای بخشی با فاصله تصویر d ≤ D باشد. اگر چندین پلی لاین های این چنینی وجود داشته باشند، تا زمانی که چند موقعیت دیگر به طور صحیح طراحی نشوند، موقعیت مذکور طراحی نمی شود. تابع «polycand» (به الگوریتم 2-4 رجوع کنید) یک نقطه GPS (g) را به عنوان یک شناسه در نظر می گیرد و مجموعه ای از پلی لاین های نامزد را با اندازه های تصویر g در بخش های پلی لاین بازگشت می دهد.
الگوریتم 2-4: یافتن چندخطی های نامزد(تابع polycand)
تابع، از تابع Calc param استفاده می کند. همه خطوط پاره خط های هر پلی لاین مورد تحلیل قرار گیرند اما تنها پاره خط پلی لاین که نزدیکترین فاصله به نقطه g را دارا می باشد به عنوان کاندیدا انتخاب می شود. تابع از دو متغیر موقتی d و l استفاده می کند. متغیر d فاصله موجود از شروع پلی لاین تا نقطه تصویر شده بر روی نزدیکترین پاره خط را ذخیره می کند.
در خط 5 ، پارامترهای (cd , cl) برای هر پاره خط spli ، محاسبه می شود. اگر فاصله cd تا پاره خط فعلی کمتر یا برابر با مقدار بی دقتی D برابر باشد و برای برخی از پاره خط های قبلی همان پلی لاین کمتر از فاصله d باشد، فاصله فعلی cd در کنار cl و اندازه تصویر ذخیره می شوند(خطوط 8-6). پلی لاین که دارای پاره خط هایی در فاصله بی دقتی از نقطه g می باشد، در فهرست پلی لاین های کاندیدا یا همان Cand گنجانده می شود( رجوع کنید به خطوط 11-10).
نقطه های GPS متعاقب (subsequent GPS points):
در مورد وضعیت های متعاقب، برای به دست آوردن یک نتیجه همسان با طراحی صحیح صورت گرفته در شکل ب، ما نقطه GPS (gi) برای یک پلی لاین با توجه به طراحی نقطه GPS قبلی تعیین می کنیم. نقطه gi را باید برای همان پلی لاین به عنوان gj-1 یا برای چندخطی که از یک نقطه اتصال مشترک با چندخطی قبلی برخوردار است طراحی کنیم.
دوباره به شکل الف توجه کنید، می بینید که چندخطی pl3 نمی تواند به عنوان نامزدی برای طراحی g2 در نظر گرفته شود زیرا به pl2 متصل نیست. برای جلوگیری از انجام طراحی های غلط در اتصالات، به عنوان نمونه طراحی g1 برای pl1، نواحی اتصال را معرفی می کنیم و در درون این نواحی، نقاط GPS را طراحی نمی کنیم. در شکل ج این حالت به تصویر کشیده شده است.
تابع polyId (رجوع کنید به الگوریتم 3-4)
چندخطی pl برای نقطه GPS (g) را طبق چندخطی ppl که نقطه قبلی GPS به آن وصل شده است، شناسائی می کند. تابع، چندخطی و فاصله آغاز چندخطی تا تصویر را باز میگرداند. در خطوط 7-2، ببینید آیا نقطه فعلی GPS بر روی همان جندخطی به عنوان نقطه GPS قبلی هست یا خیر. فاصله CD تا هر بخش از پلی لاین PPL محاسبه می شود و کوتاه ترین فاصله انتخاب می شود اما فاصله باید کمتر از D، ارزش بی قدرتی، باشد. چنانچه این جستجو نتیجه تهی به بار آورد(سطر8)، فرض می کنیم که نقطه GPS باید به گونه ای برای یک چندخطی طراحی شود که به چندخطی قبلی متصل شود. بنابراین، در خطوط 9 تا 21 تابع، به دنبال چندخطی های موجود در محدوده D مربوط به نقطه GPS می گردد و با PPL برخورد می کند. چنانچه بیش از یک چندخطی(خطوط 16 تا 18) و یا اصلاً چندخطی وجود نداشته باشد، تابع، چندخطی تعریف نشده و یک فاصله نامتناهی را باز می گرداند. حالت دوم بدین معناست که در داده های GPS شکافی وجود دارد که باید آنرا پر کرد. اگر دو پاره خط از چندخطی که با PPL قطع می شوند، در محدوده فاصله D مربوط به نقطه GPS باشند(حالت دوم در خط 14) بدین ترتیب نزدیکترین پاره خط انتخاب می شود.
برای تعیین این که آیا یک نقطه GPS در یک ناحیه اتصال قرار دارد، نخست به نتیجه تابع polyId، یعنی چندخطی که GPS در آن تصویر می شود و فاصله تصویر از آغاز چندخطی، نیاز داریم. اتصالات از طریق فاصله موجود از آغاز یک چندخطی(رجوع کنید به تعریف 3-3) مشخص می شوند.
بنابراین اگر تصویر کردن در محدوده فاصله موجود از یک اتصال بر چندخطی خود قرار داشته باشد، نقطه GPS در یک ناحیه اتصال قرار می گیرد. بعداً ما تصویر های این وضعیت ها را مورد توجه قرار نمی دهیم. فاصله ای کمتر از بی دقتی D باعث می شود که نتیجه ای درست به بار آید، وگرنه تابع، نتیجه ای غلط به بار می آورد.
پیچیدگی تابعcalcparamثابت است.تابع polycandقطعات پلی لاین ها را بررسی میکند و پیچیدگی .PLmax)│PL│O( را حاصل میکند.که│PL│اصل واساس مجموعه PLمیباشدو PLmax حد اکثر طول پلی لاین در ترم هایی از شمار base point ها میباشد.تابع possible connection در میان اتصالات ظاهر میشود.و پیچیدگی .Cmax)│C│O(است که│C│اساس مجموعه Cاست و Cmaxحداکثر (تعداد پلی لاینهای دارای مقدار)در یک ارتباط میباشد.پیچیدگی تابع polyId ،
.Cmax + │PL│.PLmax)│C│O(است.به دلیل اینکه در بدترین مورد ،این مقدار در میان همه اتصالات بررسی میکندو قطعات پلی لاین را چک میکند.
4.2شکل عناصر مسیر (جاده)
بیاد آورید که جاده توالی از subpolylineهای مرتبط با مسیر های حرکت و عناصر جاده ای می باشد که بدین گونه برای شکل دادن یک پلی لاین تک ترکیب میشوند.ما برای توضیح دادن اینکه چگونه عناصر جاده ای ساخته شده اند پیش رفتیم. عناصر مسیر به وسیله 4 نوع ساب پلی لاین شکل گرفته اند. که به عنوان مثال در تصویر آمده است و در دنباله توضیح داده شده است . مانند تصاویر قبلی دایره های تو خالی در شکل نقاط GPSرا نشان میدهد.در اینجا 3 پلی لاین ( )و( )و( و مسیر(جاده )اهمیت داده شده است.
تصویر aساده ترین نمونه از مسیر را نشان میدهد. که شامل فقط یک عنصر جاده ای می شود(یک ساب پلی لاین واحد)مطابق مدل ما هرگز نمیتوانیم شروع وپایان جاده را تقریب بزنیم. اما همیشه موقعیت های دقیق آنها را تعیین میکنیم. این به این معنی است که وقتی ما چنین پلی لاینی را شکل می دهیم اولین و آخرین نقاط GPSای را که میتوانند به درستی ترسیم شوند را مورد توجه قرار مید هیم. ( و ( در تصویر a .فاصله ها از شروع پلی لاین ،قسمتی از پلی لاین را که جاده را تشکیل میدهد ،تعیین میکندو مسیر جابجایی شروع و پایان را معین میکند. تصویر b نشان میدهد که چگونه ساب پلی لاین اولین عنصر مسیر شکل گرفته است .برای چنین ساب پلی لاینی اندازه ای که با شروع جاده مشابه است دقیقا"اندازه تصویرنقطه GPSترسیم شده نخست می باشد.
اندازه دیگر ساب پلی لاین باید اندکی تعدیل شود.بنابر این مساوی با اندازه اتصالی که جاده به پلی لاینی متفاوت
تغییر مسیر میدهد،می باشد.برای نشان دادن این مساله ،نقاط GPS ، 0≤ در تصویر در پلی لاین
یکسان طرح شده اند. ،اما نقطه در پلی لاین دیگری طرح شده است.اگر چه مسیر می تواند فقط به پلی
لاین جدید در تغییر مسیر دهد،بنابراین اندازه گیری تصویر به عنوان اندازه نزدیکترین تقاطع با
پلی لاین دیگر تقریب زده میشود (( ) ) .بعدا"تصویر cچگوتگی اینکه آخرین عنصر مسیر
ساب پلی لاین شکل گرفته است را نشان میدهد.این نمونه مشابه است اما به صورت مخالف با مورد اولین
ساب پلی لاین.اگر مسیر حرکت مشابه مسیر پلی لاین باشد ،شروع آخرین ساب پلی لاین در تصویر
تقریب زده می شود.انتهای ساب پلی لاین به وسیله آخرین موقعیت ترسیم شده صحیح جاده یعنی تعیین
میشود.اگر مسیر مخالف باشد،اندازه ها در جهت مخالف شکل میگیرند.سر انجام تصویر dنشان میدهد که
چگونه ساب پلی لاینی از عنصر حد وسط جادهintermediate elementشکل گرفته میشود.این مورد اگر
نقاط GPS مسیر ترسیم شده در بیشتر از 2 پلی لاین ترسیم شده باشند ،رخ می دهد.اندازه شروع و انتهابرای
چنین پلی لاینی اندازه شروع و انتهای طرح ها نیست اما باید با اندازه اتصالات که در آنها مسیر پلی لاین را عوض میکند باید تقریب زده شود.در تصویر ،نقطه GPS و اولین و آخرین نقطه GPSهستند که در پلی لاین وسط ترسیم شده اند. مقادیر فاصله آنها از شروع پلی لاین با مقادیر اتصالات و و...
(( ) )و (( ) ).
اگر هیچ ساب پلی لاین همسایه ای وجود نداشته باشد که متعلق به پلی لاین یکسان باشد،فقط این 4 نمونه وجود دارد.اگر چه ممکن است برای مسیری که ساب پلی لاین های همسایه داشته باشد که متعلق به به پلی لاین یکسان باشد ،اما مسیر های مخالف داشته باشد.این اتفاق اگر کاربر u-turnبسازد رخ میدهد.تصویر aاین مساله را توضیح میدهد.در این نمونه ،انتهای ساب پلی لاین شروعی برای بعدی است.تصویر bجزئیات بیشتری را ارائه میدهدنقاط GPSبرای مشخص شدن ترتیبشان شماره گذاری میشوند. آخرین نقطه که در مسیر یکسان به عنوان ساب پلی لاین جاری می باشد،شروع ساب پلی لاین جدید است. این نقطه GPSمیتواند در جهت یکسان با پلی لاین باشد(قبل از چرخش)و یا در جهت دیگر باشد(بعد از چرخش)
ما یک تابع define direction به کار می بریم.(الگوریتم 4.5را ببینید)که مسیر حرکت در طول یک خط چند گانه (poly line) برای دو طرح متوالی تعیین می شود.
Algorithm 4.5 Direction Identification (function defineDirection)
Require: INPUT: pDst, cDst ∈ R, pDir ∈ {−1, 0, 1} OUTPUT: direction ∈ {−1, 0, 1} 1: direction ← 0
2: if pDst < cDst then
3: direction ← 1
4: else if pDst > cDst then
5: direction←−1
6: else
7: direction ← pDir
8: end if
9: return direction
تابع به عنوان استدلال مقادیر قبلی و فعلی نقاط GPS در طرح قرار می گیرد و همچنین جهت حرکت در خط چند گانه (poly line) تا نقطه قبلی GPS ملاحظه می شود
اگر مقدار قبلی PDST کمتر از مقدار آن در CDST باشد مسیر منطبق بر خط چند گانه و آن را (1) تعیین میکنیم . ولی اگر مقدار قبل بیشتر از مقدار فعلی باشد جهت مسیر مخالف است و باید آن را (1-) در نظرمی گیریم . اگر دو اندازه برابر باشد مسیر با مسیر قبلی منطبق است در آخرین و ضعیت نقاط GPS متوالی که یکسان هستند رخ می دهد مثل وقتی که فردی در ترافیک سنگین قرار دارد و به کندی حرکت می کند .
مسیر های حرکت برای مقادیر تقریبی به کار گرفته می شوند وقتی که ما مسیر های قطع نشدنی از توالی زیر چند گانه ایجاد کرده ایم . .(الگوریتم 4.6را ببینید)
Algorithm 4.6 End Identification for a Subpolyline (function findEnd)
Require: INPUT: pPl, cPl ∈ PL, pDst, cDst ∈ R, pDir ∈ {−1, 0, 1} OUTPUT: endDst ∈ R
1: distThroughConn, endDst←∞ 2: for all ci = {cc1, ..., ccn} ∈ C such that
∃cci j , ccik ∈ ci (cci j = (pPl, i j
) ∧ ccik = (cPl, ik
)) do
3: cDistToConnP ← ( i j − pDst); cDistToConnC ← ( ik − cDst)
4: if (( pDir = 1 ∧ cDistToConnP ≥ −2D)∨
(pDir = −1 ∧ cDistToConnP ≤ 2D))∧
|cDistToConnC| + |cDistToConnP| < distThroughConn then
5: endDst ← i j ; distThroughConn ← |cDistToConnC| + |cDistToConnP|
6: else if pDir = 0 ∧ |cDistToConnC| + |cDistToConnP| < distThroughConn
then
7: endDst ← i j ; distThroughConn ← |cDistToConnC| + |cDistToConnP|
8: end if
9: end for
10: return endDst
تابع (FIND END) اندازه End DSTرادر طول اتصال چند گانه PPL در جایی که اتصال آن و خط چند گانه فعلی CPLتقسیم می شود پیدا می کند . تابع مقادیر PDST نقطه GPS قبلی طرح را و مسیر PDir روی خط چند گانه (poly line) PPL ومقادیر CDST نقطه GPS کنونی طرح را به کار می برد .
تابع اتصالی را که فاصله بین نقطه فعلی و نقطه قبلی را اگر بیشتر از حداقل باشد انتخاب می کند.اما اگر آن بیشتر از یک اتصال باشد در جایی که پلی لاین را قطع می کند انتخاب میکند . نقطه موقتی Dist Through Conn فاصله طرح قبلی از طرح جاری را حفظ می کند .
تمامی اتصالات Ci که PPL و CPL را قطع می کند( در خط دو ) ملاحظه می شود . متغییر های cDist TO Connp و cDist TO Connc به تقریب فاصله از اتصال مناسب به طرح قبلی و فعلی به کار می روند.اتصال در دو مورد مناسب است . ( خط 4 )
- اگر آن باشد در بیشترین 2D پشت نقطه طرح شده ( یعنی به آن اجازه داده شده که رو به جلو باشد ) . وقتی که مسیر منطبق برPOLY Line اش می شود . هنگامی که مسیر مخالف است آن در پشت یا جلو نقطه طرح دو سطر بیشترین فاصله از 2D قرار دارد توجه کنید که cDist To Connp هنگامی که مسیر حرکت pDir (1) است ،منفی خواهد بود اما اتصال در مسیر مخالف pDist ( پشت pDist ) است . همچنین وقتی که مسیر حرکت 1- است واتصال در همان مسیر است( جلو pDist ).
نکته |cDist To Conn p| (|cDist TO Conn c|) : برای بدست آوردن مقدار مثبت برای فاصله در اتصال به کارمی بریم .
اگر فاصله بین نقاط طرح در میان اتصال
cDist To Conn p|+|cDist TO Conn c|) )
کمتر از فاصله میان اتصال قبلی باشد پس اندازه اتصال جدید هست کاندید مقدار آخر برای خط فرعی چند گانه است .اگر مسیر خط فرعی چند گانه تعریف نشده باشد اتصال بلا فاصله حداقل بین نقاط طرح فعلی وقبلی به سادگی بعنوان کاندید انتخاب می شوند .
تابع شروع ( Find Start ) ( الگوریتم 4.7 را ببینید )
Algorithm 4.7 Start Identification for a Subpolyline (function findStart)
Require: INPUT: pPl, cPl ∈ PL, pDst ∈ R
OUTPUT: startDst ∈ R
1: for c = {cc1, ..., ccn} ∈ C such that ∃cck, ccm(cck = (pPl, pDst) ∧ ccm = (cPl, m ))
do
2: startDst ← m
3: end for
4: return startDst
بطور دقیق با تابع( Find end ) مرتبط می شود . خط فرعی چند گانه بعدی جایی که خط فرعی چند گانه قبلی پایان می شود شروع می شود بنا براین تابع FIND START تعریف میکند جایی که خط فرعی چند گانه شروع می شود و تعریف می شود بر اساس خط فرعی چند گانه قبلی که روی خط چند گانه (poly line) PPL و در مقدار pDist تمام شده بود.تابع بهخ شروع DST که فاصلهای است که در آن خط فرعی چند گانه جاری شروع می شود برمی گردد. سرانجام تابع From RE (الگوریتم 4.8 را ببینید.) .
Algorithm 4.8 Route Element Formation (function formRE)
Require: INPUT: pl ∈ PL, ls, le ∈ R
OUTPUT: re = (spl, dir) where spl = ( pl, , ) ∈ SPL, dir ∈ {−1, 1} 1: if ls < le then
2: spl = ( pl, , ) ← ( pl, ls, le); dir ← 1
3: else
4: ← ( pl, le, ls); dir←−1
5: end if
6: return re
عنصر مربوطه خط سیری را ایجاد می کند . خط فرعی چند گانه آنها نیاز خطها چند گانه را ارضا می کنند خصوصا مقدار شروع خط فرعی چند گانه باید کمتر از مقدار پایانی آن باشد .در حالی که محاسبه کردن این ممکن است اتفاق بیفتد وقتی مقدار شروع از مقدار انتهایی آن بیشتر می شود .
تابع From RE این مسئله را حل می کند .تابع خط چند گانه (poly line) مقدار آغازی وپایانی موقتی pl و Ls و Le را بعنوان پارامترهای ورودی می گیرد . به عنصر خط سیر
re=(spl dir) که بطور صحیح در خط چند گانه فرعی , در طول مسیر حرکت ایجاد شده است بر می گردد.
اگر مسیر حرکت منطبق شود با مسیر خط چند گانه یعنی Le>Ls اندازه شروع و پایان نهایی هستند (خطهای 2-1 ) اگر مسیر حرکت ورودی منطبق بر مسیر خط چند گانه (poly line) نباشد یعنی Ls>Le اندازه شروع بزرگتر از اندازه پایانی است وآنها عوض شده اند (خط های 4-3 ) مسیر بر اساس مقادیر شروع و پایانی تعیین می شود (خط های 2و4 ) .تابع های تعریف مسیر From RE مراحل را طی کرده است در زمان ثابت ( دائمی ) در حالی که توابع انتهایی Find و شروع Find داری پیچیدگی O ( | C | . c max) هستند جاییکه | C | تعداد اتصالات است و در این صورت c max کاردینال Cardinal)) یک اتصال می باشد
3-4 ایجاد مسیر
در این بخش ما یک مروری از محتوای ایجاد اساسی یک مسیر که در سحت سرور اتفاق می افتد فراهم کردیم. در اینجا ما برای ایجاد مسیر اقدام به توضیح بعضی از جزئیات می کنیم.ساختار داده ها :
برای گرفتن موقعیت از الگوریتم استفاده می شود . در انیجا ppl خط چند گانه ای است که جدیدترین می باشد. نقطه Gps قبلی با pDst ترسیم شده بود .
pDst فاصله ای از نقطه شروع خط چند گانه برای موقعیت روی خط چندگانه است که ای
