我尝试使用该代码查找使用区域的“点是否位于三角形内”。通过这种方式,我可以找到“点是否位于多边形内”的答案,因为可以制作出任何多边形由一个或多个三角形组成。但是当多边形有更多边时,此方法将很复杂。我想知道是否有另一种更简单的方法可以在Java中实现。
这是我的代码,用于查找“点是否位于三角形内”。
class PointInTriangle {
static double AreaofTriangle(int x1,int y1,int x2,int y2,int x3,int y3){
return 0.5*(double)Math.abs(x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2));
}
static boolean isInTriangle(int x1,int y1,int x2,int y2,int x3,int y3,int px,int py){
double bigArea,area1,area2,area3;
bigArea = AreaofTriangle(x1, y1, x2, y2, x3, y3);
area1 = AreaofTriangle(px, py, x2, y2, x3, y3);
area2 = AreaofTriangle(x1, y1, px, py, x3, y3);
area3 = AreaofTriangle(x1, y1, x2, y2, px, py);
if(bigArea == (area1+area2+area3)) {
return true;
}
return false;
}
public static void main(String[]args){
Scanner in = new Scanner(System.in);
System.out.println("Enter three points of triangle:");// (x1,y1) , (x2,y2) , (x3,y3)
int x1,y1,x2,y2,x3,y3,px,py;
x1 = in.nextInt();
y1 = in.nextInt();
x2 = in.nextInt();
y2 = in.nextInt();
x3 = in.nextInt();
y3 = in.nextInt();
System.out.println("\nEnter searching point:");// (px,py)
px = in.nextInt();
py = in.nextInt();
if(isInTriangle(x1, y1, x2, y2, x3, y3, px, py)){
System.out.println("\nExtra point is in the triangle");
}
else{
System.out.println("\nExtra point is not in the triangle");
}
}
}
最佳答案
Wikipedia在Even–odd rule上有直接解决此问题的方法。这是Java实现的示例:
class Point {
int x;
int y;
Point(int x, int y){
this.x = x;
this.y = y;
}
}
public class Testing {
Point[] polygon;
Testing(Point[] polygon) {
this.polygon = polygon;
}
public static void main(final String[] args) {
Point[] polygon = {new Point(5,11), new Point(4,4), new Point(11,2), new Point(2,2)};
Testing test = new Testing(polygon);
Point pOutside = new Point(6,6);
Point pInside = new Point(3,3);
System.out.println(test.isInsideByEvenOddRule(pOutside)); // false
System.out.println(test.isInsideByEvenOddRule(pInside)); // true
}
// java implementation of https://en.wikipedia.org/wiki/Even–odd_rule
boolean isInsideByEvenOddRule(Point point){
boolean result = false;
int j = polygon.length - 1;
for (int i = 0; i < polygon.length; i++) {
if ((polygon[i].y > point.y) != (polygon[j].y > point.y) &&
(point.x < polygon[i].x + (polygon[j].x - polygon[i].x) *
(point.y - polygon[i].y) / (polygon[j].y - polygon[i].y))) {
result = !result;
}
j = i;
}
return result;
}
}