Określ, czy punkt znajduje się wewnątrz wielokąta?

Question

Tworzę niestandardowe sterowanie w Delphi (odziedziczonym po TCustomControl), które składa się z wielu elementów listy wielokątów (nieregularne kształty). Muszę zaimplementować zdarzenia myszy na element, ale najpierw muszę być w stanie wykryć, czy pozycja myszy znajduje się w danym wielokącie (array of TPoint). Dostaję wiadomość Hit Test (WM_NCHITTEST) i to jest miejsce, gdzie będę musiał wykonać tę walidację. Mam wiele wielokątów, zrobię pętlę przez każdy element wielokąta i wykonam tę kontrolę, aby zobaczyć, czy pozycja X/Y myszy znajduje się w tym wielokącie.

procedure TMyControl.WMNCHitTest(var Message: TWMNCHitTest); 
var 
    P: TPoint; //X/Y of Mouse 
    Poly: TPoints; //array of TPoint 
    X: Integer; //iterator 
    I: TMyListItem; //my custom list item 
begin 
    P.X:= Message.XPos; 
    P.Y:= Message.YPos; 
    for X := 0 to Items.Count - 1 do begin 
    I:= Items[X]; //acquire my custom list item by index 
    Poly:= I.Points; //acquire polygon points 

    //Check if Point (P) is within Polygon (Poly)...? 

    end; 
end; 

Answer 1

Można użyć PtInRegion:

function PointInPolygon(Point: TPoint; const Polygon: array of TPoint): Boolean; 
var 
    rgn: HRGN; 
begin 
    rgn := CreatePolygonRgn(Polygon[0], Length(Polygon), WINDING); 
    Result := PtInRegion(rgn, Point.X, Point.Y); 
    DeleteObject(rgn); 
end; 

Answer 2

można wykorzystywać algorytm rozstrzygający ray znaleźć tutaj: http://en.wikipedia.org/wiki/Point_in_polygon#Ray_casting_algorithm

Większość klas grafika komputerowa wykorzystać to jako przykład.

Answer 3

Sprawdzanie, czy punkt znajduje się wewnątrz wielokąta, można wykonać, wyobrażając sobie poziomą linię przechodzącą przez ten punkt, a następnie od lewej do prawej, licząc ile razy ta wyimaginowana linia przecina wielokąt. Jeśli liczba wielokątów przecina się przed trafieniem w punkt jest nieparzysta, to punkt znajduje się wewnątrz, jeśli nawet wtedy punkt znajduje się poza polem.

Answer 4

Istnieje inna technika, której używamy w znacznym stopniu, która w ogóle nie zawiera żadnych elementów matematycznych i która może obsługiwać niezwykle złożone wbudowane elementy sterujące o dowolnym kształcie. Wystarczy mieć poza ekranem obraz kontrolny z wszystkimi kolorami części (jak pokazano na poniższym obrazku), które użytkownik może kliknąć.

Gdy przesuwają mysz, po prostu spoglądaj na kolor piksela pod spodem myszy w obrazie poza ekranem, który dokładnie informuje, jaki przycisk/przycisk kontrolny są nadpisane - biały, aby nie nad nim, i dowolną serię kolorów dla różnych części.

Color mask

// Pseudo-Code

function MouseOverControl(LocalMousePos:TPoint):ControlID; 
begin 
    //sanity check 
    Result:=IDNull; 
    if (LocalMouse.X < 0) or (LocalMouse.X > ControlWidth) or 
     (LocalMouse.Y < 0) or (LocalMouse.Y > ControlHeight) then 
      exit; 
    case OffScreenControlMask.Canvas.Pixels[LocalMousePos.X,LocalMousePos.Y] of 
    clwhite:exit; 
    clRed:result:=ControlIDOne; 
    clGreen:result:=ControlIDTwo; 
    clBlue:result:=ControlIDThree; 
    ... etc 
    end; 
end; 

UWAGA: Załączony Maska Kolor obraz przedstawia pięć identycznych kontroli okrągłe podzielone na ćwiartki z przyciskiem środkowej (a ponieważ wszystkie one korzystają z tych samych kolorach mamy stałe dla każdego koloru i ustalamy, która z pięciu myszy jest zakończona prostym XPosition) wraz z dodatkowym nieregularnym sterowaniem po ich prawej stronie i ustawionymi lub prostokątnymi przyciskami pod spodem.