Форум Flasher.ru

Форум Flasher.ru (http://www.flasher.ru/forum/index.php)
-   ActionScript 3.0 (http://www.flasher.ru/forum/forumdisplay.php?f=83)
-   -   координаты точки пересечения (http://www.flasher.ru/forum/showthread.php?t=136366)

greegreeman 15.02.2010 19:02

координаты точки пересечения
 
как узнать координаты точки пересечения прямой и мувиклипа? я проверил при помощи hitTestObject() пересеклась ли моя прямая и мувик. если пересеклась, то в какой точке? помоги, плиз, разобраться

Psycho Tiger 15.02.2010 19:28

Математикой.

greegreeman 15.02.2010 19:35

наверняка уже есть все давно высчитанное до меня. подскажите, где можно найти формулы и применить их

Добавлено через 56 секунд
т.к. у меня опыт во Flash не большой, то я надеялся, что я просто не знаю функцию, которая вернет мне координату точки пересечения... эх...

Crenth 15.02.2010 19:41

Если в двумерном пространстве (на плоскости) искать - то у вас серьезные проблемы :)
Если в трехмерном (т.е. пересечение плоскости мувика и прямой) - то смотрите по ссылке


http://ru.wikipedia.org/wiki/%D0%9D%...80%D0%B8%D1%8F

wvxvw 15.02.2010 19:57

Код AS3:

public static function intersectionPoint(p0:Point, p1:Point, p2:Point, p3:Point):Point
{
    var rX:Number = ((p0.x * p1.y - p0.y * p1.x) * (p2.x - p3.x) -
                    (p0.x - p1.x) * (p2.x * p3.y - p2.y * p3.x)) /
                    ((p0.x - p1.x) * (p2.y - p3.y) - (p0.y - p1.y) * (p2.x - p3.x));
    var rY:Number = ((p0.x * p1.y - p0.y * p1.x) * (p2.y - p3.y) -
                    (p0.y - p1.y) * (p2.x * p3.y - p2.y * p3.x)) /
                    ((p0.x - p1.x) * (p2.y - p3.y) - (p0.y - p1.y) * (p2.x - p3.x));
    return new Point(rX, rY);
}

Только надо дооптимизировать :)

greegreeman 15.02.2010 20:11

я так понимаю "слегка" дооптимизировать :)

silin 15.02.2010 20:34

о пересечении прямой(геометрическое понятие) и мувиклипа (программный объект) и говорить-то не очень серьезно, хотя понятно, что под мувиклипом подразумевается некая фигура, но если неизвестно какая, то какие тут могут быть формулы..

как вариант: прошагать по прямой с каким-то шагом (точностью), походу проверяя hitTestPoint мувика с каждой точкой,
затратно, но будешь все знать: где пресекается, сколько раз и т.д.

Psycho Tiger 16.02.2010 00:12

Однако же, если шаг будет больше, чем линия пересечения - можно тупо перескочить её. Везде свои плюсы и минусы.

wvxvw 16.02.2010 00:17

Цитата:

Сообщение от greegreeman (Сообщение 886739)
я так понимаю "слегка" дооптимизировать :)

Ну, формула-то рабочая - вычисляет точку пересечения двух прямых, а если вам нужны пересечения с кривыми - это уже считаете сами, мой слабый интеллект не справится :)

greegreeman 16.02.2010 01:21

всем спасибо. похоже придется достать конспект по матану и сдуть пыль :) почитать про аппроксимацию. любую (практически любую) сложную фигуру можно свести к простой с определенной степенью точности... а пока что попробую вариант, который предложил silin. буду шагать :)

Партизан 16.02.2010 09:33

Цитата:

Сообщение от greegreeman (Сообщение 886803)
... а пока что попробую вариант, который предложил silin. буду шагать :)

Думаю быстрее и эффектвнее будет отрисовать битмап с мувика и пробежаться по нему.

Котяра 16.02.2010 10:31

аналоговый хак:
отрисовываем мувик в битмапдату1.
отрисовываем красную линию в битмапдату2.
мержим (или copyChanell) битмапдату1 по альфаканалу битмапдаты2 в битмапдату3(размер общий, зависит от заимного расположения).
или так: создаем битмапдату3 ( альфа=0) - размер которой зависит от размеров битмапа1 и битмапа2 и их расположения. копируем красный канал из битмапы2, копируем альфа канал из битмап1.
берём результирующую выборку по красному цвету не 0 альфы (getColorBoundsRect)
размер rect соответствует "степени пересечения"

greegreeman 16.02.2010 10:52

Котяра, а не могли бы вы привести пример кодом, плиз. Я там в начале сразу указал, что у меня опыта не оч много :) моя первая игруха... буду весьма благодарен

