Точка пересечения двух отрезков

MrFOX · 07.08.2014, 15:01

Вот код:

Код AS3:

import flash.display.Shape;
 
//Создаем первый отрезок...
var Line1:Shape = new Shape  ;
addChild(Line1);
var Line1x1 = 160; //Начальная точка по оси Х для первого отрезка
var Line1y1 = 300; //Начальная точка по оси Y для первого отрезка
var Line1x2 = 150; //Конечная точка по оси Х для первого отрезка
var Line1y2 = 100; //Конечная точка по оси Y для первого отрезка
Line1.graphics.clear();
Line1.graphics.lineStyle(0, 0x00FF00, 1);
Line1.graphics.moveTo(Line1x1, Line1y1);
Line1.graphics.lineTo(Line1x2, Line1y2);
var angle1 = Math.atan2(Line1y2 - Line1y1, Line1x2 - Line1x1) / (Math.PI / 180); //Угол первого отрезка
 
//Создаем второй отрезок...
var Line2:Shape = new Shape  ;
addChild(Line2);
var Line2x1 = 195; //Начальная точка по оси Х для второго отрезка
var Line2y1 = 355; //Начальная точка по оси Y для второго отрезка
var Line2x2 = 100; //Конечная точка по оси Х для второго отрезка
var Line2y2 = 100; //Конечная точка по оси Y для второго отрезка
Line2.graphics.clear();
Line2.graphics.lineStyle(0, 0x0000FF, 1);
Line2.graphics.moveTo(Line2x1, Line2y1);
Line2.graphics.lineTo(Line2x2, Line2y2);
var angle2 = Math.atan2(Line2y2 - Line2y1, Line2x2 - Line2x1) / (Math.PI / 180); //Угол второго отрезка
 
var k1 = Math.tan(angle1 * Math.PI / 180);
var b1 = Line1y2 - k1 * Line1x2;
 
var k2 = Math.tan(angle2 * Math.PI / 180);
var b2 = Line2y2 - k2 * Line2x2;
 
var x0 = (b1 - b2) / (k2 - k1);
var y0 = k1 * x0 + b1;
 
if (((x0>=Line1x1 && x0<=Line1x2) || (x0<=Line1x1 && x0>=Line1x2)) && ((y0>=Line1y1 && y0<=Line1y2) || (y0<=Line1y1 && y0>=Line1y2)))
{
   var line1B = true;
}
if (((x0>=Line2x1 && x0<=Line2x2) || (x0<=Line2x1 && x0>=Line2x2)) && ((y0>=Line2y1 && y0<=Line2y2) || (y0<=Line2y1 && y0>=Line2y2)))
{
   var line2B = true;
}
if (line1B && line2B)
{
   trace("x0 = " + x0)
   trace("y0 = " + y0)
}

Цель кода:Найти точку пересечения двух отрезков.

Код вроде работает хорошо, но если начальную координату Х для первого отрезка (переменная Line1x1) на 150, то точка пересечения этих отрезков не находиться, хотя визуально она есть.
Прошу помочь с кодом.

Alex Lexcuk · 07.08.2014, 22:28

Тут все не так просто, нужно сначала определить пересекаются ли отрезки в принципе, затем
не углами, через углы не true.

Код AS3:

		public function lineCross(b:Point, e:Point, b1:Point, e1:Point):Boolean {
			//взято с http://progs-maker.narod.ru/algor.html
			var x1:Number = b.x;
			var y1:Number = b.y;
			var x2:Number = e.x;
			var y2:Number = e.y;
			var x3:Number = b1.x;
			var y3:Number = b1.y;
			var x4:Number = e1.x;
			var y4:Number = e1.y;
 
			var maxx1:Number = Math.max(x1, x2);
			var maxy1:Number = Math.max(y1, y2);
			var minx1:Number = Math.min(x1, x2);
			var miny1:Number = Math.min(y1, y2);
			var maxx2:Number = Math.max(x3, x4);
			var maxy2:Number = Math.max(y3, y4);
			var minx2:Number = Math.min(x3, x4);
			var miny2:Number = Math.min(y3, y4);
 
			var dx21:Number = x2 - x1, dy21:Number = y2 - y1; // Длина проекций первой линии на ось x и y
			var dx43:Number = x4 - x3, dy43:Number = y4 - y3; // Длина проекций второй линии на ось x и y
			var dx13:Number = x1 - x3, dy13:Number = y1 - y3;
 
			var div:Number, mul:Number;
			div = dy43 * dx21 - dx43 * dy21;
			if (div == 0) 
			return false; // Линии параллельны...
 
			if (div > 0) {
				mul = dx43 * dy13 - dy43 * dx13;
				if (mul < 0 || mul > div)
				return false; // Первый отрезок пересекается за своими границами...
				mul = dx21 * dy13 - dy21 * dx13;
				if (mul < 0 || mul > div) return false; // Второй отрезок пересекается за своими границами...
			} else
			{
				mul = - (dx43 * dy13 - dy43 * dx13);
				if (mul  < 0 || mul > -div)
				return false; // Первый отрезок пересекается за своими границами...
				mul = - (dx21 * dy13 - dy21 * dx13);
				if (mul < 0 || mul > -div)
				return false; // Второй отрезок пересекается за своими границами...
			}
		return true;
		}
 
		public function lineIntersect(lineAP1:Point, lineAP2:Point, lineBP1:Point, lineBP2:Point):Point {
			// http://forum.vingrad.ru/faq/topic-157574.html
			var lDetlineA:Number, lDetlineB:Number, lDetDivInv:Number, 
			lDiffLA:Point, lDiffLB :Point,
			result:Point = new Point;
			lDetlineA = lineAP1.x*lineAP2.y - lineAP1.y*lineAP2.x;
			lDetlineB = lineBP1.x*lineBP2.y - lineBP1.y*lineBP2.x;
 
			lDiffLA = lineAP1.subtract(lineAP2);
			lDiffLB = lineBP1.subtract(lineBP2);
 
			lDetDivInv = 1 / ((lDiffLA.x*lDiffLB.y) - (lDiffLA.y*lDiffLB.x));
 
			result.x = ((lDetlineA*lDiffLB.x) - (lDiffLA.x*lDetlineB)) * lDetDivInv;
			result.y = ((lDetlineA*lDiffLB.y) - (lDiffLA.y*lDetlineB)) * lDetDivInv;
			return result;
		}

