algorithm - कैसे एक लाइन के साथ दर्पण बिंदु की गणना करने के लिए?




math graphics (4)

जब ऐसी चीजें कंप्यूटर प्रोग्राम में की जाती हैं, तो आपको इनमें से एक समस्या का सामना करना पड़ सकता है जो कि पूर्णांक अंकगणितीय (या जितना संभव हो) का उपयोग करके इन गणनाओं को पूरा करने के लिए है, यह मानते हुए कि इनपुट पूर्णांक में है यह पूर्णांक में जितना संभव हो उतना संभव है कि एक अलग मुद्दा यह है कि मैं यहाँ कवर नहीं करेगा।

निम्नलिखित एक "गणितीय" समाधान है, जो अगर लागू होता है तो शाब्दिक रूप से फ़्लोटिंग-बिंदु गणना की आवश्यकता होगी मुझे नहीं पता कि यह आपके मामले में स्वीकार्य है या नहीं। आप अपने स्वाद के लिए इसे अनुकूलित कर सकते हैं

(1) अपनी लाइन L द्वारा प्रतिनिधित्व करें

A * x + B * y + C = 0

समीकरण। ध्यान दें कि वेक्टर (A, B) इस रेखा का सामान्य वेक्टर है।

उदाहरण के लिए, यदि लाइन को दो बिंदुओं X1(x1, y1) और X2(x2, y2) से परिभाषित किया जाता है, तो

A = y2 - y1
B = -(x2 - x1)
C = -A * x1 - B * y1

(2) वेक्टर की लंबाई (A, B) सभी गुणांक को विभाजित करके समीकरण को सामान्य करें। Ie लंबाई की गणना

M = sqrt(A * A + B * B)

और फिर मूल्यों की गणना करें

A' = A / M
B' = B / M
C' = C / M

समीकरण

A' * x + B' * y + C' = 0

अभी भी आपकी लाइन L बराबर समीकरण है, सिवाय इसके कि अब सामान्य वेक्टर (A', B') एक इकाई वेक्टर है।

(3) अपना अंक P(px, py) और मूल्य की गणना करें

D = A' * px + B' * py + C'

यह आपको अपने प्वाइंट P से हस्ताक्षरित दूरी D को आपकी लाइन L । दूसरे शब्दों में, यह P से दूरी L से निकटतम बिंदु तक है (हमें वास्तव में निकटतम बिंदु की परवाह नहीं है, हमें सिर्फ दूरी चाहिए)।

संकेत कहते हैं कि लाइन L के किन किन किनारे पर P है। यदि P उसी तरफ निहित है, तो वेक्टर (A', B') ("सकारात्मक" पक्ष) की तरफ इशारा कर रहा है, दूरी सकारात्मक है। यदि P दूसरी तरफ ("नकारात्मक" तरफ) है, तो दूरी नकारात्मक है।

(4) अपने दर्पण बिंदु P'(px', py') खोजने के लिए आपको पूर्ण बिंदु से अपने बिंदु P को स्थानांतरित करने की आवश्यकता है |2 * D| लाइन के पार दूसरी ओर L

"रेखा के पार" वास्तव में इसका मतलब है कि यदि बिंदु P L के "सकारात्मक" पक्ष पर पड़ा था, तो हमें इसे "नकारात्मक" पक्ष में वेक्टर (A', B') की दिशा में स्थानांतरित करना होगा। और इसके विपरीत, यदि बिंदु P L के "नकारात्मक" पक्ष पर पड़ा था, तो हमें इसे "सकारात्मक" पक्ष में वेक्टर (A', B') की दिशा में स्थानांतरित करना होगा।

इसे केवल वेक्टर (A', B') की दिशा में बिंदु -2 * D (शून्य से नोट करें) की दूरी को स्थानांतरित करने के रूप में व्यक्त किया जा सकता है।

इसका मतलब है कि

px' = px - 2 * A' * D
py' = py - 2 * B' * D

आपको अपने दर्पण बिंदु P'(px', py')

वैकल्पिक रूप से, आप लाइन पर वास्तविक निकटतम बिंदु N ढूँढने के आधार पर एक दृष्टिकोण का उपयोग कर सकते हैं और फिर N संबंध में आपकी बिंदु P को प्रतिबिंबित कर सकते हैं। यह पहले से ही अन्य उत्तर में सुझाया गया है, मैं सिर्फ यह बताता हूँ कि मैं यह कैसे करूँ।

(1) एक समीकरण बनाएँ

A*x + B*y + C = 0

आपकी लाइन L , जैसा कि ऊपर चरण 1 में वर्णित है। इस समीकरण को सामान्य करने की कोई आवश्यकता नहीं है

(2) P माध्यम से गुजरने वाली लंब रेखा के लिए एक समीकरण बनाएं मान लीजिए कि लंब रेखा का प्रतिनिधित्व है

D*x + E*y + F = 0

D और E गुणांक अभी दूर जाना जाता है

D = B
E = -A

जबकि F गणना समीकरण में बिंदु P को प्रतिस्थापित करके की जा सकती है

F = -D*px - E*py

(3) दो रेखीय समीकरणों की प्रणाली को हल करके इन दो पंक्तियों के चौराहे का पता लगाएं

A*x + B*y = -C
D*x + E*y = -F

क्रामर का नियम इस मामले में बहुत अच्छी तरह से काम करता है। विकीपीडिया में रेखा प्रतिच्छेदन लेख में दिए गए फार्मूला इस प्रणाली में क्रैमर के नियम के आवेदन के अलावा कुछ भी नहीं है

समाधान आपको नजदीकी बिंदु N(nx, ny) हम चाहते थे।

