Блог пользователя SkyHawk

Автор SkyHawk, 13 лет назад, По-русски

Требуется помощь в дебаге.


Вот задача. Если в двух словах: проверить принадлежность точки треугольнику.
Вот код.

Приветствуются: 
  • Чьё-либо решение этой задачи.
  • Аналогичные задачи с других сайтов - потестить.
  • Найденные баги в моем коде.
Спасибо!

P.s. В тему - треугольный велосипед.



UPD. Всем большое спасибо!
  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Ошибка в проверке знаков углов, когда точка на границе

например, 3 0 3 -2 0 -2 0 0 

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Пример не осознал, но ошибку понял, спасибо огромное!
»
13 лет назад, # |
Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится
import java.awt.Polygon;
import java.awt.geom.Line2D
import java.io.FileReader; import java.io.FileWriter; import java.io.IOException; import java.util.Scanner; public class Main { public static void main(String []args) throws IOException { Scanner sc=new Scanner(new FileReader("INPUT.TXT")); FileWriter fw=new FileWriter("OUTPUT.TXT"); int []x=new int[3]; int []y=new int[3]; Line2D[]lines=new Line2D[3]; for(int i=0;i<3;i++) { x[i]=sc.nextInt(); y[i]=sc.nextInt(); } int xp=sc.nextInt(); int yp=sc.nextInt(); Line2D L2=new Line2D.Double(xp, yp, xp, yp); for(int i=0;i<3;i++) { lines[i]=new Line2D.Double(x[i],y[i], x[(i+1)%3],y[(i+1)%3] ); if(lines[i].intersectsLine(L2)) { fw.write("In"); fw.close(); return ; } } Polygon p=new Polygon(x,y,3); if(p.contains(xp,yp)) fw.write("In"); else fw.write("Out"); fw.close(); } }
»
13 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится
Я знаю как минимум три способа решения задачи:

1) Использовать большую библиотечку для проверки принадлежности точки многоугольнику.
2) Рассмотрим прямые P1P2, P2P3, P3P1 и проверим, что точка лежит по одну и ту же сторону относительно каждой из них.
3) Пусть данная точка - P. Проверим, что сумма площадей треугольников P1P2P, P2P3P, P3P1P равна площади треугольника P1P2P3
  • »
    »
    13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Методы я тоже знаю, просто очень не хотелось их писать и хотелось узнать в чем ошибка именно у меня. Спасибо Bugman, теперь знаю.

»
13 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#define eps 1e-7
using namespace std;

int n;

double area(int x1,int y1,int x2,int y2,int x3,int y3)
 {
  return 0.5*abs(x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2));
 }

int main()
{
 #ifndef ONLINE_JUDGE
  freopen("input.txt","rt",stdin);
  freopen("output.txt","wt",stdout);
 #endif

  int x1,x2,x3,y1,y2,y3,px,py;
  scanf("%d%d%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3,&px,&py);
  if (fabs(area(x1,y1,x2,y2,x3,y3)-(area(x1,y1,x2,y2,px,py)+
  area(x1,y1,x3,y3,px,py)+area(x2,y2,x3,y3,px,py)))<=eps) printf("In"); else printf("Out");

 fclose(stdin);fclose(stdout);
 return 0;
}