Программирование с отображением графической информации

[Takada_sony]

Помогите пожалуйста:
Даны две точки М1 (х1 , у1 ), М2(х2 , у2 ) и прямая Ах+By+С=0. Необходимо найти на этой прямой такую точку М0 (х0 , у0 ), чтобы суммарное расстояние от нее до двух данных точек было минимально.

[Kostia]

Эта точка лежит на пересечении двух прямых Ах+By+С=0 и прямой проходящей через точки M1 и M2.
Составляешь уравнение прямой, потом решаешь системку с двумя неизвестными и решение этой системы и есть та точка которую требуется найти.

[Vago]

Сообщение от Kostia

Эта точка лежит на пересечении двух прямых Ах+By+С=0 и прямой проходящей через точки M1 и M2.

Ой ли?!

M1=(-1;0); M2=(1;0).
A = 1; B = 1; C = -2 (y = -x+2).
M0 это отнюдь не точка (2;0) будет!..

Added 19:36 CET
Не говоря уж о случае, когда эти прямые - параллельны.

[Kostia]

хм, да ты прав, возможно я слегка поторопился с ответом.
Ну тогда можно попробовать составить уравнения перпендикуляров к прямой проходящих через M1 и M2 и найти точки пересечения и найти точку которая лежит посередине этих точек(отрезка прямой) из которых исходят перпендикуляры.

[Vago]

Сообщение от Kostia

составить уравнения перпендикуляров к прямой проходящих через M1 и M2 и найти точки пересечения и найти точку которая лежит посередине этих точек

Тоже нет. Вернее, верно только в одном частном случае - когда прямые параллельны. Для набора же исх. данных, который я написал выше, по этим рассуждениям получается:
точки пересечения перпендикуляров: (0.5;1.5) и (1.5;0.5). Точка между ними - (1;1). Сумма расстояний = SQRT(5)+1 ~3.24
А искомая точка на самом деле - (1.25;0.75). Сумма расстояний = SQRT(2.25^2+0.75^2) + SQRT(0.25^2+0.75^2) ~2.37+0.79 ~3.16

[Takada_sony]

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

[Vago]

Про язык - ни слова, значит, я в его выборе абсолютно свободен?..

АлгорЫтм:

#!/usr/bin/python
# -*- coding: cp1251 -*-

from numpy import sqrt

# Вычисление y для конкретного x, принадлежащего прямой,
# заданной ур-ем Ax+By+C=0
def Y( x, A, B, C ):
    return (-A*x-C)/B


# Вычисление расстояния между точками (x1,y1) и (x2,y2)
def Dist( x1, y1, x2, y2 ):
    return sqrt( (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2) )


# В реальной программе заменить на ввод
x1 =  1.; y1 = 0.		# Первая из заданных точек
x2 = -1.; y2 = 0.		# Вторая заданная точка
A = 1.; B = 1.; C = -2.		# К-ты прямой
#2 A = 0.; B = 1.; C = -2.
#3 A = 1.; B = 0.; C = -2.

print "M1 = (", x1, ",", y1, ")   M2 = (", x2, ",", y2, ")"

# Определяем интервал [xS,xF], в пределах которого лежит искомая точка.
# Для этого найдём точки пересечения перпендикуляров к заданной прямой,
# проходящих через точки M1 и M2, с этой самой "заданной прямой".
if A != 0. and B != 0.:
    k0 = -A/B; b0 = -C/B
    # Перепендикуляр к заданной прямой через т.M1
    k1 = -1./k0; b1 = y1-k1*x1
#p	print k1, b1
    # Перепендикуляр к заданной прямой через т.M2
    k2 = -1./k0; b2 = y2-k2*x2
#p	print k2, b2
    xS = (b1-b0) / (k0-k1)
    xF = (b2-b0) / (k0-k2)
elif A == 0.:
    xS = x1; xF = x2

# Чтобы перебор, написанный ниже, работал, xS должно быть меньше, чем xF
# Если нужно - переставляем их.
if xF < xS:
    xF, xS = xS, xF	# Это в Питоне так просто делается циклическая перестановка двух переменных

#p print xS
#p print xF

deX = 0.001		# Шаг перебора
xMin = xS; distMin = Dist( xS, Y( xS, A, B, C ), x1, y1 ) + Dist( xS, Y( xS, A, B, C ), x2, y2 )

x = xS+deX
while x <= xF:
    dist = Dist( x, Y( x, A, B, C ), x1, y1 ) + Dist( x, Y( x, A, B, C ), x2, y2 )
    if dist < distMin:
        xMin = x
        distMin = dist
    x += deX

print "M0 = (", xMin, ",", Y( xMin, A, B, C ), ")"

#

При B=0 (прямая параллельна оси OY) программа работать не будет. Обработайте этот случай сами - попрактикуйтесь...

Ну а графику прилепить - это уже голая техника...

[Takada_sony]

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

[Vago]

Это, увы, не ко мне. Но по Делфи тут специалистов, по-моему, полно...

[evg_m]

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