(4) अब बस गणना करें

px' = nx + (nx - px)
py' = ny + (ny - py)

अपना अंक P'(px', py') खोजने के लिए

ध्यान दें कि यह दृष्टिकोण पूर्णतः पूर्णांकों में लागू किया जा सकता है। एकमात्र कदम है जो सटीकता खो सकता है चरण 3 में क्रैमर के नियम के अंदर विभाजन होता है। निश्चित रूप से, सामान्य रूप से, आपको "लगभग अभिन्न" समाधान के लिए भुगतान करना होगा, बड़ी संख्या में अंकगणित की आवश्यकता है। C और F भी गुणांक कर सकते हैं, क्रैमर के नियम फ़ार्मुलों के अंदर कम्प्यूटेशंस का उल्लेख भी नहीं कर सकते।

2 डी विमान में, मेरे पास एक बिंदु और एक रेखा है। कैसे इस लाइन के साथ दर्पण बिंदु प्राप्त करने के लिए?


प्रश्न के बिंदु पर रेखा के निकटतम बिंदु की गणना करें। फिर उन बिंदुओं के बीच वेक्टर की दिशा में पलटना और लाइन पर निकटतम बिंदु पर जोड़ें। वॉयला, आपको दर्पण बिंदु मिल गया है।


मैंने एक और सिस्टम के लिए यह बिल्कुल किया है जो मैंने बनाया है .. मेरे कोड में यह बहुत अधिक है; इसलिए मुझे आशा है कि मैंने सभी आवश्यक बिट्स Line.ClosestPoint(Point pt) ... Line.ClosestPoint(Point pt) एक विधि है जिसे आप चाहते हैं ...

एल्गोरिथ्म इस विचार पर आधारित है कि दी गई रेखा के ढलान के पारदर्शी गुणों को नकारात्मक गुणात्मक रूप से किसी भी रेखा से प्रति रेखा के ढलान पर आधारित है। यानी, यदि एक पंक्ति में ढलान एम है, तो दूसरी पंक्ति में ढलान -1 / मी है तो आपको जो सब करने की ज़रूरत है वह रेखा के माध्यम से रेखा के माध्यम से -1 / एम के बराबर ढलान के रूप में बना है और मूल रेखा के साथ इस रेखा के चौराहे को ढूंढें।

public class Line
{
    protected const double epsilon = 1.0e-8;

    public Point Anchor { get; set; }

    public double Slope { get; set; }

    public virtual Point ClosestPoint(Point pt)
    { return Intersection(Make(pt, -1 / Slope)); }

    protected Line(Point anchor, double slope)
    {
        Anchor = anchor;
        Slope = slope;
    }

    public static Line Make(Point anchor, double slope)
    { return new Line(anchor, slope); }

    public virtual Point Intersection(Line line)
    {
        if (lib.Within(line.Slope, Slope, epsilon))              
            if( lib.Within(line.YIntcpt, YIntcpt, epsilon))
                // code for NoInterceptException not included
                throw new NoInterceptException(
                    "The two lines overlap.");
            else return Point.NullPoint;
        // ----------------------------------------
        double tm = Slope, om = line.Slope,
            tx = Anchor.X, ty = Anchor.Y,
            ox = line.Anchor.X, oy = line.Anchor.Y;

        var x = double.IsInfinity(tm) ? tx :
                double.IsInfinity(om) ? ox :
                   (tm * tx - om * ox + oy - ty) /
                          (tm - om);

        var y = double.IsInfinity(tm) ?
               om * (x - ox) + oy :
               tm * (x - tx) + ty;

        return Point.Make(x, y);
    }
}

public struct Point
{
    const double epsilon = 1.0e-12;
    private readonly bool isDef;
    private readonly double y;
    private readonly double x;
    public bool HasValue { get { return isDef; } }
    public bool IsNull { get { return !isDef; } }

    private Point(double xValue, double yValue)
    { x = xValue; y = yValue; isDef = true; }
    public static Point Make(double x, double y)
    { return new Point(x, y); }

    public double X 
    {
        get
        {
                  // code for AlgebraicException not included
            if (IsNull) throw new AlgebraicException("Null Point Object"); 
            return x;
        }
    }
    public double Y
    {
        get
        {
                  // code for AlgebraicException not included
            if (IsNull) throw new AlgebraicException("Null Point Object");
            return y;
        }
    }

    public static Point NullPoint { get { return new Point();}}

    //  Other functionality

} 

यह विवरण इस बात पर निर्भर करता है कि आपकी रेखा का प्रतिनिधित्व कैसे किया जाता है। यदि आप इसे लाइन पर एक इकाई कॉलम वेक्टर एन के साथ लाइन पर एक मनमाना बिंदु पी के रूप में प्रतिनिधित्व करते हैं, तो दर्पण बिंदु Q 'किसी भी बिंदु पर Q द्वारा दिया जाता है:

क्यू '= क्यू 2 (आई - एनएन टी ) ( पी - क्यू )

(यहाँ, मैं 2x2 पहचान मैट्रिक्स है, एन टी एन के स्थानांतरण ( n को 2x1 मैट्रिक्स के रूप में इलाज कर रहा है), और nn टी 2x2 मैट्रिक्स है जो n टी के मानक मैट्रिक्स गुणा द्वारा निर्मित है) यह बहुत कठिन नहीं है दिखाओ कि क्यू 'यदि आप पी कहीं भी रेखा पर स्थानांतरित नहीं बदलेंगे।

अन्य रेखा अभ्यावेदन को बिंदु / इकाई वेक्टर प्रतिनिधित्व में परिवर्तित करना कठिन नहीं है





computational-geometry