Wolsh 16.02.2010 11:02

Цитата:

Однако же, если шаг будет больше, чем линия пересечения - можно тупо перескочить её.
Ну если тупо то можно. А если рисовать прямую, увеличивая ее на шаг - то перескочить не получится. Кроме того, надо использовать сужение поиска - начинать с середины линии и вести поиск границы, ориентируясь на "точка попала" и "точка не попала".

greegreeman 16.02.2010 12:01

на самом деле, Wolsh, конечно прав. у этого алгоритма даже название есть... Wolsh, подскажи, плиз, как рисовать прямую, увеличивая ее шаг, если я пока рисую ее так
Код AS3:

var child:Shape = new Shape();
child.graphics.lineStyle(1, 0x990000);
child.graphics.moveTo(this.x, this.y);
child.graphics.lineTo(dirX, dirY);// dirX, dirY - координаты клика мышкой


Партизан 16.02.2010 12:28

Код AS3:

package {
        import flash.display.BitmapData;
        import flash.display.Shape;
        import flash.display.Sprite;
        import flash.events.Event;
        import flash.geom.Point;
 
        /**
        * ...
        * @author Mikhail Klabukov
        */

        public class Main extends Sprite {
 
                private var shape:Shape = new Shape();
 
                public function Main():void {
                        if (stage)
                                init();
                        else
                                addEventListener(Event.ADDED_TO_STAGE, init);
                }
 
                private function init(e:Event = null):void {
 
                        removeEventListener(Event.ADDED_TO_STAGE, init);
 
                        shape.graphics.beginFill(0xFFCC00);
                        shape.graphics.drawEllipse(200, 200, 100, 250);
                        shape.graphics.endFill()
                        addChild(shape);
 
                        var startLine:Point = new Point(100, 100);
                        var endLine:Point = new Point(500, 550);
 
                        drawLine(startLine, endLine, 0x0000FF);
 
                        checkIntersection(startLine, endLine);
                }
 
                private function checkIntersection(start:Point, end:Point):void {
 
                        var bd:BitmapData = new BitmapData(stage.stageWidth, stage.stageHeight, true, 0);
                        bd.draw(shape)
                        var distance:uint = Point.distance(start, end);
                        end.offset(-start.x, -start.y);
                        var angle:Number = Math.atan2(end.y, end.x);
                        var arr:Array = [];
                        while (distance--){
                                var pnt:Point = Point.polar(distance, angle);
                                pnt.offset(start.x, start.y);
                                var col:uint = bd.getPixel(pnt.x, pnt.y);
                                if (col){
                                        //trace("ПересечениеXY:",uint(pnt.x),uint(pnt.y))
                                        arr.push(pnt);
                                }
                        }
                        if (arr.length){
                                drawLine(arr[0], arr[arr.length - 1]);
 
                                trace("Пересечение:", arr[arr.length - 1], arr[0])
                                trace("Длина пересечения:", uint(Point.distance(arr[0], arr[arr.length - 1])) + "px")
                        }
                }
 
                private function drawLine(start:Point, end:Point, color:Number = 0xff0000):void {
                        var line:Shape = new Shape()
                        line.graphics.lineStyle(2, color);
                        line.graphics.moveTo(start.x, start.y);
                        line.graphics.lineTo(end.x, end.y);
                        line.graphics.endFill();
                        addChild(line);
                }
        }
}


Psycho Tiger 16.02.2010 12:43

Цитата:

Сообщение от Wolsh (Сообщение 886852)
Ну если тупо то можно. А если рисовать прямую, увеличивая ее на шаг - то перескочить не получится. Кроме того, надо использовать сужение поиска - начинать с середины линии и вести поиск границы, ориентируясь на "точка попала" и "точка не попала".

Ну, конечно, если задать шаг в пиксель - то не проскочим - только вот цена такого алгоритма слишком дорога. Я бы так никогда не делал.

Котяра 16.02.2010 13:07

оптимизировать.
1) берем промежуток ограниченный баундсом мувика ( формулу сами посчитаете)
2) делаем шаг в delta = len/2 (посередине)
3) хиттестим.
если false уменьшаем шаг ( дихотомией, фибоначчи, золотым сечением итп) и в 3) так до 1 пикселя, чтоб быть уверенным что проверили всё. чтоб не хиттестить уже проверенные точки, можно их помечать - записывать в массив или еще как, хотя проверка наличия метки может быть дороже хиттеста)
нет здесь никакого экстремума)

wvxvw 16.02.2010 13:21

Цитата:

