خوارزمية لحواف العثور فريدة من المضلع عيون

Question

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

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

هل هناك خوارزمية أكثر ذكاء لهذا؟

Answer 1

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

لبحث عن ميزة في هذا الهيكل أن تأخذ مؤشر أكبر، والبحث عنه في المستوى الأعلى وينتهي مع خريطة التجزئة. ثم أخذ مؤشر أصغر والبحث عنه في هذه الخريطة تجزئة الثانية.

Answer 2

وفقط لتوضيح، وتريد، للحصول على قائمة مضلع مثل هذا:

A +-----+ B
   \    |\
    \ 1 | \
     \  |  \
      \ | 2 \
       \|    \
      C +-----+ D

وبعد ذلك بدلا من الحواف مثل هذا:

A - B -+
B - C  +- first polygon
C - A -+

B - D -+
D - C  +- second polygon
C - B -+

وبعد ذلك كنت ترغب في إزالة مكررة B - C مقابل C - B حافة وتقاسمها

ما هو نوع من مشكلة الأداء هل ترى مع الخوارزمية الخاصة بك؟ انا اقول مجموعة التي تحتوي على تنفيذ التجزئة معقول ينبغي أن تؤدي طيب جدا. من ناحية أخرى، إذا التجزئة ليست الأمثل للبيانات، سيكون لديك الكثير من التصادمات التي قد تؤثر على الأداء بشكل كبير.

Answer 3

وأنت على حد سواء الصحيح. باستخدام hashset جيدة حصلت أداء جيدا إلى ما بعد المستويات المطلوبة. انتهى بي الأمر المتداول بلدي قليلا مجموعة التجزئة.

وسوف العدد الإجمالي للحواف يكون بين N / 2 و N. N يجري عدد من القمم فريدة من نوعها في شبكة. وجميع حواف المشتركة يكون N / 2، وجميع حواف فريدة يكون N. من هناك وتخصيص مخزن مؤقت لuint64 وحزمة مؤشرات بلدي إلى هذه القيم. باستخدام مجموعة صغيرة من الجداول فريدة يمكنني العثور على حواف فريدة من نوعها بسرعة!

Answer 4

وهيريس تنفيذ C من حافة تجزئة المستخدمة في خلاط بالضبط لغرض خلق بسرعة حواف من الوجوه، قد تعطي بعض النصائح للآخرين لجعل بأنفسهم.

HTTP: // gitorious. غزاله / blenderprojects / خلاط / النقط / الماجستير / خلاط / المصدر / خلاط / blenlib / المتدرب / edgehash.c

http://gitorious.org/ blenderprojects / خلاط / النقط / الماجستير / خلاط / المصدر / خلاط / blenlib / BLI_edgehash.h

وهذا يستخدم BLI_mempool، https://gitorious.org/blenderprojects /blender/blobs/master/blender/source/blender/blenlib/intern/BLI_mempool.c

https://gitorious.org/ blenderprojects / خلاط / النقط / الماجستير / خلاط / المصدر / خلاط / blenlib / BLI_mempool.h

Answer 5

وتحتاج أولا للتأكد من القمم الخاصة بك فريدة من نوعها. هذا إذا كنت تريد فقط حافة واحدة في موقف معين. ثم يمكنني استخدام هذه البنية البيانات

وtypedef std::pair<int, int> Edge;

وEdge sampleEdge;

وstd::map<Edge, bool> uniqueEdges;

والحافة تحتوي على مؤشرات قنة التي تشكل ميزة في ترتيب فرزها. وبالتالي إذا sampleEdge يتم إجراء حافة تتكون من القمم مع الأرقام القياسية 12 و 5، sampleEdge.first = 5 و sampleEdge.12

وبعد ذلك يمكنك القيام به فقط

وuniqueEdges[sampleEdge] = true;

ولجميع الحواف. سوف uniqueEdges عقد جميع حواف فريدة من نوعها.