Wydaje się to nietrywialne (na różnych forach pojawia się sporo zapytań), ale absolutnie potrzebuję tego jako elementu budującego bardziej złożony algorytm.

Wkład: 2 wielokąty (A i B) w 2D, podane jako lista krawędzi[(x0, y0, x1, y2), ...] każdy. Punkty są reprezentowane przez parydoubles. Nie wiem, czy są podane zgodnie z ruchem wskazówek zegara, przeciwnie do ruchu wskazówek zegara lub w dowolnym kierunku. jarobić wiem, że niekoniecznie są wypukłe.

Wydajność: 3 wielokąty reprezentujące A, B i przecinający się wielokąt AB. Każdy z nich może być pustym (?) Wielokątem, np.null.

Podpowiedź na temat optymalizacji: Te wielokąty reprezentują granice pomieszczenia i podłogi. Tak więc granica pomieszczenia normalnie całkowicie przecina się z granicą podłogi, chyba że należy do innego piętra na tej samej płaszczyźnie (argh!).

Mam nadzieję, że ktoś już to zrobił w c # i pozwoli mi wykorzystać ich strategię / kod, ponieważ to, co do tej pory odkryłem w tym problemie, jest raczej zniechęcające.

EDYTOWAĆ: Więc wydaje mi się, że nie jestem całkowicie cholernie za bycie słabym w perspektywie zrobienia tego. Chciałbym tutaj przetworzyć pożądany wynik, ponieważ jest to szczególny przypadek i może ułatwić obliczenia:

Wydajność: Pierwszy wielokąt minus wszystkie przecinające się bity, wielokąty przecięcia (liczba mnoga jest OK). Nie interesuje mnie drugi wielokąt, tylko jego przecięcie z pierwszym.

EDIT2: Obecnie używamGPC (General Polygon Clipper) biblioteka, która sprawia, że ​​to naprawdę proste!