Xác định xem một điểm có nằm trong đa giác không?

Question

Tôi đang tạo điều khiển tùy chỉnh trong Delphi (được kế thừa từ TCustomControl) bao gồm một số mục danh sách đa giác (hình dạng không đều). Tôi cần phải thực hiện các sự kiện chuột cho mỗi mục, nhưng trước tiên tôi cần phải có khả năng phát hiện nếu vị trí chuột nằm trong một đa giác nhất định (array of TPoint). Tôi đang bắt được thông báo Kiểm tra lượt truy cập (WM_NCHITTEST) và đây là nơi tôi sẽ cần thực hiện xác thực này. Tôi có một số đa giác, tôi sẽ thực hiện một vòng lặp qua từng mục đa giác và thực hiện kiểm tra này để xem vị trí X/Y của chuột có nằm trong đa giác này hay không.

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

Bạn có thể sử dụng 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

Bạn có thể sử dụng các thuật toán đúc ray tìm thấy ở đây: http://en.wikipedia.org/wiki/Point_in_polygon#Ray_casting_algorithm

Hầu hết các lớp học đồ họa máy tính sử dụng như là một ví dụ.

Answer 3

Kiểm tra xem điểm có nằm trong một đa giác hay không bằng cách tưởng tượng một đường ngang qua điểm đó, sau đó từ trái sang phải đếm số lần đường tưởng tượng này đi qua một đa giác. Nếu số lượng đa giác vượt qua trước khi nhấn một điểm là lẻ thì điểm là bên trong, nếu ngay cả điểm đó nằm ngoài một đa giác.

Answer 4

Có một kỹ thuật khác mà chúng tôi sử dụng rộng rãi, không liên quan đến bất kỳ toán học nào và có thể xử lý các điều khiển nhúng cực kỳ phức tạp của bất kỳ hình dạng nào. Đơn giản chỉ cần có một hình ảnh ngoài màn hình của điều khiển với tất cả các phần màu mã hóa (như được hiển thị trong hình dưới đây) mà người dùng có thể nhấp vào.

Khi di chuyển chuột, chỉ cần nhìn vào màu của điểm ảnh bên dưới con chuột trong hình ảnh ngoài màn hình của chúng tôi và cho chúng tôi biết chính xác nút/điều khiển nào vượt quá màu trắng để không vượt qua và bất kỳ chuỗi nào màu sắc cho các bộ phận khác nhau.

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; 

Chú ý: Hình ảnh Mask Màu kèm theo đại diện lăm điều khiển hình tròn giống hệt nhau chia thành trục tọa với một nút trung tâm (và kể từ khi tất cả họ đều sử dụng màu sắc tương tự chúng tôi có hằng số cho mỗi màu và chúng tôi xác định xem một trong năm con chuột đã kết thúc bằng một XPosition đơn giản) cùng với một điều khiển bất thường bổ sung ở bên phải của chúng và các nút hình chữ nhật hoặc đặt bên dưới.