Точка в многоугольнике

Форум » Для флейма » Точка в многоугольнике » Ответить

Точка в многоугольнике

fil: Всем привет ! Требуется узнать - входит ли точка в некий сложный многоугольник (район на карте) Координаты точки и список координат границ многоугольника имеются. Может писал кто такой алгоритм ?

Ответов - 5

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

Dima: Можно погуглить или покурить 3 страницы http://www.cyberforum.ru/cpp-beginners/thread570427.html

fil: Вот так, вроде, работает lOk:=.F. pnt:={Y, X} // точка dim:={{Y,X},{Y,X},,,{Y,X}} // координаты вершин многоугольника for st=1 to len(dim)-1 cmp:={iif(pnt[1] > dim[st,1],1,0), iif(pnt[1] <= dim[st+1,1],1,0)} if cmp[1]+cmp[2]!=1 if pnt[2] - dim[st, 2] < (pnt[1] - dim[st, 1]) * ; (dim[st+1, 2] - dim[st, 2]) / (dim[st+1, 1] - dim[st, 1]) lOk:=! lOk endif endif next

SadStar2019: решил проверить от нечего делать набросал код файл окна wMain.fmg [pre] DEFINE WINDOW TEMPLATE AT 147,365 HEIGHT 282 WIDTH 817 TITLE "Dot in area - test" MAIN ON INIT wInit() ON RELEASE wClose() FONT "Arial" SIZE 9 DEFINE LABEL LABEL_1 COL 10 ROW 16 VALUE "координаты точки {n,n}:" ACTION Nil WIDTH 182 HEIGHT 16 AUTOSIZE .F. FONTNAME "Arial" FONTSIZE 10 FONTBOLD .T. FONTITALIC .F. FONTUNDERLINE .F. FONTSTRIKEOUT .F. TOOLTIP Nil BACKCOLOR Nil FONTCOLOR Nil BORDER .f. CLIENTEDGE .f. HSCROLL .f. VSCROLL .f. TRANSPARENT .F. RIGHTALIGN .T. HELPID Nil VISIBLE .T. END LABEL DEFINE TEXTBOX txt_dotXY COL 205 ROW 12 WIDTH 271 HEIGHT 28 VALUE Nil READONLY .F. FONTNAME "Arial" FONTSIZE 10 FONTBOLD .T. FONTITALIC .F. FONTUNDERLINE .F. FONTSTRIKEOUT .F. PASSWORD .F. TOOLTIP Nil BACKCOLOR Nil FONTCOLOR Nil INPUTMASK Nil FORMAT Nil MAXLENGTH Nil UPPERCASE .F. LOWERCASE .F. ONGOTFOCUS Nil ONCHANGE Nil ONLOSTFOCUS Nil ONENTER Nil RIGHTALIGN .F. VISIBLE .T. TABSTOP .T. HELPID Nil END TEXTBOX DEFINE LABEL LABEL_2 COL 12 ROW 60 VALUE "координаты углов {n,n}:" ACTION Nil WIDTH 182 HEIGHT 16 AUTOSIZE .F. FONTNAME "Arial" FONTSIZE 10 FONTBOLD .T. FONTITALIC .F. FONTUNDERLINE .F. FONTSTRIKEOUT .F. TOOLTIP Nil BACKCOLOR Nil FONTCOLOR Nil BORDER .f. CLIENTEDGE .f. HSCROLL .f. VSCROLL .f. TRANSPARENT .F. RIGHTALIGN .T. HELPID Nil VISIBLE .T. END LABEL DEFINE TEXTBOX txt_AnglesXY COL 204 ROW 52 WIDTH 596 HEIGHT 28 VALUE Nil READONLY .F. FONTNAME "Arial" FONTSIZE 10 FONTBOLD .T. FONTITALIC .F. FONTUNDERLINE .F. FONTSTRIKEOUT .F. PASSWORD .F. TOOLTIP Nil BACKCOLOR Nil FONTCOLOR Nil INPUTMASK Nil FORMAT Nil MAXLENGTH Nil UPPERCASE .F. LOWERCASE .F. ONGOTFOCUS Nil ONCHANGE Nil ONLOSTFOCUS Nil ONENTER Nil RIGHTALIGN .F. VISIBLE .T. TABSTOP .T. HELPID Nil END TEXTBOX DEFINE BUTTON btn_Exit COL 696 ROW 12 WIDTH 100 HEIGHT 24 CAPTION "Exit" PICTURE Nil ICON Nil ACTION wMain.release() FONTNAME "Arial" FONTSIZE 10 FONTBOLD .T. FONTITALIC .F. FONTUNDERLINE .F. FONTSTRIKEOUT .F. FONTCOLOR Nil ONGOTFOCUS Nil ONLOSTFOCUS Nil HELPID Nil FLAT .F. TABSTOP .T. TRANSPARENT .F. TOOLTIP Nil VISIBLE .T. DEFAULT .F. END BUTTON DEFINE BUTTON btn_Check COL 204 ROW 104 WIDTH 100 HEIGHT 24 CAPTION "Check" PICTURE Nil ICON Nil ACTION Start() FONTNAME "Arial" FONTSIZE 10 FONTBOLD .T. FONTITALIC .F. FONTUNDERLINE .F. FONTSTRIKEOUT .F. FONTCOLOR Nil ONGOTFOCUS Nil ONLOSTFOCUS Nil HELPID Nil FLAT .F. TABSTOP .T. TRANSPARENT .F. TOOLTIP Nil VISIBLE .T. DEFAULT .F. END BUTTON DEFINE LABEL LABEL_3 COL 12 ROW 144 VALUE "координаты углов {n,n}:" ACTION Nil WIDTH 182 HEIGHT 16 AUTOSIZE .F. FONTNAME "Arial" FONTSIZE 10 FONTBOLD .T. FONTITALIC .F. FONTUNDERLINE .F. FONTSTRIKEOUT .F. TOOLTIP Nil BACKCOLOR Nil FONTCOLOR Nil BORDER .f. CLIENTEDGE .f. HSCROLL .f. VSCROLL .f. TRANSPARENT .F. RIGHTALIGN .T. HELPID Nil VISIBLE .T. END LABEL DEFINE TEXTBOX txt_Result COL 204 ROW 136 WIDTH 271 HEIGHT 28 VALUE Nil READONLY .F. FONTNAME "Arial" FONTSIZE 10 FONTBOLD .T. FONTITALIC .F. FONTUNDERLINE .F. FONTSTRIKEOUT .F. PASSWORD .F. TOOLTIP Nil BACKCOLOR Nil FONTCOLOR Nil INPUTMASK Nil FORMAT Nil MAXLENGTH Nil UPPERCASE .F. LOWERCASE .F. ONGOTFOCUS Nil ONCHANGE Nil ONLOSTFOCUS Nil ONENTER Nil RIGHTALIGN .F. VISIBLE .T. TABSTOP .T. HELPID Nil END TEXTBOX END WINDOW[/pre] файл программы dot.prg [pre] #include <minigui.ch> #define CRLF HB_OsNewLine() Function Main //сетевая версия public cIniFile:='Dot.ini' Load Window wMain wMain.txt_Result.Enabled:=.f. //Center Window wMain Activate Window wMain Return *-------------------------------------------------------- static function wInit() local txt BEGIN INI FILE cIniFile GET txt SECTION "Save" ENTRY "txt_dotXY" DEFAULT "" wMain.txt_dotXY.Value:=txt GET txt SECTION "Save" ENTRY "txt_AnglesXY" DEFAULT "" wMain.txt_AnglesXY.Value:=txt END INI return NIL *-------------------------------------------------------- static function wClose() BEGIN INI FILE cIniFile SET SECTION "Save" ENTRY "txt_dotXY" TO wMain.txt_dotXY.Value SET SECTION "Save" ENTRY "txt_AnglesXY" TO wMain.txt_AnglesXY.Value END INI return NIL *-------------------------------------------------------- static function Start() local lOk:=.F. //pnt:={Y, X} // точка local t1:=wMain.txt_dotXY.Value local pnt:=&t1 // точка local t2:=wMain.txt_AnglesXY.Value local dim:=&t2 //{{Y,X},{Y,X},,,{Y,X}} // координаты вершин многоугольника for st=1 to len(dim)-1 cmp:={iif(pnt[1] > dim[st,1],1,0), iif(pnt[1] <= dim[st+1,1],1,0)} if cmp[1]+cmp[2]!=1 if pnt[2] - dim[st, 2] < (pnt[1] - dim[st, 1]) * ; (dim[st+1, 2] - dim[st, 2]) / (dim[st+1, 1] - dim[st, 1]) lOk:=! lOk endif endif next wMain.txt_Result.Value:=iif(lOk,"the point inside the figure", "the point OutSide the figure") return NIL[/pre] фигура {{1,1},{2,4},{4,5},{5,2},{3,0}} точка {2,0} определяется неправильно Я накосячил или алгоритм? P.S. А если фигура не выпуклая? P.S.2 "Все уже украдено до нас" https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83

fil: Многоугольник выпуклый. Это район на карте. Массив точек {{1,1},{2,4},{4,5},{5,2},{3,0},{1,1}} 1 элемент = последнему

полная версия страницы