Тут демка
http://www.murmadillo.tut.su/html/li...Intersect.html

nubideus · 08.08.2014, 03:42

я как то ковырял точку пересечения прямых, там все проще, во втором посте до абсурда мудренно. завтра найду/напишу

MrFOX · 08.08.2014, 16:55

Я не совсем понял, что за координаты возвращает переменная result. Если координаты точки пересечения, то они не верные.

Может это я что-то неправильно сделал...Вот код, который я изменил под себя:

Код AS3:

package 
{
	import flash.display.MovieClip;
	import flash.geom.Point;
	import flash.display.Shape;
 
	public class DDD extends MovieClip
	{
		public function DDD()
		{
			trace("НАЧАЛО");
			var Line1:Shape = new Shape  ;
			addChild(Line1);
			var Line1x1 = 160;//Начальная точка по оси Х для первого отрезка
			var Line1y1 = 300;//Начальная точка по оси Y для первого отрезка
			var Line1x2 = 150;//Конечная точка по оси Х для первого отрезка
			var Line1y2 = 100;//Конечная точка по оси Y для первого отрезка
			Line1.graphics.clear();
			Line1.graphics.lineStyle(0, 0x00FF00, 1);
			Line1.graphics.moveTo(Line1x1, Line1y1);
			Line1.graphics.lineTo(Line1x2, Line1y2);
 
			var FF:Point = new Point  ;
			//Создаем второй отрезок...
			var Line2:Shape = new Shape  ;
			addChild(Line2);
			var Line2x1 = 195;//Начальная точка по оси Х для второго отрезка
			var Line2y1 = 355;//Начальная точка по оси Y для второго отрезка
			var Line2x2 = 100;//Конечная точка по оси Х для второго отрезка
			var Line2y2 = 100;//Конечная точка по оси Y для второго отрезка
			Line2.graphics.clear();
			Line2.graphics.lineStyle(0, 0x0000FF, 1);
			Line2.graphics.moveTo(Line2x1, Line2y1);
			Line2.graphics.lineTo(Line2x2, Line2y2);
 
			var Line1Point1:Point = new Point(Line1x1,Line1y1);
			var Line1Point2:Point = new Point(Line1x2,Line1y2);
 
			var Line2Point1:Point = new Point(Line2x1,Line2y1);
			var Line2Point2:Point = new Point(Line2x2,Line2y2);
 
			trace(lineIntersect(Line1Point1,Line2Point1,Line1Point2,Line2Point2))
 
		}
 
		private function lineCross(b:Point, e:Point, b1:Point, e1:Point):Boolean
		{
			//взято с http://progs-maker.narod.ru/algor.html
			var x1:Number = b.x;
			var y1:Number = b.y;
			var x2:Number = e.x;
			var y2:Number = e.y;
			var x3:Number = b1.x;
			var y3:Number = b1.y;
			var x4:Number = e1.x;
			var y4:Number = e1.y;
 
			trace (x1)
 
			var maxx1:Number = Math.max(x1,x2);
			var maxy1:Number = Math.max(y1,y2);
			var minx1:Number = Math.min(x1,x2);
			var miny1:Number = Math.min(y1,y2);
			var maxx2:Number = Math.max(x3,x4);
			var maxy2:Number = Math.max(y3,y4);
			var minx2:Number = Math.min(x3,x4);
			var miny2:Number = Math.min(y3,y4);
 
			var dx21:Number = x2 - x1,dy21:Number = y2 - y1;// Длина проекций первой линии на ось x и y
			var dx43:Number = x4 - x3,dy43:Number = y4 - y3;// Длина проекций второй линии на ось x и y
			var dx13:Number = x1 - x3,dy13:Number = y1 - y3;
 
			var div:Number,mul:Number;
			div = dy43 * dx21 - dx43 * dy21;
			if (div == 0)
			{
				trace ("ПАРАЛЕЛЬНЫ")
				return false;
			}// Линии параллельны...
			if (div > 0)
			{
				mul = dx43 * dy13 - dy43 * dx13;
				if (mul < 0 || mul > div)
				{
					return false;
				}// Первый отрезок пересекается за своими границами...
				mul = dx21 * dy13 - dy21 * dx13;
				if (mul < 0 || mul > div)
				{
					return false;
				}// Второй отрезок пересекается за своими границами...
			}
			else
			{
				mul = - (dx43 * dy13 - dy43 * dx13);
				if (mul  < 0 || mul > -div)
				{
					return false;
				}// Первый отрезок пересекается за своими границами...
				mul = - (dx21 * dy13 - dy21 * dx13);
				if (mul < 0 || mul > -div)
				{
					return false;
				}// Второй отрезок пересекается за своими границами...
			}
			return true;
		}
 
		public function lineIntersect(lineAP1:Point, lineAP2:Point, lineBP1:Point, lineBP2:Point):Point
		{
			// http://forum.vingrad.ru/faq/topic-157574.html
			var lDetlineA:Number, lDetlineB:Number, lDetDivInv:Number, 
			lDiffLA:Point, lDiffLB :Point,
			result:Point = new Point;
			lDetlineA = lineAP1.x * lineAP2.y - lineAP1.y * lineAP2.x;
			lDetlineB = lineBP1.x * lineBP2.y - lineBP1.y * lineBP2.x;
 
			lDiffLA = lineAP1.subtract(lineAP2);
			lDiffLB = lineBP1.subtract(lineBP2);
 
			lDetDivInv = 1 / ((lDiffLA.x*lDiffLB.y) - (lDiffLA.y*lDiffLB.x));
 
			result.x = ((lDetlineA*lDiffLB.x) - (lDiffLA.x*lDetlineB)) * lDetDivInv;
			result.y = ((lDetlineA*lDiffLB.y) - (lDiffLA.y*lDetlineB)) * lDetDivInv;
			return result;
		}
 
	}
 
}

