Điểm trong thuật toán Đa giác cho kết quả sai đôi khi

Question

Tôi đã thấy trên StackOverflow một thuật toán "ray trong đa giác" mà tôi đã triển khai trong Mã PHP của mình. Hầu hết thời gian, nó hoạt động tốt, nhưng trong một số trường hợp phức tạp, với đa giác phức tạp và các điểm luẩn quẩn, nó thất bại và nó nói rằng điểm đó không có trong đa giác khi nó được.

Ví dụ:
Bạn sẽ tìm thấy here Đa giác và điểm của tôi: phương pháp pointInPolygon nằm trong lớp Đa giác. Ở cuối tệp, có hai điểm được cho là nằm bên trong đa giác đã cho (True on Google Earth). Điều thứ hai hoạt động tốt, nhưng một trong những đầu tiên là lỗi :(.

Bạn có thể dễ dàng kiểm tra các đa giác trên Google Earth sử dụng this KML file.

Answer 1

Đã có :-) Tôi cũng đi máng stackoverflows PiP-đề nghị, bao gồm tham chiếu của bạn và this thread. Unfortunelaty không có gợi ý nào (ít nhất là những gì tôi đã thử) là hoàn hảo và đủ cho một kịch bản đời thực: giống như người dùng vẽ đồ thị đa giác phức tạp trên bản đồ google tự do, "luẩn quẩn" so với các vấn đề trái, số âm và vân vân.

Thuật toán PiP phải hoạt động trong mọi trường hợp, ngay cả khi đa giác bao gồm hàng trăm nghìn điểm (như biên giới hạt, công viên tự nhiên, v.v ..) - cho dù đa giác là "điên".

Vì vậy, tôi đã kết thúc việc xây dựng một thuật toán mới, dựa trên một số nguồn tin từ một thiên văn học ứng dụng:

//Point class, storage of lat/long-pairs 
class Point { 
    public $lat; 
    public $long; 
    function Point($lat, $long) { 
     $this->lat = $lat; 
     $this->long = $long; 
    } 
} 

//the Point in Polygon function 
function pointInPolygon($p, $polygon) { 
    //if you operates with (hundred)thousands of points 
    set_time_limit(60); 
    $c = 0; 
    $p1 = $polygon[0]; 
    $n = count($polygon); 

    for ($i=1; $i<=$n; $i++) { 
     $p2 = $polygon[$i % $n]; 
     if ($p->long > min($p1->long, $p2->long) 
      && $p->long <= max($p1->long, $p2->long) 
      && $p->lat <= max($p1->lat, $p2->lat) 
      && $p1->long != $p2->long) { 
       $xinters = ($p->long - $p1->long) * ($p2->lat - $p1->lat)/($p2->long - $p1->long) + $p1->lat; 
       if ($p1->lat == $p2->lat || $p->lat <= $xinters) { 
        $c++; 
       } 
     } 
     $p1 = $p2; 
    } 
    // if the number of edges we passed through is even, then it's not in the poly. 
    return $c%2!=0; 
} 

thử nghiệm minh họa:

$polygon = array(
    new Point(1,1), 
    new Point(1,4), 
    new Point(4,4), 
    new Point(4,1) 
); 

function test($lat, $long) { 
    global $polygon; 
    $ll=$lat.','.$long; 
    echo (pointInPolygon(new Point($lat,$long), $polygon)) ? $ll .' is inside polygon<br>' : $ll.' is outside<br>'; 
} 

test(2, 2); 
test(1, 1); 
test(1.5333, 2.3434); 
test(400, -100); 
test(1.01, 1.01); 

Đầu ra:

2,2 is inside polygon 
1,1 is outside 
1.5333,2.3434 is inside polygon 
400,-100 is outside 
1.01,1.01 is inside polygon 

Bây giờ đã hơn một năm kể từ khi tôi chuyển sang algor trên ithm trên một số trang web. Không giống như "SO-thuật toán" đã không có bất kỳ khiếu nại cho đến nay. Xem nó trong hành động here (cơ sở dữ liệu mycological quốc gia, xin lỗi cho danish). Bạn có thể vẽ một đa giác, hoặc chọn một "kommune" (một quận) - cuối cùng so sánh một đa giác với hàng ngàn điểm với hàng ngàn bản ghi).

Cập nhật Note, thuật toán này được nhắm mục tiêu theo dữ liệu địa lý/lat, lngs mà có thể rất chính xác (thập phân n'th), do đó xem xét "trong đa giác" như bên trong đa giác - không trên biên giới của đa giác . 1,1 được coi là bên ngoài, vì nó là trên đường viền. 1.0000000001,1.01 không phải là.