كيفية أداء التقسيم المكاني في n-dimensions؟

Question

أحاول تصميم تنفيذ كمية المتجه كفئة قالب C ++ يمكنها التعامل مع أنواع وأبعاد مختلفة من المتجهات (مثل 16 ناقلات البعد من البايتات ، أو متجهات 4D من الزوجي ، إلخ).

لقد قرأت على الخوارزميات ، وأنا أفهم معظمها:

هنا و هنا

أرغب في تنفيذ خوارزمية Linde-Buzo-Gray (LBG) ، لكنني أواجه صعوبة في معرفة الخوارزمية العامة لتقسيم المجموعات. أعتقد أنني بحاجة إلى تحديد طائرة (طائرة مفرطة؟) تقسم المتجهات في الكتلة بحيث يكون هناك عدد متساو على كل جانب من الطائرة.

تحرير لإضافة المزيد من المعلوماتهذه عملية تكرارية ، لكنني أعتقد أنني أبدأ بإيجاد النقطه الوسطى لجميع المتجهات ، ثم استخدم هذا النقطه المركزي لتحديد الطائرة المقسمة ، والحصول على النقط الوسطى لكل من جانبي الطائرة ، واستمر حتى يكون لدي عدد من المجموعات اللازمة لخوارزمية VQ (تكرار لتحسين التشويه الأقل على طول الطريق). تظهر الرسوم المتحركة في الرابط الأول أعلاه بشكل جيد.

أسئلتي هي:

ما هي الخوارزمية للعثور على الطائرة بمجرد الحصول على النقطه الوسطى؟

كيف يمكنني اختبار المتجه لمعرفة ما إذا كان على جانبي تلك الطائرة؟

Answer 1

إذا بدأت بنهج وسط واحد ، فسيتعين عليك تقسيمه ، بشكل أساسي عن طريق مضاعفةه ونقل النقاط قليلاً في اتجاه تعسفي. الطائرة هي مجرد طائرة متعامدة مع هذا الاتجاه.

لكنك لست بحاجة إلى حساب تلك الطائرة.

بشكل أعم ، يتم تعريف المنطقة (1) على أنها مجموعة من النقاط التي تقترب من النقطه الوسطى C_I من أي نقطية وسط أخرى. عندما يكون لديك اثنين من الأقطار ، كل منطقة مساحة نصف ، وبالتالي مفصولة بطائرة (مفرطة).

كيفية اختبار المتجه X لمعرفة أي جانب من الطائرة هو؟ (هذا مع اثنين من النطاقات النروية)

فقط حساب المسافة || X-C1 || و || X-C2 || ، سوف يمنحك فهرس القيمة الدنيا (1 أو 2) المنطقة التي تنتمي إليها النقطة X.

بشكل عام ، إذا كان لديك N centroids ، فستقوم بحساب جميع المسافات || x-c_i || ، وأن Centroid X الأقرب إلى (أي ، التي تكون المسافة في الحد الأدنى) تمنحك المنطقة X التي تنتمي إليها.

Answer 2

لا أفهم تمامًا الخوارزمية ، لكن السؤال الثاني سهل:

لنتصل الخامس متجه يمتد من عند أي نقطة على متن الطائرة ل نقطة في السؤال. ثم تكمن نقطة الاستبعاد على نفس الجانب من المستوى (المفرط) كالمعتاد ن IFF v · n > 0