Delaunay refinement
জাল উৎপাদনে, ডেলাউনে সংশোধনগুলি জাল উৎপাদনের জন্য অ্যালগরিদম যা একটি ইনপুটের জ্যামিতিতে স্টেইনার পয়েন্ট যুক্ত করার নীতির উপর ভিত্তি করে, এমনভাবে যা ডেলাউনে ত্রিভুজ বা বর্ধিত ইনপুটের সীমাবদ্ধ ডেলাউনে ত্রিভুজকে মেশিং অ্যাপ্লিকেশনের গুণমানের প্রয়োজনীয়তা পূরণ করে। ডেলাউনে পরিশোধন পদ্ধতির মধ্যে রয়েছে চিউ এবং রুপার্টের পদ্ধতি। চিউ-এর দ্বিতীয় অ্যালগরিদম চিউ-এর দ্বিতীয় অ্যালগরিদম একটি পিসওয়াইজ লিনিয়ার সিস্টেম (পি. এল. এস) গ্রহণ করে এবং শুধুমাত্র মানের ত্রিভুজের একটি সীমাবদ্ধ ডেলাউনে ত্রিভুজ প্রদান করে যেখানে গুণ একটি ত্রিভুজের ন্যূনতম কোণ দ্বারা সংজ্ঞায়িত করা হয়। ত্রিমাত্রিক স্থানে এম্বেড করা মেশিং পৃষ্ঠগুলির জন্য এল. পল চিউ দ্বারা বিকশিত, চিউ-এর দ্বিতীয় অ্যালগরিদমটি নির্দিষ্ট কিছু ক্ষেত্রে রুপার্টের অ্যালগরিদমের তুলনায় ব্যবহারিক সুবিধার কারণে দ্বি-মাত্রিক জাল জেনারেটর হিসাবে গৃহীত হয়েছে এবং এটি অবাধে উপলব্ধ ত্রিভুজ প্যাকেজে প্রয়োগ করা ডিফল্ট মানের জাল জেনারেটর। চিউ-এর দ্বিতীয় অ্যালগরিদমটি প্রায় 28.6 ডিগ্রি পর্যন্ত ন্যূনতম কোণ সহ একটি স্থানীয় বৈশিষ্ট্য আকার-শ্রেণীবদ্ধ জাল সমাপ্ত এবং উত্পাদন করার নিশ্চয়তা দেয়। অ্যালগরিদমটি ইনপুট শীর্ষগুলির একটি সীমাবদ্ধ ডেলাউনে ত্রিভুজ দিয়ে শুরু হয়। প্রতিটি ধাপে, একটি নিম্নমানের ত্রিভুজের পরিধি কেন্দ্রকে একটি ব্যতিক্রম ছাড়া ত্রিভুজের মধ্যে ঢোকানো হয়ঃ যদি পরিধি কেন্দ্রটি নিম্নমানের ত্রিভুজ হিসাবে একটি ইনপুট বিভাগের বিপরীত দিকে থাকে, তবে বিভাগের মধ্যবিন্দুটি ঢোকানো হয়। উপরন্তু, মূল অংশের ব্যাস বলের ভিতরে (এটি বিভক্ত হওয়ার আগে) পূর্বে ঢোকানো যে কোনও পরিধি ত্রিভুজ থেকে সরানো হয়। কোনও নিম্নমানের ত্রিভুজ না থাকা পর্যন্ত সার্কামসেন্টার সন্নিবেশ পুনরাবৃত্তি করা হয়। রুপার্টের অ্যালগরিদম রুপার্টের অ্যালগরিদম একটি সমতলীয় সরলরেখার গ্রাফ (বা দুটির চেয়ে বেশি মাত্রায় একটি পিসওয়াইজ রৈখিক ব্যবস্থা) নেয় এবং শুধুমাত্র মানের ত্রিভুজের একটি সামঞ্জস্যপূর্ণ ডেলাউনে ত্রিভুজ প্রদান করে। একটি ত্রিভুজকে নিম্নমানের হিসাবে বিবেচনা করা হয় যদি এর পরিধি থেকে সংক্ষিপ্ততম প্রান্তের অনুপাত কিছু নির্ধারিত প্রান্তের চেয়ে বেশি হয়। 1990-এর দশকের গোড়ার দিকে জিম রুপার্ট দ্বারা আবিষ্কৃত, "দ্বিমাত্রিক মানের জাল উৎপাদনের জন্য রুপার্টের অ্যালগরিদম সম্ভবত প্রথম তাত্ত্বিকভাবে নিশ্চিত মেশিং অ্যালগরিদম যা বাস্তবে সত্যই সন্তোষজনক"। অনুপ্রেরণা গণনামূলক তরল গতিবিদ্যার মতো কম্পিউটার সিমুলেশন করার সময়, একটি উইং বিভাগের 2ডি রূপরেখার মতো একটি মডেল দিয়ে শুরু করা হয়। একটি 2ডি সসীম উপাদান পদ্ধতিতে ইনপুট ত্রিভুজ আকারে হতে হবে যা সমস্ত স্থান পূরণ করে এবং প্রতিটি ত্রিভুজকে এক ধরনের উপাদান দিয়ে পূরণ করতে হবে-এই উদাহরণে, "বায়ু" বা "ডানা"। লম্বা, চর্মসার ত্রিভুজগুলি সঠিকভাবে অনুকরণ করা যায় না। সিমুলেশন সময় সাধারণত ত্রিভুজের সংখ্যার সাথে আনুপাতিক, এবং তাই কেউ ত্রিভুজের সংখ্যা হ্রাস করতে চায়, এখনও যুক্তিসঙ্গতভাবে সঠিক ফলাফল দেওয়ার জন্য পর্যাপ্ত ত্রিভুজ ব্যবহার করে-সাধারণত একটি কাঠামোগত গ্রিড ব্যবহার করে। বহুভুজ মডেলটিকে সীমাবদ্ধ উপাদান পদ্ধতির জন্য উপযুক্ত ত্রিভুজে রূপান্তর করতে কম্পিউটার রুপার্টের অ্যালগরিদম (বা কিছু অনুরূপ মেশিং অ্যালগরিদম) ব্যবহার করে। অ্যালগরিদম অ্যালগরিদমটি ইনপুট শীর্ষগুলির একটি ডেলাউনে ত্রিভুজ দিয়ে শুরু হয় এবং তারপরে দুটি প্রধান ক্রিয়াকলাপ নিয়ে গঠিত। খালি ব্যাসের বৃত্তযুক্ত একটি অংশের মধ্যবিন্দু ত্রিভুজের মধ্যে ঢোকানো হয়। একটি নিম্নমানের ত্রিভুজের পরিধিকে ত্রিভুজের মধ্যে ঢোকানো হয়, যদি না এই পরিধিকেন্দ্রটি কোনও অংশের ব্যাস বৃত্তের মধ্যে থাকে। এই ক্ষেত্রে, পরিবর্তে দখল করা অংশটি বিভক্ত করা হয়। এই ক্রিয়াকলাপগুলি পুনরাবৃত্তি করা হয় যতক্ষণ না কোনও নিম্নমানের ত্রিভুজ বিদ্যমান থাকে এবং সমস্ত বিভাগ দখল করা হয় না। সিউডোকোড ফাংশন রুপার্ট (পয়েন্ট, সেগমেন্ট, থ্রেশহোল্ড) হল টিঃ = ডেলাউনে ত্রিভুজ (পয়েন্ট) কিউঃ = দখল করা অংশ এবং নিম্নমানের ত্রিভুজগুলির সেট যেখানে কিউ খালি নয়ঃ// প্রধান লুপ যদি কিউতে একটি সেগমেন্ট থাকে এসঃ টি-তে এস-এর মধ্যবিন্দু সন্নিবেশ করান অন্যথায় কিউ-তে নিম্নমানের ত্রিভুজ টি থাকেঃ যদি টি-এর পরিধি একটি বিভাগকে অতিক্রম করেঃ এস-কে কিউ-তে যোগ করুন; অন্যথায়ঃ টি-এর পরিধিটি টি প্রান্তে সন্নিবেশ করান যদি শেষ হয় যদি কিউ শেষ আপডেট করা হয় এবং টি শেষ রুপার্ট ফেরত দেয়। পরিবর্তন ছাড়াই ব্যবহারিক ব্যবহার রুপার্টের অ্যালগরিদমটি অ-তীব্র ইনপুট এবং প্রায় 20.7 ডিগ্রির কম যে কোনও নিম্ন-মানের থ্রেশহোল্ডের জন্য একটি মানের জাল শেষ এবং তৈরি করার নিশ্চয়তা দেয়। এই বিধিনিষেধগুলি শিথিল করার জন্য বিভিন্ন ছোট ছোট উন্নতি করা হয়েছে। ছোট ইনপুট কোণের কাছাকাছি মানের প্রয়োজনীয়তা শিথিল করে, অ্যালগরিদমটি যে কোনও সরল-রেখার ইনপুট পরিচালনা করার জন্য প্রসারিত করা যেতে পারে। বক্র ইনপুটও অনুরূপ কৌশল ব্যবহার করে মেশ করা যেতে পারে। রুপার্টের অ্যালগরিদম স্বাভাবিকভাবেই তিনটি মাত্রায় প্রসারিত করা যেতে পারে, তবে স্লাইভার টাইপ টেট্রাহেড্রনের কারণে এর আউটপুট গ্যারান্টি কিছুটা দুর্বল। দুটি মাত্রায় রুপার্টের অ্যালগরিদমের একটি সম্প্রসারণ অবাধে উপলব্ধ ত্রিভুজ প্যাকেজে প্রয়োগ করা হয়। এই প্যাকেজে রুপার্টের অ্যালগরিদমের দুটি রূপ প্রায় 26.5 ডিগ্রির নিম্নমানের প্রান্তিকের জন্য সমাপ্ত হওয়ার নিশ্চয়তা দেয়। বাস্তবে এই অ্যালগরিদমগুলি 30 ডিগ্রির বেশি নিম্নমানের সীমার জন্য সফল। যাইহোক, উদাহরণগুলি জানা যায় যার ফলে অ্যালগরিদমটি 29.06 ডিগ্রির চেয়ে বেশি প্রান্তিকের সাথে ব্যর্থ হয়। আরও দেখুন স্থানীয় বৈশিষ্ট্যের আকার বহুভুজ জাল টেটজেন ভোরোনোই রেখাচিত্র তথ্যসূত্র আরও পড়া জাল প্রজন্ম ত্রিভুজ (জ্যামিতি) ভিডিও ক্লিপ সম্বলিত নিবন্ধ