простая геометрия

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

s/него/них/

Если за «проходит через» понимать «не лежит целиком вне», то все, что тебе нужно сделать, это вычислить, лежат ли все четыре точки в одном полупространстве, образуемом прямой, задаваемой твоим отрезком.

Это ровно четыре операции вычисления величины, которую школьники знают как «отклонение точки от прямой».

отличается знаком от других

предыдущих, которые до вычита альфы?

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

>>точькой

горизонтале

лучь

Убейся.

после

http://img844.imageshack.us/img844/2270/tmpw.png

пшёл вон!

в одном полупространстве, образуемом прямой,

я хз как это

да, спасибо, это работает вроде, правда пока не берусь доказывать, что на всех 360 градучах

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

Нихрена оно не работает. Луч может резать, а отрезок все равно находиться вне.

                                                                          
                                                                          
                                           zz                             
                                           z zzz                          
                                           z    zzz                       
                                          z        zzz                    
                                          z           zzzz                
                                          z               zzz             
                                          z                  zzz          
                                         z                      zzz       
                                         z                         zz     
                                         z                         z      
                                        z                         z       
                                        z                         z       
                           zzz          z                        z        
                     zzzzzz             z                       z         
               zzzzzz                  z                       z          
         zzzzzz                        z                      z           
      zzz                              z                      z           
                                      z                      z            
                                      z                     z             
                                      z                    z              
                                      z                   z               
                                     z                    z               
                                     z                   z                
                                     z         zzzzzzzzzz                 
                                    zzzzzzzzzzz                           
                                                                          
                                                                          

это легко проверить

если вашь способ мене затратный, чего хотелось бы, могли бы вы лучше нарисовать его?

вашь \ ваш :)

вертиш всё это вокруг второй точки отрезка, повторяеш алгоритм. дополнительное условие к исходному алгоритму: если один из полученых углов больше pi/2, то не проходит. доказывть щас не берусь, но идея думаю ясна.

s/pi/+-pi/

вертеть вроде как затратно, можно же просто проверить лежит ли точка в четырёхугольнике

а ты точно пробовал гуглить? :)

http://stackoverflow.com/questions/99353/how-to-test-if-a-line-segment-inters...

http://stackoverflow.com/questions/30080/how-to-know-if-a-line-intersects-a-p...

Похоже на бред школьника.

тебе очень выпендриться охота, да нечем? ещё раз говорю: пшел вон!

Gро полуплоскость правильно тебе говорят.

Если у нас есть ребро многоугольника, то мы можем перейти в систему координат одной из точек, тогда знак полуплоскости будет равен знаку выражения v1.x * v2.y - v1.y * v2.x, где v1 - радиус-вектор другого конца ребра, а v2 радиус-вектор какой-то точки. Так вот, если знаки полуплоскостей для двух точке различаются, они лежат по разные стороны от отрезка с концами (0,0) и (v1.x, v2.y) в нашей СК. Становится очевидно, что два отрезка пересекаются тогда и только тогда, когда концы _любого_ из них лежат по разные стороны от другого отрезка. Соответственно многоугольник пересекается отрезком только если этот отрезок пересекает хотябы одно ребро.

Решение простейшей задачи описано тысячу раз, в том числе мной выше и по ссылкам. Ты же посчитал, что недопродуманные ошметки твоего потока сознания, со свинскими грамматическими ошибками, будут кому-то интересны.

Так что «выпендриться охота, да нечем» - это про тебя. Пошел вон.

Кстати ты прав, это действительно классическое простое решение, активно применяющееся в вычислительной математике, например в построении анизотропных сетках.

Это ровно четыре операции вычисления величины, которую школьники знают как «отклонение точки от прямой».

Это правда поток сознания, однако мне понятно, что подразумевалось.

>>активно применяющееся в вычислительной математике, например в построении анизотропных сеток.

Логично, для определения полигонов, которые надо измельчить.

Кстати, какая величина является анизотропной в сетках, которые они называют анизотропными? Степень огрубления и измельчения?

Если да то именно анизотропность для возникновения подобной задачи не нужна особо.

Или они анизотропными называют вообще любые сетки с измельчением вблизи границ?

>Логично, для определения полигонов, которые надо измельчить.

В точности.

Степень огрубления и измельчения?

Пожалуй да.

Или они анизотропными называют вообще любые сетки с измельчением вблизи границ?

Необязательно границ, но ход мыслей верный.

>>Необязательно границ

Ну естественно не только границ но и, например, областей с получающимся большим градиентом искомой величины.

Пожалуй да.

