मैं एक रेखा खंड को बिंदुओं के एक सेट में फिट करने की कोशिश कर रहा हूं लेकिन मुझे इसके लिए एल्गोरिदम खोजने में परेशानी है। मेरे पास 2D लाइन सेगमेंट L और 2D पॉइंट्स C का एक सेट है। L को किसी भी उपयुक्त तरीके से दर्शाया जा सकता है (मुझे परवाह नहीं है), जैसे समर्थन और परिभाषा वेक्टर, दो बिंदु, बाएं और दाएं बाध्य के साथ एक रैखिक समीकरण, ... केवल महत्वपूर्ण बात यह है कि रेखा है शुरुआत और अंत, इसलिए यह अनंत नहीं है।

मैं L को C में फ़िट करना चाहता हूं, ताकि c से L की सभी दूरियों का योग हो (जहां <कोड> code>c C में एक बिंदु है) को छोटा किया जाता है। यह कम से कम वर्ग समस्या है लेकिन मैं (सोचता हूं) बहुपद फिटिंग का उपयोग नहीं कर सकता, क्योंकि L केवल एक खंड है। उस क्षेत्र में मेरे गणितीय ज्ञान की थोड़ी कमी है इसलिए आगे पढ़ने पर किसी भी संकेत की भी सराहना की जाएगी।

यहाँ मेरी समस्या का एक उदाहरण है:

1

नारंगी रेखा को नीले बिंदुओं पर फिट किया जाना चाहिए ताकि प्रत्येक बिंदु की रेखा से दूरी के वर्गों का योग न्यूनतम हो। मुझे कोई फर्क नहीं पड़ता कि समाधान एक अलग भाषा में है या कोड बिल्कुल नहीं है, जब तक कि मैं इससे एक एल्गोरिदम निकाल सकता हूं।

चूंकि यह एक गणितीय प्रश्न से अधिक है, मुझे यकीन नहीं है कि यह SO के लिए ठीक है या इसे मान्य या गणित विनिमय को पार करने के लिए स्थानांतरित किया जाना चाहिए।

1
Timo 12 अप्रैल 2020, 23:19
क्या आप सभी बिंदुओं का उपयोग करना चाहते हैं? आप एक बिंदु और रेखा के बीच के अंतर को कैसे परिभाषित करना चाहेंगे? x दिशा में दूरी, y दिशा में, बिंदु और रेखा के बीच सबसे छोटा रास्ता?
 – 
Chelmy88
12 अप्रैल 2020, 23:25
दूरी को एक बिंदु और रेखा के बीच के सबसे छोटे पथ के रूप में परिभाषित किया गया है। कुछ मामलों में यह L के लिए लंबवत एक रेखा होगी और अन्य मामलों में यह L के अंतिम बिंदुओं में से एक के लिए एक रेखा होगी।
 – 
Timo
12 अप्रैल 2020, 23:31
क्या आपके पास लाइन की लंबाई पर कोई शर्त है? यदि ध्यान दें कि न्यूनतम दूरी को लंबवत बनाने के लिए रेखा को हमेशा बढ़ाया जा सकता है। रैखिक प्रतिगमन के लिए एल्गोरिथ्म को देखते हुए (जो y दिशा में दूरी को कम करेगा), मुझे लगता है कि इसे आसानी से अनुकूलित किया जा सकता है
 – 
Chelmy88
12 अप्रैल 2020, 23:38
रेखा की लंबाई एक पूर्व निर्धारित स्थिरांक है और इसे बदला नहीं जा सकता।
 – 
Timo
12 अप्रैल 2020, 23:51

2 जवाब

यहाँ अजगर में एक प्रस्ताव है। यहां प्रस्तावित दृष्टिकोण के आधार पर बिंदुओं और रेखा के बीच की दूरी की गणना की जाती है: एक ​​रेखा खंड को बिंदुओं के समूह में फ़िट करें

तथ्य यह है कि खंड की एक सीमित लंबाई है, जो min और max फ़ंक्शन, या if के उपयोग को यह देखने के लिए परीक्षण करती है कि हमें लंबवत दूरी या दूरी का उपयोग करना है या नहीं। अंतिम बिंदु, विश्लेषणात्मक समाधान प्राप्त करने के लिए वास्तव में कठिन (असंभव?) बनाता है।

इस प्रकार प्रस्तावित समाधान सर्वोत्तम समाधान प्राप्त करने के लिए अनुकूलन एल्गोरिथम का उपयोग करेगा। यह scipy.optimize.minimize का उपयोग करता है, देखें: https: //docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.minimize.html

चूंकि खंड की लंबाई निश्चित है, इसलिए हमारे पास स्वतंत्रता की केवल तीन डिग्री है। प्रस्तावित समाधान में मैं शुरुआती खंड बिंदु और खंड ढलान के x और y निर्देशांक का उपयोग मुक्त मापदंडों के रूप में करता हूं। मैं इन 3 मापदंडों और लंबाई से खंड का आरंभ और समाप्ति बिंदु प्राप्त करने के लिए getCoordinates फ़ंक्शन का उपयोग करता हूं।

import numpy as np
from scipy.optimize import minimize
import matplotlib.pyplot as plt
import math as m
from scipy.spatial import distance

# Plot the points and the segment
def plotFunction(points,x1,x2):
    'Plotting function for plane and iterations'
    plt.plot(points[:,0],points[:,1],'ro')
    plt.plot([x1[0],x2[0]],[x1[1],x2[1]])
    plt.xlim(0, 1)
    plt.ylim(0, 1)
    plt.show()

