Версия для печати темы

Автор: milfes 6.01.2007 1:40

Пожалуйсто помогите решить задачу:
Дано множество отрезков, заданых координатами концов. Определить количество точек пересечения.
Вот что я сам написал:

program graphpoints;
uses crt,graph;
const nmax=100;
type t_kor=record
                 xn,yn,xk,yk:integer;
     end;
var kor:array[1..nmax] of t_kor;
    i,k,n,j,y,maxx,maxy,driver,mode:integer;
    r1,r2,ra,rb,r:real;

procedure generatedata;
      var i:integer;
      begin
          for i:=1 to n do
          begin
            kor[i].xn:=random(maxx);
            kor[i].yn:=random(maxy);
            kor[i].xk:=random(maxx);
            kor[i].yk:=random(maxy);
            line(kor[i].xn,kor[i].yn,kor[i].xk,kor[i].yk);
          end;
      end;

begin
  randomize;
  write('Введите количество отрезков ');
  readln(n);
  driver:=detect;
  initgraph(driver,mode,'d:\tp\bgi');
  maxx:=getmaxx;
  maxy:=getmaxy;
  generatedata;
  readkey;
  closegraph;
  k:=0;
  for i:=1 to n-1 do
  begin
      for j:=i+1 to n do
      begin
          r1:=(kor[j].xn-kor[i].xn)*(kor[i].yk-kor[i].yn)-(kor[j].yn-kor[i].yn)*(kor[i].xk-kor[i].xn);
          r:= (kor[i].yk-kor[i].yn)*(kor[j].xn-kor[j].xk)-(kor[j].yn-kor[j].yk)*(kor[i].xk-kor[i].xn);
          r2:=(kor[j].xn-kor[j].xk)*(kor[j].yn-kor[i].yn)-(kor[j].yn-kor[j].yk)*(kor[j].xn-kor[i].xn);
          ra:=r1/r;
          rb:=r2/r;
          if (ra<=1) and (ra>=0) and (rb>=0) and (rb<=1) then
             k:=k+1
      end;
  end;
  writeln('Количество точек пересечения ',k);
  readkey;
end.

Программа работает неправильно, число пересечение выводится меньше, чем на самом деле.

Автор: Bokul 6.01.2007 1:51

У тебя не правильно проверяются пересечение отрезков, http://algolist.manual.ru/maths/geom/intersect/lineline2d.php

Автор: milfes 6.01.2007 2:04

Спасибо, ща попробую исправить.

Автор: milfes 6.01.2007 5:28

Вот изменил:

r1:=(kor[j].xk-kor[j].xn)*(kor[i].yn-kor[j].yn)-(kor[j].yk-kor[j].yn)*(kor[i].xn-kor[j].xn);
r:= (kor[j].yk-kor[j].yn)*(kor[i].xk-kor[i].xn)-(kor[i].yk-kor[i].yn)*(kor[j].xk-kor[j].xn);
r2:=(kor[i].xk-kor[i].xn)*(kor[i].yn-kor[j].yn)-(kor[i].yk-kor[i].yn)*(kor[i].xn-kor[j].xn);

Но результат остался прежним.

Автор: volvo 6.01.2007 6:18

milfes, у тебя может не хватать разрядности (промежуточный результат вычисления, например, (kor[j].xk-kor[j].xn)*(kor[i].yn-kor[j].yn), не поместится в Integer, и усечется - в результате получишь неверные значения Ra, Rb) и в итоге - некорректный результат... Я бы переходил сразу на Real:

r1:=1.0 * (kor[j].xk-kor[j].xn) * 1.0 * (kor[i].yn-kor[j].yn)-
    1.0 * (kor[j].yk-kor[j].yn) * 1.0 * (kor[i].xn-kor[j].xn);
r:= 1.0 * (kor[j].yk-kor[j].yn) * 1.0 * (kor[i].xk-kor[i].xn)-
    1.0 * (kor[i].yk-kor[i].yn) * 1.0 * (kor[j].xk-kor[j].xn);
r2:=1.0 * (kor[i].xk-kor[i].xn) * 1.0 * (kor[i].yn-kor[j].yn)-
    1.0 * (kor[i].yk-kor[i].yn) * 1.0 * (kor[i].xn-kor[j].xn);

- тогда промежуточные значения гарантированно будут в типе Real, и результат должен быть правильным... Попробуй...

Автор: milfes 6.01.2007 6:30

Спасибо.