Раз так, то выходит, что анизотропность тут была упомянута для красного словца, так как определять полигоны для измельчения приходится и для изотропных сеток, где скорость измельчения по всем направлениям одинакова ;)

+1

1) Если любая точка отрезка лежит в области прямоугольника - то ок

2) Иначе - если отрезок пересекает любое ребро прямоугольник - тоже ок

3) Иначе не пересекаются

К примеру так:

(defmethod include-p ((point point) (rectangle rectangle))
  (and (> (point-x point) (point-x (rectangle-a rectangle)))
       (> (point-y point) (point-y (rectangle-a rectangle)))
       (< (point-x point) (point-x (rectangle-b rectangle)))
       (< (point-y point) (point-y (rectangle-b rectangle)))))

(defmethod intersects-p ((line line) (rectangle rectangle))
  (or (include-p (line-a line) rectangle)
      (include-p (line-b line) rectangle)
      (apply #'or* (mapcar #'(lambda (e)
                               (intersects-p line e))
                            (lines rectangle)))))

Саму геометрию можно вводить так:

(defun symbol+ (&rest symbols)
  (intern (apply #'concatenate 'string (mapcar #'string symbols))))

;;;
;;; Define set as structure.
;;;

(defmacro define-structured-set ((name &key (element-type t) (initial-value nil) constructor) &rest elements)
  `(progn
     (defparameter ,(symbol+ '* name '-slots*) (list ,@(mapcar #'(lambda (e)
                                                                   `',(symbol+ name '- e))
                                                               elements)))
     (defstruct (,name (:constructor ,(if constructor constructor name) (,@elements)))
       ,@(mapcar #'(lambda (e) `(,e ,initial-value :type ,element-type)) elements))
     (defmethod print-object ((,name ,name) stream)
       (format stream "{~A}"
               (let ((string (format nil "~{~A, ~}"
                                     (list ,@(mapcar #'(lambda (e)
                                                         `(,(symbol+ name '- e) ,name))
                                                     elements)))))
                 (subseq string 0 (- (length string) 2)))))
     (defmacro for-each ((e type set) &body body)
       `(let (,e)
          (loop :for acc :in ,(symbol+ '* type '-slots*)
                :do (progn
                      (setf ,e (funcall acc ,set))
                      ,@body))))
     (values ',name)))

;;;
;;; Linear vector spaces, or LVS
;;;

;; Define LVS point as set of coordinates (for some basis)
;;
(defmacro define-LVS-point (name &rest coordinates)
  `(define-structured-set (,name :element-type integer :initial-value 0) ,@coordinates))

;; Define figure as set of points
;;
(defmacro define-figure ((name LVS &rest other-args) &rest points)
  `(define-structured-set (,name :element-type ,LVS ,@other-args) ,@points))

;;;
;;; Euclidean plane geometry
;;;

(define-LVS-point point x y)

(defmacro define-point-op (name op)
  `(defun ,name (a b)
     (point (,op (point-x a) (point-x b))
            (,op (point-y a) (point-y b)))))

(define-point-op point+ +)
(define-point-op point- -)

(define-figure (line point) a b)

;; (line (point 1 2) (point 3 4))
;; => {{1, 2}, {3, 4}}

(define-figure (quadrilateral point) a b c d)

(define-figure (rectangle point :constructor %rectangle) a b)
(defun rectangle (a dx dy)
  (%rectangle a (point+ a (point dx dy))))

(defmethod rectangle-slide ((rectangle rectangle) (point point))
  (%rectangle (point- (rectangle-a rectangle) point)
              (point- (rectangle-b rectangle) point)))

ещё - point это, конечно, скорее vector.

(defmethod include-p ((point point) (rectangle rectangle)) 
  (and (> (point-x point) (point-x (rectangle-a rectangle))) 
       (> (point-y point) (point-y (rectangle-a rectangle))) 
       (< (point-x point) (point-x (rectangle-b rectangle))) 
       (< (point-y point) (point-y (rectangle-b rectangle))))) 

Я почти уверен, что такие повторяющиеся рисунки в коде лиспа есть признак серьезной недоработки.

Это называется аккесоры - такая подробная запись в объектной системе Common Lisp вида (accessor class), реально тут просто записано кодом второе логическое правило (из тех трёх):

(p.x > rect.a.x) and (p.y > rect.a.y) and (p.x < rect.b.x) and (p.y < rect.b.y)

Т.е. произвольный 4-угольник разбивает пространство на 9 областей и эти четыре предиката создают сигнатуру которая вполне определяет - в какой именно областилежит точка. Для двух точек (линия) по этношению к произвольному 4-угольнику и его 9 областям значить будут комбинации номеров этих областей - (i -> i), (i -> k) и (i -> k -> l) стрелки и для каждой комбинации точно известно - пересекает прямая угольник или нет. Короче - достаточно заменить там функции > и < (они для прямоугольников) на более общие отношения и мы будем иметь дело уже с решением для произвольного 4-угольника.

Я почти уверен, что такие повторяющиеся рисунки в коде лиспа есть признак серьезной недоработки.

Точно, в коде лиспа так не пишут (я знал!) там пишут:

(произношу заклинание '(буэ !) '(теперь всё готово))

> и для каждой комбинации точно известно - пересекает прямая угольник или нет

не бейте ногами, если пишу чушь, неправильно поняв :)

123
456
789

взять например 4-9, тут может быть отрезок, как пересекающий 5, так и проходящий мимо

взять например 4-9, тут может быть отрезок, как пересекающий 5, так и проходящий мимо

Да, и всего 4 таких стрелки (точнее 8 просто (a b) = (b a)), я писал:

(i -> i), (i -> k) и (i -> k -> l)

поэтому нужны комбинации по три - скажем, (4, 9) мы можем представить как два «произведения»

(4, 9) = (4, 8) * (8, 9) =def= (4, 8, 9) (4, 9) = (4, 5) * (5, 9) =def= (4. 5. 9)

Вот я и имею в виду что каждая из комбинаций {(i i) (i k) (i k l)} вполне определяет текущую ситуацию (топологически).

(p.x > rect.a.x) and (p.y > rect.a.y) and (p.x < rect.b.x) and (p.y < rect.b.y) 

;; даёт сигнатуру (a : Bool, b : Bool, c : Bool, d : Bool)
 
or (include-p line.a rectangle) ;; это вида (5 ?)
   (include-p line.b rectangle) ;; а это (? 5)
   (map (intersects-p line e) (lines rectangle)) ;; а это True если пересечение контура угольника и линии имеет место быть.

Т.е. в данном случае все эти соображения про (i -> i), (i -> k) и (i -> k -> l) не используются - я просто так написал.

Молодой человек, не изобретайте велосипед и воспользуйтесь наработками человечества: JTS Topology Suite и General Polygon Clipper, последний так вообще с байндингами для десятка языков. Если охота поупражнять мозги - покопайтесь в исходниках вышеозначенных библиотек, посмотрите, как там решаются подобные задачи.

P.S. И да, не слушайте quasimoto, а то будете, как он, тратить на смешные задачи несмешное время, зато потом с гордостью заявлять: «Но морфизм есть!» :)

> Если за «проходит через» понимать «не лежит целиком вне», то все, что тебе нужно сделать, это вычислить, лежат ли все четыре точки в одном полупространстве, образуемом прямой, задаваемой твоим отрезком.

Перед этим постом не хватало фразы «Внимание, правильный ответ» :)

Там все равно потом нужно проверить, лежат ли обе точки отрезка по одинаковые стороны от обеих сабжевых прямых, и если да, то проверить, не лежат ли они целиком внутри (введя далекоудаленную точку прямой и посмотрев расклад знаков отклонения). Всего в 4 + 4 + 2 вычислений отклонений.

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

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

не изобретайте велосипед и воспользуйтесь наработками человечества: JTS Topology Suite и General Polygon Clipper

Это хорошие библиотеки, нет спору. Но самому нужно тоже уметь, я так считаю.

а то будете, как он, тратить на смешные задачи несмешное время, зато потом с гордостью заявлять: «Но морфизм есть!» :)

Так, а где написано что я потратил много времени? Отрезок пересекает фигуру тогда и только когда: одна из его точек лежит в области фигуры (проверяется достаточно легко), или он пересекает одно из рёбер фигуры (тоже просто). Вот и кода там - кот наплакал :) Всё остальное - размышления на тему (или это уже нельзя?).

Интересно было бы посмотреть, как на такой простой задаче правильно применить что-то вроде законов вычислительной сложности, (есть ли там аналог закона сохранения/минимальности энергии - закон сохранения/минимальности вычислительной сложности задачи?), чтобы определить признак оптимальности алгоритма вычисления.

Интересно куда копать, может кто знает.

>>одна из его точек лежит в области фигуры (проверяется достаточно легко), или он пересекает одно из рёбер фигуры (тоже просто)

Невзаимоисключающее или детектед. Сделайте меня развидеть это ;)

Это называется аккесоры - такая подробная запись в объектной системе Common Lisp вида (accessor class), реально тут просто записано кодом второе логическое правило (из тех трёх)

ну можно было и чуть меньше букв сделать:

(defmethod include-p ((p point) (r rectangle))
  (symbol-macrolet ((x point-x) (y point-y) (a rectangle-a) (b rectangle-b))
    (and (>  (x p)  (x (a r)) )
         (>  (y p)  (y (a r)) )
         (<  (x p)  (x (b r)) )
         (<  (y p)  (y (b r)) ))))

не?

Не :) Потому что есть with-accessors который и делает такие вот symbol-macrolet (можно посмотреть как - по macroexpand). Это дело вкуса - писать везде полные аккессоры или использовать with-accessors, есть проекты где придерживаются первого варианта, а есть любители второго.

Невзаимоисключающее или детектед. Сделайте меня развидеть это ;)

Не понял :) Если что, то под фигурой я понимаю, как обычно, 2-мерное множество, а не её контур (1-мерное). Если нужно пересечение с контуром то достаточно только второго пункта.

Я так сделал ещё потому что в CL `or' это не функция а специальная форма. Т.е.

or
  (include line-point-a figure)
  (include line-point-b figure)
  (intersects line figure-line-1)
  ..
  (intersects line figure-line-k)

Вернёт True на первом же истинном условии, а дальнейшие вычисления проводится не будут (а зачем?). Т.е. сложность алгоритма тут от некоторого минимального значения (k операций, для 4-угольника - 4) до некоторого максимального ( k*(2 + c) где c это количество операций для установления пересечения отрезка с отрезком, т.е. 4 (вроде как), для 4-угольника этот максимум будет 24 операциями).

Интересно куда копать, может кто знает.

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

Её можно построить (эту логику) примерно так:

1) Взять за основу поле рациональных чисел и линейное векторное пространство над ним. И ввести три сущности - точки, линии и фигуры. А именно - точки это кортежи чисел (длинна кортежа - 2, т.к. тут плоскость), линии это пары точек, а замкнутые фигуры образуются контурами, которые суть либо множества точек (безо всяких условий), либо множества линий (с условием замкнутости).

module Geom where
import Data.Ratio

-- 1.1) Let the field of ℚ : <ℚ, +, -, *, />
type Field = Rational

-- 1.2) Let the 2D linear vector space Ε as a set of 2-tuples over ℚ field
--      (2-tuple (a, b) is a set such as {a {b}})
data Vector = Vector Field Field deriving (Eq, Show)

zero_vector = Vector 0 0

(⊕) :: Vector -> Vector -> Vector
(Vector x1 y1) ⊕ (Vector x2 y2) = Vector (x1 + x2) (y1 + y2)

(⊖) :: Vector -> Vector -> Vector
(Vector x1 y1) ⊖ (Vector x2 y2) = Vector (x1 - x2) (y1 - y2)

(⊙) :: Field -> Vector -> Vector
rat ⊙ (Vector x y) = Vector (rat * x) (rat * y)

(⊘) :: Vector -> Field -> Vector
(Vector x y) ⊘ rat = Vector (x / rat) (y / rat)

-- 1.3) Vectors also represent a Point objects

type Point = Vector

point :: Field -> Field -> Point
point x y = Vector x y

-- 1.4) Line is a set of two Points

data Line = Line Point Point deriving (Eq, Show)

-- 1.5) Figure is a set of Points

type Figure = [Point]

-- Also Figure is a set of it lines:

figure_lines :: Figure -> [Line]
figure_lines figure = let first = (head figure)
                          collect (x:xs) = if xs /= []
                                           then (Line x (head xs)) : (collect xs)
                                           else (Line x first) : []
                          in collect figure

2) Потом вводится единственный геометрический предикат ↑ который определяет местоположения точки относительно линии (True если «выше/левее» и False если «ниже/правее»)

-- 2.1) Geom. predicate (simplification - for positive numbers only)

(↑) :: Point -> Line -> Bool
(Vector x y) ↑ (Line (Vector x1 y1) (Vector x2 y2)) = if x1 == x2
        then x < x1
        else if y1 == y2
             then y > y1
             else (y / x) > ((y2 - y1) / (x2 - x1))

(↓) :: Point -> Line -> Bool
point ↓ line = not (point ↑ line)

Этот предикат ↑ (ну и ↓) и есть основная операция в Евклидовой геометрии - реализованная на том или ином ЯП она будет транслирована в фиксированное количество машинных инструкций. К примеру, если мы говорим только о прямоугольниках, то ↑ это (>) , а ↓ это (<) - и то и другое это одна машинная инструкция. А в общем случае это (оптимально) 8 машинных инструкций.

3) Дальше утверждается что любое высказывание в логике Евклидовой геометрии это суть язык

EPrim ::= Point ↑ Line
Log1  ::= not
Log2  ::= or | and
EExpr ::= EPrim | Log1 EExpr | Log2 EExpr EExpr

И что любая задача логического характера в нём выражается. А так как терминалы этого языка - логические операции not/or/and, геометрический предикат ↑ и объекты Point и Line можно утверждать, что любая логическая задача в Евклидовой геометрии транслируется в инструкции какого-либо вычислителя (ЯП, грубо говоря), т.е. любая такая задача алгоритмически вычислима.

4) Например, вопрос о пересечении двух линий:

-- 4) lines intersections