# Get the sum of the distance between all the points and the segment
# The segment is defined by guess and length were:
# guess[0]=x coordinate of the starting point
# guess[1]=y coordinate of the starting point
# guess[2]=slope
# Since distance is always >0 no need to use root mean square values
def getDist(guess,points,length):
  start_pt=np.array([guess[0],guess[1]])
  slope=guess[2]
  [x1,x2]=getCoordinates(start_pt,slope,length)
  total_dist=0
  # Loop over each points to get the distance between the point and the segment
  for pt in points:
    total_dist+=minimum_distance(x1,x2,pt,length)

  return(total_dist)

# Return minimum distance between line segment x1-x2 and point pt
# Adapted from https://stackoverflow.com/questions/849211/shortest-distance-between-a-point-and-a-line-segment
def minimum_distance(x1, x2, pt,length):
  length2 = length**2  # i.e. |x1-x2|^2 - avoid a sqrt, we use length that we already know to avoid re-computation
  if length2 == 0.0:
    return distance.euclidean(p, v);
  # Consider the line extending the segment, parameterized as x1 + t (x2 - x1).
  # We find projection of point p onto the line.
  # It falls where t = [(pt-x1) . (x2-x1)] / |x2-x1|^2
  # We clamp t from [0,1] to handle points outside the segment vw.
  t = max(0, min(1, np.dot(pt - x1, x2 - x1) / length2));
  projection = x1 + t * (x2 - x1);  # Projection falls on the segment
  return distance.euclidean(pt, projection);


# Get coordinates of start and end point of the segment from start_pt,
# slope and length, obtained by solving slope=dy/dx, dx^2+dy^2=length
def getCoordinates(start_pt,slope,length):
    x1=start_pt
    dx=length/m.sqrt(slope**2+1)
    dy=slope*dx
    x2=start_pt+np.array([dx,dy])
    return [x1,x2]

if __name__ == '__main__':
    # Generate random points
    num_points=20
    points=np.random.rand(num_points,2)

    # Starting position
    length=0.5
    start_pt=np.array([0.25,0.5])
    slope=0

    #Use scipy.optimize, minimize to find the best start_pt and slope combination
    res = minimize(getDist, x0=[start_pt[0],start_pt[1],slope], args=(points,length), method="Nelder-Mead")

    # Retreive best parameters
    start_pt=np.array([res.x[0],res.x[1]])
    slope=res.x[2]
    [x1,x2]=getCoordinates(start_pt,slope,length)

    print("\n** The best segment found is defined by:")
    print("\t** start_pt:\t",x1)
    print("\t** end_pt:\t",x2)
    print("\t** slope:\t",slope)
    print("** The total distance is:",getDist([x1[0],x2[1],slope],points,length),"\n")

    # Plot results
    plotFunction(points,x1,x2)
0
Chelmy88 13 अप्रैल 2020, 14:27

यह समाधान अपेक्षाकृत पहले से ही यहां पोस्ट किए गए के समान है, लेकिन मुझे लगता है कि यह थोड़ा अधिक कुशल, सुरुचिपूर्ण और समझने योग्य है, इसलिए मैंने समानता के बावजूद इसे पोस्ट किया है।

जैसा कि पहले ही लिखा जा चुका है, न्यूनतम (अधिकतम (...)) सूत्रीकरण इस समस्या को विश्लेषणात्मक रूप से हल करना कठिन बनाता है, यही वजह है कि scipy.optimize अच्छी तरह से फिट बैठता है।

समाधान https://math.stackexchange.com/questions/330269/the-distance-from-a-point-to-a-line-segment

import numpy as np
import matplotlib.pyplot as plt
from scipy.optimize import minimize, NonlinearConstraint


def calc_distance_from_point_set(v_):
    #v_ is accepted as 1d array to make easier with scipy.optimize
    #Reshape into two points
    v = (v_[:2].reshape(2, 1), v_[2:].reshape(2, 1))

    #Calculate t* for s(t*) = v_0 + t*(v_1-v_0), for the line segment w.r.t each point
    t_star_matrix = np.minimum(np.maximum(np.matmul(P-v[0].T, v[1]-v[0]) / np.linalg.norm(v[1]-v[0])**2, 0), 1)
    #Calculate s(t*)
    s_t_star_matrix = v[0]+((t_star_matrix.ravel())*(v[1]-v[0]))

    #Take distance between all points and respective point on segment
    distance_from_every_point = np.linalg.norm(P.T -s_t_star_matrix, axis=0)
    return np.sum(distance_from_every_point)

if __name__ == '__main__':

    #Random points from bounding box

    box_1 = np.random.uniform(-5, 5, 20)
    box_2 = np.random.uniform(-5, 5, 20)
    P = np.stack([box_1, box_2], axis=1)
    segment_length = 3
    segment_length_constraint = NonlinearConstraint(fun=lambda x: np.linalg.norm(np.array([x[0], x[1]]) - np.array([x[2] ,x[3]])), lb=[segment_length], ub=[segment_length])
    point = minimize(calc_distance_from_point_set, (0.0,-.0,1.0,1.0), options={'maxiter': 100, 'disp': True},constraints=segment_length_constraint).x
    plt.scatter(box_1, box_2)
    plt.plot([point[0], point[2]], [point[1], point[3]])

उदाहरण परिणाम:

enter image description here

1
ec2604 13 अप्रैल 2020, 17:42