И когда линии параллельны, переменная div не была равна 0.

nuToH · 08.08.2014, 17:13

Не уверен, что в тему, но возможно будет полезно:

Код AS3:

public static function isIntersection(a1:Point, a2:Point, b1:Point, b2:Point, intersectPoint:Point = null):Boolean {
	var de:Number = (b2.y - b1.y) * (a2.x - a1.x) - (b2.x - b1.x) * (a2.y - a1.y);
	if(de != 0.0) {
		var u0:Number = (b2.x - b1.x) * (a1.y - b1.y) - (b2.y - b1.y) * (a1.x - b1.x) / de;
		var u1:Number = (b1.x - a1.x) * (a2.y - a1.y) - (b1.y - a1.y) * (a2.x - a1.x) / de; 
		if((u0 >= 0.0) && (u0 <= 1.0) && (u1 >= 0.0) && (u1 <= 1.0)) {
			if(intersectPoint != null) {
				intersectPoint.x = a1.x + u0 * (a2.x - a1.x);
				intersectPoint.y = a1.y + u0 * (a2.y - a1.y);
			}
			return true;
		}
	}
	return false;
}

a1 - а2 - первый отрезок.
б1 - б2 - второй.
Ф-ция возвращает факт пересечения. Доп. аргументом можно задать точку, куда запишутся координаты пересечения.

MrFOX · 08.08.2014, 19:40

nuToH, как раз таки это в тему. Спасибо!

pytachok · 10.08.2014, 13:13

Пользуюсь вот этой функцией: Аналог как у nuToH, только возвращает точку пересечения.

Код AS3:

public function IsLinesCross(x11:Number, y11:Number, x12:Number, y12:Number, 
											x21:Number, y21:Number, x22:Number, y22:Number):Point
		{
 
			// решаем систему методом Крамера
			var d:Number = (x12 - x11) * (y21 - y22) - (x21 - x22) * (y12 - y11);
 
			if (d == 0) return null; // Отрезки либо параллельны, либо полностью/частично совпадают
 
			var d1:Number = (x21 - x11) * (y21 - y22) - (x21 - x22) * (y21 - y11);
			var d2:Number = (x12 - x11) * (y21 - y11) - (x21 - x11) * (y12 - y11);
 
			var t1:Number = d1 / d;
			var t2:Number = d2 / d;
 
			if (t1 >= 0 && t1 <= 1 && t2 >= 0 && t2 <= 1) 
			{
				var rX:Number = ((x11 * y12 - y11 * x12) * (x21 - x22) - 
							(x11 - x12) * (x21 * y22 - y21 * x22)) /
							((x11 - x12) * (y21 - y22) - (y11 - y12) * (x21 - x22));
				var rY:Number = ((x11 * y12 - y11 * x12) * (y21 - y22) - 
							(y11 - y12) * (x21 * y22 - y21 * x22)) /
							((x11 - x12) * (y21 - y22) - (y11 - y12) * (x21 - x22));
				return new Point(rX, rY);
			}
			else return null; // не пересекаются
		}