|
Алгоритмика Об алгоритмах вообще; методы, обсуждения способов решения |
25.10.2011, 21:20
|
#1
|
злобный флудер
Регистрация: 10.07.2007
Сообщений: 2,585
Написано 789 полезных сообщений (для 1,476 пользователей)
|
Точка в четырёхугольнике
Подайте пожалуйста алгоритм проверки, попала ли точка в произвольный четырёхугольник.
|
(Offline)
|
|
25.10.2011, 21:21
|
#2
|
Unity/C# кодер
Регистрация: 03.10.2005
Адрес: Россия, Рязань
Сообщений: 7,568
Написано 3,006 полезных сообщений (для 5,323 пользователей)
|
Ответ: Точка в четырёхугольнике
Проверяй на попадание в два треугольника
|
(Offline)
|
|
Эти 2 пользователя(ей) сказали Спасибо pax за это полезное сообщение:
|
dsd (25.10.2011), NitE (25.10.2011)
|
25.10.2011, 21:59
|
#3
|
[object Object]
Регистрация: 01.08.2008
Адрес: В России
Сообщений: 4,359
Написано 2,473 полезных сообщений (для 6,856 пользователей)
|
Ответ: Точка в четырёхугольнике
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
__________________
Retry, Abort, Ignore? █
Intel Core i7-9700 4.70 Ghz; 64Gb; Nvidia RTX 3070
AMD Ryzen 7 3800X 4.3Ghz; 64Gb; Nvidia 1070Ti
AMD Ryzen 7 1700X 3.4Ghz; 8Gb; AMD RX 570
AMD Athlon II 2.6Ghz; 8Gb; Nvidia GTX 750 Ti
|
(Offline)
|
|
Эти 2 пользователя(ей) сказали Спасибо Randomize за это полезное сообщение:
|
|
25.10.2011, 22:07
|
#4
|
Задрот
Регистрация: 24.07.2009
Адрес: Ивановская область, г. Кинешма
Сообщений: 1,574
Написано 407 полезных сообщений (для 863 пользователей)
|
Ответ: Точка в четырёхугольнике
Да ну вас. четырехугольник по всякому невыпуклый, => проверяем, по какую сторону от каждой из 4-х вершин нах-ся точка. Если точка по одну сторону у всех ребер - значит точка в многоугольнике)
ПС сторона точки относительно ребра: sgn(f(x,y)), где f(x,y) = (Ax+bY+C = 0)
подставляешь в уравнение координаты точки и получаешь число. Знак этого числа и определяет сторону
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
25.10.2011, 22:46
|
#5
|
Мастер
Регистрация: 13.06.2011
Сообщений: 1,103
Написано 481 полезных сообщений (для 1,836 пользователей)
|
Ответ: Точка в четырёхугольнике
Можно выбрать две противоположные точки, есть две пары векторов составляющие четырех угольник. Углы между ними легко найти. Ищем угол между вектором 1-4 и 1-(проверяемая точка), если он меньше чем угол между векторами 1-4 и 1-2, то проверяем лежит ли точка по туже сторону от линии 4-2, что и точка 1.
если да, значит точка внутри четырехугольника, нет, проверяем тоже для векторов 3-2 3-4 и 3-(проверяемая точка)
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
25.10.2011, 22:47
|
#6
|
Мастер
Регистрация: 03.05.2010
Адрес: Подмосковье
Сообщений: 1,218
Написано 438 полезных сообщений (для 790 пользователей)
|
Ответ: Точка в четырёхугольнике
произвольный четырёхугольник
|
четырехугольник по всякому невыпуклый
|
впервые слышу
__________________
О¯О ¡¡¡ʁɔvʎнdǝʚǝdǝu dиW
|
(Offline)
|
|
Эти 3 пользователя(ей) сказали Спасибо Igor за это полезное сообщение:
|
|
26.10.2011, 00:15
|
#7
|
Мастер
Регистрация: 24.06.2009
Адрес: Набережные Челны
Сообщений: 930
Написано 292 полезных сообщений (для 504 пользователей)
|
Ответ: Точка в четырёхугольнике
|
(Offline)
|
|
26.10.2011, 00:18
|
#8
|
Unity/C# кодер
Регистрация: 03.10.2005
Адрес: Россия, Рязань
Сообщений: 7,568
Написано 3,006 полезных сообщений (для 5,323 пользователей)
|
Ответ: Точка в четырёхугольнике
Частные случаи:
Если проверять на то, с какой стороны точка от каждого отрезка - то будет не верно.
Для второго случая думаю надо найти кратчайшую диагональ, и по ней разделить на два треугольника, хотя опять будет не верно).
|
(Offline)
|
|
26.10.2011, 00:19
|
#9
|
Задрот
Регистрация: 24.07.2009
Адрес: Ивановская область, г. Кинешма
Сообщений: 1,574
Написано 407 полезных сообщений (для 863 пользователей)
|
Ответ: Точка в четырёхугольнике
Сообщение от Igor
впервые слышу
|
Аа...бл, простите, тогда другой метод:
берем угол, rand(0,360)
строим из точки луч, направленный в ту сторону, и считаем кол-во точек пересечения луча и ребер многоугольника. Если четное - точка снаружи, нечетное - внутри.
|
(Offline)
|
|
26.10.2011, 00:56
|
#10
|
[object Object]
Регистрация: 01.08.2008
Адрес: В России
Сообщений: 4,359
Написано 2,473 полезных сообщений (для 6,856 пользователей)
|
Ответ: Точка в четырёхугольнике
Сообщение от Павел
rand(0,360)
|
Использовать Rand? Классная ф-ция получится. Не с первого раза но точно выдаст правильный результат.
__________________
Retry, Abort, Ignore? █
Intel Core i7-9700 4.70 Ghz; 64Gb; Nvidia RTX 3070
AMD Ryzen 7 3800X 4.3Ghz; 64Gb; Nvidia 1070Ti
AMD Ryzen 7 1700X 3.4Ghz; 8Gb; AMD RX 570
AMD Athlon II 2.6Ghz; 8Gb; Nvidia GTX 750 Ti
|
(Offline)
|
|
26.10.2011, 00:59
|
#11
|
[object Object]
Регистрация: 01.08.2008
Адрес: В России
Сообщений: 4,359
Написано 2,473 полезных сообщений (для 6,856 пользователей)
|
Ответ: Точка в четырёхугольнике
О чё нарыл:
<?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>"; } ?>
Охреневаю сам от существования подобного
__________________
Retry, Abort, Ignore? █
Intel Core i7-9700 4.70 Ghz; 64Gb; Nvidia RTX 3070
AMD Ryzen 7 3800X 4.3Ghz; 64Gb; Nvidia 1070Ti
AMD Ryzen 7 1700X 3.4Ghz; 8Gb; AMD RX 570
AMD Athlon II 2.6Ghz; 8Gb; Nvidia GTX 750 Ti
|
(Offline)
|
|
26.10.2011, 01:05
|
#12
|
Задрот
Регистрация: 24.07.2009
Адрес: Ивановская область, г. Кинешма
Сообщений: 1,574
Написано 407 полезных сообщений (для 863 пользователей)
|
Ответ: Точка в четырёхугольнике
Автора на кастрацию срочно
|
(Offline)
|
|
26.10.2011, 01:10
|
#13
|
[object Object]
Регистрация: 01.08.2008
Адрес: В России
Сообщений: 4,359
Написано 2,473 полезных сообщений (для 6,856 пользователей)
|
Ответ: Точка в четырёхугольнике
Сообщение от Павел
Автора на кастрацию срочно
|
Алгоритм нормальный.
На остальное плевать.
__________________
Retry, Abort, Ignore? █
Intel Core i7-9700 4.70 Ghz; 64Gb; Nvidia RTX 3070
AMD Ryzen 7 3800X 4.3Ghz; 64Gb; Nvidia 1070Ti
AMD Ryzen 7 1700X 3.4Ghz; 8Gb; AMD RX 570
AMD Athlon II 2.6Ghz; 8Gb; Nvidia GTX 750 Ti
|
(Offline)
|
|
26.10.2011, 01:13
|
#14
|
Задрот
Регистрация: 24.07.2009
Адрес: Ивановская область, г. Кинешма
Сообщений: 1,574
Написано 407 полезных сообщений (для 863 пользователей)
|
Ответ: Точка в четырёхугольнике
Сообщение от Randomize
Использовать Rand? Классная ф-ция получится. Не с первого раза но точно выдаст правильный результат.
|
А чо не так?? Луч в рандомном направлении. В принципе, все равно как юзать - можно и константный, к примеру 90 градусов, для него можно предаврительно A, B, C рассчитать, но rand(360) тащит, не так ли, Randomize?
|
(Offline)
|
|
26.10.2011, 02:15
|
#15
|
Бывалый
Регистрация: 16.09.2011
Сообщений: 863
Написано 257 полезных сообщений (для 546 пользователей)
|
Ответ: Точка в четырёхугольнике
Сообщение от Павел
А чо не так?? Луч в рандомном направлении. В принципе, все равно как юзать - можно и константный, к примеру 90 градусов, для него можно предаврительно A, B, C рассчитать, но rand(360) тащит, не так ли, Randomize?
|
можно тупо 0 градусов )
Ибо если будит 0 пересечений, тогда снаружи.
|
(Offline)
|
|
Ваши права в разделе
|
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения
HTML код Выкл.
|
|
|
Часовой пояс GMT +4, время: 02:24.
|