(×) :: Line -> Line -> Bool
line1@(Line p11 p12) × line2@(Line p21 p22) = (((p11 ↑ line2) && (p12 ↓ line2)) || ((p11 ↓ line2) && (p12 ↑ line2)))
                                           && (((p21 ↑ line1) && (p22 ↓ line1)) || ((p21 ↓ line1) && (p22 ↑ line1)))

5) О том, принадлежит ли точка 4-угольнику:

-- 5) quadrilateral and point intersection

quadrilateral_include_point :: Figure -> Point -> Bool
quadrilateral_include_point figure point = let lines = (figure_lines figure)
                                           in (point ↑ (lines !! 0))
                                              && (point ↑ (lines !! 1))
                                              && (point ↓ (lines !! 2))
                                              && (point ↓ (lines !! 3))

rectangle :: Point -> Field -> Field -> Figure
rectangle (Vector x y) dx dy = [(point x        y)
                               ,(point (x + dx) y)
                               ,(point (x + dx) (y + dy))
                               ,(point x        (y + dy))]

-- quadrilateral_include_point (rectangle (point 0 0) 2 2) (point 1 1)
-- => True

6) О том, пересекает ли линия 4-угольник:

-- 6) line and quadrilateral intersection

line_intersect_figure :: Line -> Figure -> Bool
line_intersect_figure line@(Line p1 p2) figure = or [(quadrilateral_include_point figure p1)
                                                    ,(quadrilateral_include_point figure p2)
                                                    ,(or (map (× line) (figure_lines figure)))]

