Sudé - liché pravidlo - Even–odd rule

Křivka (nahoře) je vyplněna podle dvou pravidel: sudé - liché pravidlo (vlevo) a pravidlo nenulového vinutí (že jo). V každém případě šipka ukazuje paprsek z bodu P směřujícího z křivky. V sudém – lichém případě je paprsek protíná dvěma řádky, sudým číslem; proto se P uzavírá jako „mimo“ křivku. Pravidlem nenulového vinutí se paprsek protíná dvakrát ve směru hodinových ručiček, z nichž každý přispívá −1 k skóre vinutí: protože součet −2 není nula, P se považuje za „uvnitř“ křivky.

The sudé - liché pravidlo je algoritmus implementováno ve vektorovém grafickém softwaru,[1] jako PostScript jazyk a Škálovatelná vektorová grafika (SVG), který určuje, jak bude vyplněn grafický tvar s více než jedním uzavřeným obrysem. Na rozdíl od nenulové pravidlo Algoritmus, tento algoritmus alternativně vybarví a ponechá nezbarvené tvary definované vnořenými uzavřenými cestami bez ohledu na jejich vinutí.

SVG definuje sudé-liché pravidlo slovy:

Toto pravidlo určuje „skrytost“ bodu na plátně nakreslením paprsku z tohoto bodu do nekonečna v libovolném směru a počítáním počtu segmentů cesty z daného tvaru, který paprsek protíná. Pokud je toto číslo liché, je bod uvnitř; pokud je sudý, bod je venku.

Pravidlo lze vidět v platnosti v mnoha programech vektorové grafiky (například Volná ruka nebo Ilustrátor ), kde křížení obrysu samo o sobě způsobí, že tvary se vyplňují zvláštním způsobem.

Na jednoduché křivce se pravidlo sudé-liché redukuje na rozhodovací algoritmus pro bod v mnohoúhelníku problém.

The SVG standard vektorové počítačové grafiky lze nakonfigurovat tak, aby při kreslení polygonů používal pravidlo sudých lichých, i když používá nenulové pravidlo ve výchozím stavu.[2]

Implementace

Níže je ukázka implementace v Krajta:[3]

def is_point_in_path(X: int, y: int, poly) -> bool:    "" "Určete, zda je bod v cestě.    Args:      x - souřadnice x bodu.      y - souřadnice y bodu.      poly - seznam n-tic [(x, y), (x, y), ...]    Vrací:      Je pravda, pokud je bod v cestě.    """    počet = len(poly)    i = 0    j = počet - 1    C = Nepravdivé    pro i v rozsah(počet):        -li ((poly[i][1] > y) != (poly[j][1] > y)) a                 (X < poly[i][0] + (poly[j][0] - poly[i][0]) * (y - poly[i][1]) /                                  (poly[j][1] - poly[i][1])):            C = ne C        j = i    vrátit se C

Viz také

Reference

  1. ^ J. D. Foley, A. van Dam, S. K. Feiner a J. F. Hughes. Počítačová grafika: Zásady a praxe. Řada SystemsProgramming Series. Addison-Wesley, Reading, 2. vydání, 1990.
  2. ^ [1], w3c.org, vyvoláno 2019-03-28
  3. ^ „PNPOLY - Bodové zahrnutí do testu polygonů - WR Franklin (WRF)“.

externí odkazy