Generuj nowe wielokąty z wyciętego wielokąta (2D)
Utknąłem z tym małym problemem i mój algorytm do rozwiązania tego problemu nie dotyczy wszystkich przypadków. Czy ktoś ma pomysł, jak to rozwiązać?
Oto przykładowy wielokąt:
przykład http://img148.imageshack.us/img148/8804/poly.png
Formalny opis
Mamy listę punktów w kolejności CW definiujących wielokąt. Możemy również zapytać, czy punkt jest punktem cięciais_cut(p)
, gdziep
to dany punkt. Teraz chcemy obliczyć nowe wielokąty spowodowane przez to „cięcie”.
Algorytm powinien to zrobić:
Wkład:{a, c1, b, c4, c, c5, d, c6, e, c3, f, c2}
Wydajność:{a, c1, c2}
, {b, c4, c3, f, c2, c1}
, {d, c6, c5}
, {e, c3, c4, c, c5, c6}
Oto mój obecny algorytm:
follow your points, CW
if the point is a cut point
-> go back trough the list looking for cut points
--- if next cut point is connected to the current cut point
and not part of the current poly, follow it
--- else keep searching
else
-> continue until you hit your starting point.
that's a poly
do this for every non-cut-point
Ten algorytm nie działa, jeśli zaczniesz odc
lubf
.