З.Ы. Я плохо знаю Haskell, поэтому там в коде, скорее всего, есть косяки. Ещё я не знаю правильно работает or или нет (т.е. как в CL, например).

Что касается оценок сложности, то, во-первых, их нужно делать в терминах количества операций ↑ (которые транслируются в некоторое небольшое количество машинных инструкций); во-вторых - тут нет понятия «входа», чтобы просто судить O(столько-то от n), входом может быть, например, количество точек/рёбер и прочих объектов в задаче. Но вот в задаче о линии и 4-угольнике это количество постоянно, поэтому, в-третьих, у каждой логической задачи будет распределение сложности (количества операций ↑) от минимального значения до максимального. Это распределение можно строить, например:

* 4-угольник разбивает пространство на 9 областей

* Существует конечное количество состояний. Каждое состояние линия+4-угольник параметризируется парой (a, b) где a - область в каторой лежит 1 точка линии, b - область в которой лежит 2 точка. При этом состояния (a, b) и (b, a) можно считать эквивалентными - (a, b) = (b, a).

* Для 4 состояний необходимо рассматривать разбиение (a, b) = (a, c-) * (c-, b), (a, c+) * (c+, b) т.е. это ещё 4 состояния.

* Всего будет |(a, a)| + |(a, b)|/2 + |(a, c-) * (c-, b), (a, c+) * (c+, b)|/2 = 9 + 8*9/2 + 8/2 = 49 состояний.

* Вот, и распределение сложности такое: для первого класса состояний будет достаточно 4↑ операции, для второго - 8↑, для третьего 16↑, четвёртого - 24↑, пятого - 32↑, шестого - 40↑. И всё - больше никаких вариантов тут нет. При этом последние четыре класса в общем-то независимы с точки зрения порядка - можно поискать хитрый способ свести их все к одному классу (чем и занимается метод Liang-Barsky для прямоугольников).

> Не :) Потому что есть with-accessors который и делает такие вот symbol-macrolet

я вкурсе про with-accessors и он делает не совсем такие symbol-macrolet, получилось бы более громоздко

>К примеру так:

А если стороны прямоугольника не параллельны осям координат? Вроде бы в таком случае это соотношение не работает?

Тогда нужно сделать my-with-accesors ;)

Общий вариант был тут