Среда программирования:
IntelliJ IDEA
Статья по теме:
Задача: Определить, принадлежит ли точка выпуклому многоугольнику.
Алгоритм: Выберем произвольную точку ( кликом мышки ).
Используя векторное произведение, проверим по очереди в порядке обхода сторон по часовой стрелке, лежит ли точка слева от очередного вектора - стороны многоугольника
( откладываем вектора: от i-й вершины к i-1-й вершине, и от i-й вершины к выбранной точке).
Если векторное произведение неотрицательно, значит точка лежит слева от стороны многоугольника, либо на стороне. Если это выполняется для каждой из сторон, то точка лежит внутри многоугольника.
Код программы:
package sample; import com.sun.xml.internal.bind.v2.schemagen.xmlschema.Annotation; import javafx.geometry.Point2D; import javafx.scene.canvas.GraphicsContext; public class Check { private int n = 6; //количество вершин многоугольника private Point2D Poly[] = new Point2D[] { new Point2D(200, 170), new Point2D(320, 120), new Point2D(440, 170), new Point2D(440, 250), new Point2D(320, 300), new Point2D(200, 250), }; //возвращает true, если точка лежит слева от прямой private boolean vector_mult (Point2D A, Point2D B, double click_X, double click_Y) { if(((B.getX()-A.getX())*(click_Y - A.getY()) - (B.getY()-A.getY())*(click_X - A.getX())) >= 0) return true; else return false; } public void DrPoly (GraphicsContext g_c) { //отрисовка многоугольника for(int i = 0; i < n-1; i++) { g_c.strokeLine(Poly[i].getX(), Poly[i].getY(), Poly[i+1].getX(), Poly[i+1].getY()); } g_c.strokeLine(Poly[n-1].getX(), Poly[n-1].getY(), Poly[0].getX(), Poly[0].getY()); } public boolean check_attachment (double click_X, double click_Y) { //возвращает true, если точка лежит слева от каждой прямой for(int i = 0; i < n-1; i++) { if(!vector_mult(Poly[i], Poly[i+1], click_X, click_Y)) return false; } if (vector_mult(Poly[n-1], Poly[0], click_X, click_Y)) return true; else return false; } }
Прикрепленный файл | Размер |
---|---|
leonidchenko_pointchecker.zip | 19.33 кб |