forum.boolean.name
Страница 1 из 2 1 2 >
Показывать 64 сообщений этой темы на одной странице

forum.boolean.name (http://forum.boolean.name/index.php)
-   Алгоритмика (http://forum.boolean.name/forumdisplay.php?f=21)
-   -   Точка в четырёхугольнике (http://forum.boolean.name/showthread.php?t=15711)

NitE 25.10.2011 21:20
Точка в четырёхугольнике
 
Подайте пожалуйста алгоритм проверки, попала ли точка в произвольный четырёхугольник.

pax 25.10.2011 21:21
Ответ: Точка в четырёхугольнике
 
Проверяй на попадание в два треугольника

Randomize 25.10.2011 21:59
Ответ: Точка в четырёхугольнике
 
PHP код:
Function PointInPoly( point_x:Float, point_y:Float, xy:Float[] )
    
    If xy.length<6 Or (xy.length&1) Return False
    
    Local x1:Float=xy[xy.Length-2]
    Local y1:Float=xy[xy.Length-1]
    Local cur_quad:Int=GetQuad(point_x,point_y,x1,y1)
    Local next_quad:Int
    Local total:Int
    
    For Local i=0 Until Len xy Step 2
        Local x2:Float=xy[i]
        Local y2:Float=xy[i+1]
        next_quad=GetQuad(point_x,point_y,x2,y2)
        Local diff:Int=next_quad-cur_quad
        
        Select diff
        Case 2,-2
            If ( x2 - ( ((y2 - point_y) * (x1 - x2)) / (y1 - y2) ) )<point_x
                diff=-diff
            EndIf
        Case 3
            diff=-1
        Case -3
            diff=1
        End Select
        
        total:+diff
        cur_quad=next_quad
        x1=x2
        y1=y2
    Next
    
    If Abs(total)=4 Then Return True Else Return False
EndFunction

Function GetQuad(axis_x:Float,axis_y:Float,vert_x:Float,vert_y:Float)
    If vert_x<axis_x
        If vert_y<axis_y
            Return 1
        Else
            Return 4
        EndIf
    Else
        If vert_y<axis_y
            Return 2
        Else
            Return 3
        EndIf    
    EndIf

EndFunction 

Reizel 25.10.2011 22:07
Ответ: Точка в четырёхугольнике
 
Да ну вас. четырехугольник по всякому невыпуклый, => проверяем, по какую сторону от каждой из 4-х вершин нах-ся точка. Если точка по одну сторону у всех ребер - значит точка в многоугольнике)

ПС сторона точки относительно ребра: sgn(f(x,y)), где f(x,y) = (Ax+bY+C = 0)
подставляешь в уравнение координаты точки и получаешь число. Знак этого числа и определяет сторону

dsd 25.10.2011 22:46
Ответ: Точка в четырёхугольнике
 
Можно выбрать две противоположные точки, есть две пары векторов составляющие четырех угольник. Углы между ними легко найти. Ищем угол между вектором 1-4 и 1-(проверяемая точка), если он меньше чем угол между векторами 1-4 и 1-2, то проверяем лежит ли точка по туже сторону от линии 4-2, что и точка 1.
если да, значит точка внутри четырехугольника, нет, проверяем тоже для векторов 3-2 3-4 и 3-(проверяемая точка)

Igor 25.10.2011 22:47
Ответ: Точка в четырёхугольнике
 
Цитата:
произвольный четырёхугольник
Цитата:
четырехугольник по всякому невыпуклый
впервые слышу

LLI.T.A.L.K.E.R. 26.10.2011 00:15
Ответ: Точка в четырёхугольнике
 

http://uztest.ru/abstracts/?id=5&t=6

pax 26.10.2011 00:18
Ответ: Точка в четырёхугольнике
 
Частные случаи:


Если проверять на то, с какой стороны точка от каждого отрезка - то будет не верно.
Для второго случая думаю надо найти кратчайшую диагональ, и по ней разделить на два треугольника, хотя опять будет не верно).

Reizel 26.10.2011 00:19
Ответ: Точка в четырёхугольнике
 
Цитата:
Сообщение от Igor (Сообщение 206976)
впервые слышу
Аа...бл, простите, тогда другой метод:
берем угол, rand(0,360)
строим из точки луч, направленный в ту сторону, и считаем кол-во точек пересечения луча и ребер многоугольника. Если четное - точка снаружи, нечетное - внутри.

Randomize 26.10.2011 00:56
Ответ: Точка в четырёхугольнике
 
Цитата:
Сообщение от Павел (Сообщение 207002)
rand(0,360)
Использовать Rand? Классная ф-ция получится. Не с первого раза но точно выдаст правильный результат.

Randomize 26.10.2011 00:59
Ответ: Точка в четырёхугольнике
 
О чё нарыл:
PHP код:
<?php
class pointLocation {
    var $pointOnVertex = true; // Check if the point sits exactly on one of the vertices

    function pointLocation() {
    }
    
    
        function pointInPolygon($point, $polygon, $pointOnVertex = true) {
        $this->pointOnVertex = $pointOnVertex;
        
        // Transform string coordinates into arrays with x and y values
        $point = $this->pointStringToCoordinates($point);
        $vertices = array(); 
        foreach ($polygon as $vertex) {
            $vertices[] = $this->pointStringToCoordinates($vertex); 
        }
        
        // Check if the point sits exactly on a vertex
        if ($this->pointOnVertex == true and $this->pointOnVertex($point, $vertices) == true) {
            return "vertex";
        }
        
        // Check if the point is inside the polygon or on the boundary
        $intersections = 0; 
        $vertices_count = count($vertices);
    
        for ($i=1; $i < $vertices_count; $i++) {
            $vertex1 = $vertices[$i-1]; 
            $vertex2 = $vertices[$i];
            if ($vertex1['y'] == $vertex2['y'] and $vertex1['y'] == $point['y'] and $point['x'] > min($vertex1['x'], $vertex2['x']) and $point['x'] < max($vertex1['x'], $vertex2['x'])) { // Check if point is on an horizontal polygon boundary
                return "boundary";
            }
            if ($point['y'] > min($vertex1['y'], $vertex2['y']) and $point['y'] <= max($vertex1['y'], $vertex2['y']) and $point['x'] <= max($vertex1['x'], $vertex2['x']) and $vertex1['y'] != $vertex2['y']) { 
                $xinters = ($point['y'] - $vertex1['y']) * ($vertex2['x'] - $vertex1['x']) / ($vertex2['y'] - $vertex1['y']) + $vertex1['x']; 
                if ($xinters == $point['x']) { // Check if point is on the polygon boundary (other than horizontal)
                    return "boundary";
                }
                if ($vertex1['x'] == $vertex2['x'] || $point['x'] <= $xinters) {
                    $intersections++; 
                }
            } 
        } 
        // If the number of edges we passed through is even, then it's in the polygon. 
        if ($intersections % 2 != 0) {
            return "inside";
        } else {
            return "outside";
        }
    }

    
    
    function pointOnVertex($point, $vertices) {
        foreach($vertices as $vertex) {
            if ($point == $vertex) {
                return true;
            }
        }
    
    }
        
    
    function pointStringToCoordinates($pointString) {
        $coordinates = explode(" ", $pointString);
        return array("x" => $coordinates[0], "y" => $coordinates[1]);
    }
    
    
}

/*** Example ***/
$pointLocation = new pointLocation();
$points = array("30 19", "0 0", "10 0", "30 20", "11 0", "0 11", "0 10", "30 22", "20 20");
$polygon = array("10 0", "20 0", "30 10", "30 20", "20 30", "10 30", "0 20", "0 10", "10 0");
foreach($points as $key => $point) {
    echo "$key ($point) is " . $pointLocation->pointInPolygon($point, $polygon) . "<br>";
}
?>
Охреневаю сам от существования подобного

Reizel 26.10.2011 01:05
Ответ: Точка в четырёхугольнике
 
Автора на кастрацию срочно

Randomize 26.10.2011 01:10
Ответ: Точка в четырёхугольнике
 
Цитата:
Сообщение от Павел (Сообщение 207022)
Автора на кастрацию срочно
Алгоритм нормальный.
На остальное плевать.

Reizel 26.10.2011 01:13
Ответ: Точка в четырёхугольнике
 
Цитата:
Сообщение от Randomize (Сообщение 207018)
Использовать Rand? Классная ф-ция получится. Не с первого раза но точно выдаст правильный результат.
А чо не так?? Луч в рандомном направлении. В принципе, все равно как юзать - можно и константный, к примеру 90 градусов, для него можно предаврительно A, B, C рассчитать, но rand(360) тащит, не так ли, Randomize?

radiobutton 26.10.2011 02:15
Ответ: Точка в четырёхугольнике
 
Цитата:
Сообщение от Павел (Сообщение 207029)
А чо не так?? Луч в рандомном направлении. В принципе, все равно как юзать - можно и константный, к примеру 90 градусов, для него можно предаврительно A, B, C рассчитать, но rand(360) тащит, не так ли, Randomize?
можно тупо 0 градусов )
Ибо если будит 0 пересечений, тогда снаружи.


Часовой пояс GMT +4, время: 07:19.
Страница 1 из 2 1 2 >
Показывать 64 сообщений этой темы на одной странице

vBulletin® Version 3.6.5.
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Перевод: zCarot