Сообщение от greegreeman (Сообщение 886803)
всем спасибо. похоже придется достать конспект по матану и сдуть пыль :) почитать про аппроксимацию. любую (практически любую) сложную фигуру можно свести к простой с определенной степенью точности... а пока что попробую вариант, который предложил silin. буду шагать :)

Ну так если точность не особо важна, так проще всего посчитать пересекаются ли окружность и прямая - нужно найти перпендикуляр к прямой проходящий через центр окружности и сравнить его с радиусом (если такой перпендикуляр не пересекается с данным отрезком, или радиус меньше длины перпендикуляра - не пересекаются, в противном случае - пересекаются). Аналогично просто посчитать пересекаются ли отрезок и прямоугольник - если крайняя правая точка отрезка левее прямоугольника, или нижняя точка выше, или крайняя левая - правее, или верхняя - ниже, то не пересекаются, в противном случае - пересекаются. Если вы можете описать многоугольник как массив отрезков - так мой первый вариант - будет самым простым решением т.как он как раз проверяет пересечение двух отрезков, просто переберите все отрезки из которых состоит многоугольник и проверьте пересечение.

VovkaMorkovka1 16.02.2010 14:49

По теме: у меня где - то завалялась геометрическая либа. Определяет пересечение графисеских примитивов с прямыми. Кому надо напомните и вечером вставлю

greegreeman 16.02.2010 15:41

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

Wolsh 16.02.2010 15:54

http://img-novosib.fotki.yandex.ru/g..._967ef1b2_orig
Psycho Tiger, читай внимательней))) Мой ответ был как раз на "шаг в пиксель". Предлагал же я вот что. За четыре "шага" мы сокращаем область поиска в 16 раз.
1. Известно, что линия пересекает фигуру, но ее половина - нет. Остается вторая половина для поиска.
2. Новая линия пересекла фигуру - есть точка без пересечения (середина всей линии) и точка с пересечением - 75% всей линии
3. Сокращаем область еще в два раза. Пересечение есть.
4. Сокращаем область еще в два раза. Пересечения нет.
Продолжаем в том же духе. 10 "шагов" и у нас останется пять точек для точечной проверки. Не надо идти по каждому пикселю линии!

UPD: к сожалению все это только красивая теория. Флэш не сравнивает реальные шейпы, только шейп и точку или bounds шейпов. В реальности даже уменьшая bounds контрольной линии мы рискуем никогда не найти пересечение, так как... его вообще может не быть, хотя hitTestObject и уверяет что есть.
Битмапдата пожалуй на сегодняшний день единственный вариант.

greegreeman 16.02.2010 19:14

наверное метод, который предложил Партизан самый точный...

Добавлено через 3 минуты
Wolsh, то что ты предлагаешь классический алгоритм, который проходят в уневере, так что он по-любому рабочий

krolser 16.02.2010 21:53

А можно вопрос к топикстартеру.
MovieClip можно представить в виде замкнутого многоуголиника (не обязательно выпоклуго) без самопересечений?

Если да, то есть простой алгоритм... (ну почти простой :). Могу расписать.

Psycho Tiger 17.02.2010 00:26

Wolsh, метод поиска делением на 2 мне знаком, но это всё равно не выход, я считаю)

Alex Lexcuk 17.02.2010 00:56

Обрисовать прямыми мувик и тестить на пересечение как wvxvw нaписал. Пример:
http://www.murmadillo.tut.su/html/li...Intersect.html

greegreeman 17.02.2010 01:07

krolser, можно. хотел бы увидеть твой практически простой алгоритм. спасибо. то, что предложил wvxvw тоже работает. надо мувик обрисовать прямыми, закинуть их в массив и проверять на пересечение, а потом юзать его формулы, которые выше. точность будет не высокой. но для некоторых задач ее вполне хватит

krolser 17.02.2010 16:56

Цитата:

Сообщение от Alex Lexcuk (Сообщение 887105)
Обрисовать прямыми мувик и тестить на пересечение как wvxvw нaписал. Пример:
http://www.murmadillo.tut.su/html/li...Intersect.html

После этого мне уже нечего рассказывать :)

greegreeman 17.02.2010 19:22

всем спасибо, узнал много нового :), надеюсь для кого-то это тоже было полезно

miramax 17.02.2010 22:33

Вот уж не думал , что мой, заброшеный на заре моей юности, блог ещё кому-то может помочь http://as3.ru/?p=6 =)
Вроде в статье есть всё необходимое.


Часовой пояс GMT +4, время: 08:16.

Copyright © 1999-2008 Flasher.ru. All rights reserved.
Работает на vBulletin®. Copyright ©2000 - 2026, Jelsoft Enterprises Ltd. Перевод: zCarot
Администрация сайта не несёт ответственности за любую предоставленную посетителями информацию. Подробнее см. Правила.